알고리즘 별 문제 정리 (33) 썸네일형 리스트형 [C++] 백준 2565: 전깃줄 https://www.acmicpc.net/problem/2565 풀이입력을 받을 때 두 개의 전깃줄을 동시에 받으므로 vector 자료형의 pair를 통해 받은 뒤,정렬을 해주면 될 것 같았다. 정렬을 하고 ,dp[i] = i번째 전깃줄이 교차하지 않고 연결되어 있기위한 없애야 하는 전깃줄의 최소 개수로 가정하고 풀이를 떠올려봤는데 도저히 감이 안 잡혔다. 인터넷 검색을 통해 풀이를 슬쩍 봤는데,가장 긴 증가하는 부분수열을 활용하는 문제라고 나와있었다.그걸 보자마자 무릎을 탁 쳤다!!https://www.acmicpc.net/problem/11053 dp[i] = i번째까지 중 가장 긴 증가하는 부분수열의 길이로 하면이미 좌측 배열의 값은 정렬이 되어있는 상태이기에, dp[i] = i번째까지의 전.. [C++] 백준 2133: 타일 채우기 https://www.acmicpc.net/problem/2133 문제의 설명이 매우 단순하니만큼 시뮬레이션을 돌려봐야 할 거 같다는 생각이 들었다.dp[i] = 3 * i 크기의 벽을 타일로 채우는 경우의 수로 가정하고, 차근차근 N = 1부터 진행해보자. 풀이N = 12 * 1과 1 * 2의 타일로는 3 * 1을 채울 수 없다.즉 dp[1] = 0 N = 2 로 총 3가지의 모양이 나온다.즉 dp[2] = 3 N = 3역시 타일을 채울 수 없었다.여기까지 했으면 N에 홀수가 들어갈경우 dp배열의 값이 0이라는 걸 추측이 가능하다. N = 4중앙을 기준으로 나눴을 때, dp[2] * dp[2] = 9라는 걸 알 수 있다.그럼 dp[4] = 9인걸까??? 답은 아니다이다.문제의 힌트를 유심히 보면4.. [C++] 백준 2225: 합분해 https://www.acmicpc.net/problem/2225 합이 N이 될 수 있는 경우의 수를 구하는 문제이다! 이 문제를 어렵게 하는 건 다음의 사항이었다.1. 0도 더할 수 있다.2. 한 개의 수를 여러 번 쓸 수 있다. 풀이일단 dp를 사용하면 될 것 같았다.1차원 dp를 n에 따라 사용해볼까 했지만,k라는 변수도 사용하려면 2차원 배열을 사용해야 될 것 같았다. 그래서 dp[i][j] = i개의 숫자를 사용해서 j가 되게 하는 경우의 수로 가정했다. 수학 아이디어가 좋아 점화식이 파바박 나오면 좋겠지만 그렇지는 않았다.그렇기에 일단 시뮬레이션을 돌려보기로 했다.N = 4, K = 4로 하고 시뮬레이션을 돌려봤다. K\N12341111122345336101544102035 무언가 규칙이.. [C++] 백준 2294: 동전 2 https://www.acmicpc.net/problem/2294 2293. 동전 1과 굉장히 유사한 문제이다.다른 점은 경우의 수를 구하는 것이 아니라 사용된 동전의 개수의 최솟값을 구하는 점 정도이다. 풀이도 굉장히 유사한 편이다.dp 배열의 값을 그 가치를 만드는 데 필요한 동전의 최소 개수로 지정해주면 매우 쉽게 풀 수 있다. 점화식은 다음과 같다dp[j] = min(dp[j-coin[i]] + 1, dp[j]);'원래 동전의 최소 개수'와 'i번째 코인을 사용했을 때의 개수 + 1'을 비교해서최솟값을 넣어주는 느낌이다.가치가 6일때를 비교해보면1원의 동전까지만 사용했을 경우 dp배열에 6이 들어가있다.5원의 동전까지 사용할 경우 min(dp[6-5] + 1, 6) = min(dp[1]+1, 6.. [C++] 백준 1520: 내리막 길 https://www.acmicpc.net/problem/1520 지도가 주어졌고 끝 지점까지 탐색하는 문제이기에 DFS를 사용해야 됨을 인지했습니다. 다 탐색할경우 4^(500 * 500)이였기에 시간복잡도를 줄일 방법이 필요했고, 그에 따라 DP를 사용해야 되는 것까지는 인지를 했는데 어떤 식으로 접근할 지 고민이 됐습니다. 처음 접근은 'dp 배열의 값 = 이 지점까지 올 수 있는 경로의 개수'로 지정했습니다.dp[m][n]에 정답이 나오도록 한 것이죠. 하지만 DFS를 통해 끝지점에 도착한 뒤, 재귀를 통해 이전 배열의 값을 하나씩 구해가야 하는데,마지막 점에 도착했을 때 리턴 값을 뭐로 해야할 지가 참 난감했습니다. 마지막 값에서 이전 방향의 값들을 모두 더한다?근데 그럼 거기서 또 dfs를.. [C++] 백준 11504: 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 이 문제는 '11053. 가장 긴 증가하는 부분 수열 문제' or '11722. 가장 긴 감소하는 부분 수열 문제'를 풀어봤을 경우 매우 간단하게 풀 수 있다. 바이토닉 수열은 문제의 설명을 읽어봤을 때 증가하는 부분수열 + 감소하는 부분수열이다.그렇다면 가장 긴 증가하는 바이토닉 수열도 마찬가지라는 뜻이다.여기서 주의할 점은 가장 긴 증가하는 부분 수열의 길이와 가장 긴 감소하는 부분 수열의 길이를 더해서는 안된다는 것이다. 두 수열이 가장 길 때의 시점이 같지 않을 수 있기에,두 시점의 길이를 저장하는 배열을 따로따로 만들어줘야 한다. 숫자가 1개 존재할 때도 자기자신으로만 이루어진 수열이므로 모든 dp값의 초기값은 1로 설정한다.. [C++] 백준 2293: 동전 1 https://www.acmicpc.net/problem/2293 조건을 보면 시간 제한과 메모리 제한이 빠듯한 문제이다.그 점을 유의하지 않으면 몇 번이나 틀릴 수 있다 ㅠㅠㅠ 문제를 보면 n가지 종류의 동전으로 가치의 합이 k가 되도록 하는 경우의 수를 구하는 문제이다. 배열의 한 축을 가치의 합으로 두면 문제가 풀릴 거 같아 그대로 진행해봤다!처음에는 동전의 종류도 배열의 한 축으로 둬서 2차원으로 생각해봤는데 풀이가 영 생각이 나지 않아서,1차원으로 바꾸어서 진행했다. 먼저 예제를 통해 시뮬레이션을 돌려보자.1원이 되는 경우: 12원이 되는 경우: 1 1 / 23원이 되는 경우: 1 1 1 / 1 24원이 되는 경우: 1 1 1 1 / 1 1 2 / 2 25원이 되는 경우: 1 1 1 1 .. [C++] 백준 9251: LCS https://www.acmicpc.net/problem/9251 모든 가능한 수열을 다 비교할경우 0.1초의 시간제한으로 인해 틀리게된다.이 문제의 경우 DP를 사용하면 편하게 풀 수 있다! 자, DP이므로 배열의 의미를 잘 지정하는 것이 중요하다. 어떤 식으로 배열을 설정하면 좋을까?이 문제는 i와 j에 각각 문자열의 문자를 대입시키고dp[i][j]의 값으로 두 문자열의 LCS를 지정하면 된다. 이 문제를 풀어보지 않았다면 i와 j에 이런 식으로 대입시키는 건 생각 못했을 거 같다. 그럼 점화식은 어떻게 구할까?dp의 경우 논리적으로 사고하기 어렵다면 시뮬레이션을 돌려보는 것이 크게 도움이 되는 경우가 많다.이 문제도 같은 경우이다. 먼저 예제의 ACAYKP를 i에, CAPCAK를 j에 대입시킨다.. 이전 1 2 3 4 5 다음
