728x90 DP 썸네일형 리스트형 [백준알고리즘] 1890번: 점프 -C++ [백준알고리즘] 1890번: 점프 -C++ 1890번: 점프 (acmicpc.net) 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 누가 봐도 동적 계획법으로 풀어야 할 것 같은 문제다. 그래서 가능한 모든 경우를 찾는데 재귀를 사용했고, DFS를 사용했다. 사실 이전에 Python으로 풀었던 문제였다. 물론 기억은 나질 않았지만.. 아래 링크가 이전에 풀었던 코드다. [백준알고리즘] 1890번: 점프 -Python (tistory.com) [백준알고리즘] 1890번: 점프 -Python [백준알.. 더보기 [백준알고리즘] 1038번: 감소하는 수 -C++ [백준알고리즘] 1038번: 감소하는 수 -C++ 1038번: 감소하는 수 (acmicpc.net) 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 쉬운 듯 안 쉬운 듯한 문제.. DFS로 푸시는 분들이 많으신 것 같고 풀이가 많으신 것 같지만, 나는 DP로 풀었다. DP로 푸는 방법 중에서도 벡터를 두개만 사용해서 문제를 풀었다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 처음 문제를 접했을 때에는 숫자를 1씩 증가시키면서.. 그러면서 각각의 수가 감소하는 수인지 확인하는 방법으로 코.. 더보기 [백준알고리즘] 11060번: 점프 점프 -C++ [백준알고리즘] 11060번: 점프 점프 -C++ 11060번: 점프 점프 (acmicpc.net) 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 동적 계획법 문제다. 그렇게 어렵게 풀지는 않았으나, 생각지도 못한 반례가 있었어서 살짝 시간을 썼다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 재환이가 이동할 수 있는 칸만큼 오른쪽으로 이동하면 된다. 처음에 이 문제에서 놓쳤던 반례는 1x1 크기의 미로에 갇힌 경우도 있을 수 있다는 것이다. 이 부분을 고치고 나니 문제를 해결할 수 있었다... 더보기 [백준알고리즘] 2098번: 외판원 순회 -Python [백준알고리즘] 2098번: 외판원 순회 -Python https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 전에 외판원 순회 2를 푼 적이 있었는데, 그 이전 문제인 것 같다. 풀이는 여기에 썼었다. 외판원 순회 2와 같은 방법으로 문제를 풀면 된다. 전에 비트 마스크로 풀었던 기억이 인상 깊게 남아있었어서, 그렇게 풀까 하다가 브루.. 더보기 [백준알고리즘] 10164번: 격자상의 경로 -Python [백준알고리즘] 10164번: 격자상의 경로 -Python https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 경우의 수를 구해주는 문제이다. DP를 사용해 모든 경우의 수를 구해주면 된다. O표시가 없는 경우(k=0인 경우)에는 시작점에서 끝점까지 이동할 수 있는 모든 경우의 수를 구해주.. 더보기 [백준알고리즘] 5557번: 1학년 -Python [백준알고리즘] 5557번: 1학년 -Python https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 별생각 없이 딕셔너리를 이용해서 풀었다. 현재까지의 누적 계산량과 인덱스를 쌍으로 하는 튜.. 더보기 [백준알고리즘] 2352번: 반도체 설계 -Python [백준알고리즘] 2352번: 반도체 설계 -Python https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 언뜻 봐서는 O(N^2)의 방식의 풀이도 통과할 줄 알았는데 시간 초과가 발생했다. 이 문제는 LIS문제이다. 가장 긴 증가하는 부분 수열을 만들어야 한다. 여기서는 직접 부분 수열을 출력하는 것이 아닌 길이만 출력하면 되기 때문에 간단한 lower .. 더보기 [백준알고리즘] 9252번: LCS 2 -Python [백준알고리즘] 9252번: LCS 2 -Python https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이전에 LCS 문제를 푼 적이 있다. 아래는 그때 풀었던 코드이다. https://suri78.tistory.com/11 오랜만에 LCS 문제를 풀려니까 머리가 아팠었다. 결국 방식은 동일하게 됐었다. 다만 문자열도 출력해주어야 하기 때문에 memoization 할 때 문자열을 직접 넣어주었다. .. 더보기 이전 1 2 3 4 5 ··· 8 다음
