본문 바로가기
728x90

동적계획법

[백준알고리즘] 1038번: 감소하는 수 -C++ [백준알고리즘] 1038번: 감소하는 수 -C++ 1038번: 감소하는 수 (acmicpc.net) 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 쉬운 듯 안 쉬운 듯한 문제.. DFS로 푸시는 분들이 많으신 것 같고 풀이가 많으신 것 같지만, 나는 DP로 풀었다. DP로 푸는 방법 중에서도 벡터를 두개만 사용해서 문제를 풀었다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 처음 문제를 접했을 때에는 숫자를 1씩 증가시키면서.. 그러면서 각각의 수가 감소하는 수인지 확인하는 방법으로 코.. 더보기
[백준알고리즘] 1014번: 컨닝 -C++ [백준알고리즘] 1014번: 컨닝 -C++ 1014번: 컨닝 (acmicpc.net) 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 으으음.. 되게 어려웠다. 처음에는 단순히 Bruteforce 방식으로 푸는데 DFS를 적용해서 풀었다. 거의 다 풀었다가 생각해보니까 시간 복잡도가 초과한다는 것을 알게 되었다. 사실상 브루트 포스를 푸는 것이기 때문에 \(O(2^(n * m))\)의 시간 복잡도가 걸려 최대 \( 2^{100} = 1,267,650,600,228,229,401,496,703,205,376 \)라는 말도 연산.. 더보기
[백준알고리즘] 11060번: 점프 점프 -C++ [백준알고리즘] 11060번: 점프 점프 -C++ 11060번: 점프 점프 (acmicpc.net) 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 동적 계획법 문제다. 그렇게 어렵게 풀지는 않았으나, 생각지도 못한 반례가 있었어서 살짝 시간을 썼다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 재환이가 이동할 수 있는 칸만큼 오른쪽으로 이동하면 된다. 처음에 이 문제에서 놓쳤던 반례는 1x1 크기의 미로에 갇힌 경우도 있을 수 있다는 것이다. 이 부분을 고치고 나니 문제를 해결할 수 있었다... 더보기
[백준알고리즘] 9655번: 돌 게임 -C++ [백준알고리즘] 9655번: 돌 게임 -C++ 9655번: 돌 게임 (acmicpc.net) 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 동적계획법동적 계획법 문제이지만, 동적 계획법을 코드에 직접 작성하지 않아도 풀 수 있는 간단한 문제다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 처음 문제를 봤을 때에는 마지막 돌에 두는 모든 경우가 한 사람인 건가? 싶었다. 게임을 하는데 항상 누군가 승자가 정해져있다는 느낌의 문제였기 때문에 실제로 종이에 돌의 번호를 그려보고 상근이와 창영이가 두는 번호를 생각해봤다. 그랬더니 진짜로 겹치지 않는다는 것을 알게 되었다. 예제처럼 돌이 5개 있다고 생각해보자. 상근이가 항상 게.. 더보기
[백준알고리즘] 9184번: 신나는 함수 실행 -C++ [백준알고리즘] 9184번: 신나는 함수 실행 -C++ 9184번: 신나는 함수 실행 (acmicpc.net) 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 조건들이 다 주어졌기 때문에 되게 쉽게 풀었다. 문제에 적힌대로 저대로만 사용하면 시간이 오래 걸리기 때문에 하나의 장치를 두어야 한다. 잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다 추가해야 할 장치는 바로 메모이제이션(Memoization)이다. 메모이제이션은 재귀와 재귀를 사용하는 DFS, 동적 계획법과 같은 곳에서 많이 사용하는 방법으로, 이미.. 더보기
[백준알고리즘] 1005번: ACM Craft -C++ [백준알고리즘] 1005번: ACM Craft -C++ 1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 먼저, 아래의 코드는 비효율적으로 짰다. 아래 코드량만 봐도 왜 이리 긴가 싶을 건데.. 입력의 마지막 조건인 '승리하기 위해 건설해야 할 건물의 번호가 주어진다'는 사실을 몰랐다. 그래서 모든 건물의 건설 시간을 구하는 방안으로 구했다가... 그렇게 작성했던 코드에서 조금 수정하는 방안으로 코드를 작성하다 보니 비효율적으로 됐다. 어제 새벽에 풀.. 더보기
[백준알고리즘] 2775번: 부녀회장이 될테야 -C++ [백준알고리즘] 2775번: 부녀회장이 될테야 -C++ 2775번: 부녀회장이 될테야 (acmicpc.net) 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 동적 계획법을 이용해 풀었다. \(i\) 층 \(j\)호에는 \(i-1\) 층의 \(0\) 호부터 \(j\)호의 모든 거주민의 수만큼 살고 있다. 이때 \(0\)호부터 \(j-1\) 호까지의 모든 거주민의 수는 \(i\) 층의 \(j-1\) 호에 살고 있는 사람 수와 같다. 따라서 dp[i][j] = dp[i-1][j] + dp[i][j-1]이 성립하게 된다. #include void solv.. 더보기
[백준알고리즘] 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와 같은 방법으로 문제를 풀면 된다. 전에 비트 마스크로 풀었던 기억이 인상 깊게 남아있었어서, 그렇게 풀까 하다가 브루.. 더보기
728x90

티스토리툴바