알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 다이나믹 프로그래밍과 슬라이딩 윈도우 알고리즘이 합쳐진 문제입니다. 문제를 풀기 위해서는 N값을 봐야합니다. N값이 100,000 까지지만, 메모리 제한이 4MB입니다. 따라서 N칸 만큼 배열을 만드는 것이 아닌, 입력을 받을 때마다, 최대, 최소값을 비교해야함을 알 수 있습니다. 입력이 들어올 때마다 최소, 최대값을 비교해야하기에 어떤 방식으로 이루어지는지 확인해보겠습니다. 최댓값을 구하는 ..

문제 링크입니다. https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 다이나믹 프로그래밍 문제입니다. (X , Y)로 올 수 있는 파이프의 종류가 3개이니, 3개의 경우로 나눠서 풀어야하는 문제였습니다. 좌표 (X , Y)가 있을 때, 해당 좌표에 도달할 수 있는 경우는 3가지입니다. 1. 가로 파이프로 도달 2. 세로 파이프로 도달 3. 대각선 파이프로 도달 각각의 경우에는 조건이 있습니다. 가로 파이프로 도달했을 경우는..

문제 링크입니다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 다이나믹 프로그래밍 문제였습니다. 문제만 읽으면 간단히 BFS, DFS로 풀 수 있는 문제지만 해당 알고리즘을 사용한다면 시간초과가 됩니다. 따라서 동적계획법과 회귀를 사용하여 푸는 문제입니다. 문제 조건입니다. 1. 자신이 있는 곳에서 상,하,좌,우 한곳으로 이동한다. 2. 이동한 곳에는 전에 있던 곳보다 대나무가 많아야한다. 3. 1,2조건을 만족하면서 최대한 오래 살..