알고리즘 (7) 썸네일형 리스트형 [백준] 2156 - 포도주 시식 아이데이션앞에서부터 값이 쭉 누적되면서, 이전 값을 사용할지말지를 결정하는 느낌으로 보아 다이나믹 프로그래밍으로 풀어야 하는문제라고 생각했다.현재의 위치에서 선택할 수 있는 경우의 수는 다음과 같다.1. 현재 위치의 포도주를 먹지 않고, 직전까지의 누적 값을 그대로 가져온다. (연속으로 3번 먹는 경우 일 수도 있으므로!!)2. 현재 위치의 포도주를 먹고, i - 2번째까지의 누적 값을 그대로 가져온다. (연속 3번이 아닌 것이 보장되므로!!)3. 현재 위치와 직전 위치의 포도주를 먹고, i - 3번째 까지의 누적 값을 그대로 가져온다. (마찬가지로, 연속 3번이 아닌 것이 보장되므로!!)이걸 관계로 나타내면,cache[i] = max(cache[i - 1], cache[i - 2] + board[i],.. [백준] 2193 - 이친수 아이데이션연속해서 숫자를 배열하는 문제를 풀어서 그런가 보자마자 2차원 dp로 풀어야겠다고 생각한 문제였다.사실 숫자가 0과 1밖에 없어서 1차원 dp 만으로도 풀리는 문제긴 하다!!왜그런지 좀 더 자세히 살펴보자문제에서 주어진 조건은 총 두개이다.1. 0으로 시작하지 말 것2. 1이 두번 연속으로 배열되지 말 것 이 말은 이렇게도 바꿀 수 있다.n자리 수의 i번째 자리의 숫자를 넣을 때,1. 1번째 자리는 1만 넣을 것2. i - 2까지의 경우의 수에서 01을 넣거나,i - 1까지의 경우의 수에서 0을 넣을 것이 관계를 수식으로 나타내면 다음과 같다cache[i] = cache[i - 2] + cache[i - 1] 풀이 n = int(input())cache = [[0] * (n + 1) for _ .. [백준] 10844 - 쉬운 계단수 아이데이션처음엔 너무 쉽게 2n - 1로 풀었으나, 틀렸습니다!!의 연속이었다.곰곰히 생각해보니까, 이건 저런 단순한 수식이 아니라2차원 DP로 풀어야 하는 문제인 것 같았다.n자리 수에 0 ~ 9의 숫자를 잘 넣으면 되는 문제이고,n자리에 넣을 숫자는 n - 1자리의 숫자의 영향을 받으니까 관계도 확실했다.아래 풀이를 보자사진에서 새로는 0 ~ 9까지 들어갈 수 있는 숫자이고,가로는 n자리수를 의미한다. 어떤 자릿수에 0이 들어갈 수 있는 경우의 수는앞 숫자가 1인 경우 하나 밖에 없다.1 ~ 8가 들어갈 수 있는 경우의 수는앞이 현 숫자보다 1 작거나, 1 큰 경우의 수의 합이다.예를 들어서, 현재 숫자가 8이면앞 숫자가 9이거나 7이어야 되므로 두 경우의 수를 더해주면 된다.그림으로 나타내면 위 브.. [백준] 9095 - 1, 2, 3 더하기 아이데이션앞서 풀었던 2xn 타일링 문제를 1x1 타일링 문제처럼 바꾸면 쉽게 풀 수 있다사실 이렇게 쉽게 생각할 수 있는 이유는 순서가 고려되어서 1 + 1 + 2와 2 + 1 + 1이 다른 경우의 수로 세어지기 때문이다아무튼! 고려할 수 있는 경우의 수는 다음과 같다!1. i - 1에서 1 더하기2. i - 2에서 2 더하기3. i - 3에서 3 더하기이렇게 해서 i번째 경우의 수는 (i - 1의 경우의 수) + (i + 2의 경우의 수) + (i - 3의 경우의 수)로 업데이트 할 수 있다 풀이t = int(input())for _ in range(t): n = int(input()) cache = [i for i in range(n + 1)] cache[0] = 1 for i.. [백준] 11727 - 2xn 타일링 2 아이데이션앞서 풀었던 2xn 타일링 문제에서 조건 하나가 추가된 버전이다.앞선 문제와 마찬가지로 다이나믹 프로그래밍을 이용하여 풀었다다만, 2x2 타일이 추가 되었기 때문에 해당 조건을 고려해주기 위하여,1. n - 1까지 쌓은 상태에서 2x1 타일을 하나 쌓기2. n - 2까지 쌓은 상태에서 2x1 타일을 두개 쌓기의 2번 조건을 다음과 같이 수정하였다. 2-1. n - 2까지 쌓은 상태에서 2x1 타일을 두개 쌓기2-2. n - 2까지 쌓은 상태에서 2x2 타일을 두개 쌓기 2의 갈래가 두가지로 나눠졌기 때문에 cache[i - 2] * 2를 해주었다. 풀이 n = int(input())cache = [1] * (n + 1)for i in range(2, n + 1, 1): cache[i] = .. [백준] 11726 - 2xn 타일링 아이데이션전형적인 다이나믹 프로그래밍 문제이다!!n = 1일 때부터 블럭을 차근차근 쌓아 나가면서, 두가지 갈래를 선택하게 된다1. n - 1까지 쌓은 상태에서 2x1 타일을 하나 쌓기2. n - 2까지 쌓은 상태에서 2x1 타일을 두개 쌓기그럼 현재의 경우의 수는? 1과 2를 더한 값이 된다!!풀이 n = int(input())cache = [1] * (n + 1)for i in range(2, n + 1, 1): cache[i] = cache[i - 2] + cache[i - 1]print(cache[n] % 10007) [백준] 1463 - 1로 만들기 아이데이션이렇게 문제를 딱 봤을 때, 1차원 배열이 머릿속에 그려지고 징검다리 퐁퐁(?) 건너는 듯한 문제는보통 그래프(DFS/DBF) 나 다이나믹 프로그래밍으로 풀리는 경우가 많았다이 문제는 그래프보다는 다이나믹 프로그래밍으로 풀어야 한다고 생각했는데 이유는 다음과 같다1. 주어진 숫자가 계속해서 감소하기만 한다더하는 연산이 없기 때문에 한번 감소하면 다시 증가할 수 없다.즉 숫자의 변화가 한 방향으로만 계속 된다.만약 중간에 증가하는 연산이 있다면, 타겟값을 찾을 때까지 숫자들이 계속 연결되는 그래프 형태를 띄기 때문에그래프 형태로 문제를 푸는 것이 맞다2. 최솟값을 찾는다이건 꼭 다이나믹 프로그래밍 만의 특성이라고는 볼 수 없지만!!아무튼 다이나믹 프로그래밍 문제에서 많이 나오는 조건이여서 넣었다 .. 이전 1 다음
