728x90 Dynamic Programming 썸네일형 리스트형 [백준알고리즘] 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 먼저, 아래의 코드는 비효율적으로 짰다. 아래 코드량만 봐도 왜 이리 긴가 싶을 건데.. 입력의 마지막 조건인 '승리하기 위해 건설해야 할 건물의 번호가 주어진다'는 사실을 몰랐다. 그래서 모든 건물의 건설 시간을 구하는 방안으로 구했다가... 그렇게 작성했던 코드에서 조금 수정하는 방안으로 코드를 작성하다 보니 비효율적으로 됐다. 어제 새벽에 풀.. 더보기 [백준알고리즘] 2630번: 색종이만들기 -Python [백준알고리즘] 2630번: 색종이만들기 -Python https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net 학교 공부하느라 정신이 없다ㅏ.. 머리 식힐 겸 간단한 거 하나 풀었다. 이 문제는 분할 정복 문제이다. 분할 정복과 동적 계획법은 비슷하지만 다른 개념이다. 간단하게 한 번 살펴보자면, 일단 둘 다 반복과 재.. 더보기 [백준알고리즘] 2293번: 동전 1 -C [백준알고리즘] 2293번: 동전 1 -C https://www.acmicpc.net/problem/2293 단계별로 풀어보기 마지막 '동적 계획법 1'의 마지막 문제였다. 그래서 기쁜 마음으로 봤는데 생각보다 쉬워서 흡족했다..ㅎㅎ 처음에는 일단 가볍게 동전 가치의 내림차순으로 정렬한 후에 재귀를 사용해서 해봤다. 역시나 시간초과가 발생했다. 그래서 다음에 사용한건 nsize와 target의 크기를 입력받아 nsize x target행렬을 만든 것이다. 이때부터는 점화식을 사용했기 때문에 내림차순 정렬이 필요없어진다. 사용했던 점화식은 다음과 같다. dp[i][j] = dp[i - 1][j] + dp[i][j - nlist[i]] (i번째 동전없이 j가치를 만들 수 있는 방법의 수) + (i번째 동전을.. 더보기 [알고리즘]Knuth's optimization 크누스 최적화 백준의 11066번 문제를 풀다가 발견한 최적화 기법이다. (문제를 해결했던 코드) 이 알고리즘은 동적 계획법으로 해결하는 문제에서 특수한 조건일 때 시간 복잡도를 \(O(n^3)\)에서 \(O(n^2)\)까지 줄일 수 있는 강력한 알고리즘이다. 사용할 수 있는 동적 계획법의 종류에는 이차원 배열인 \(C\)와 \(C\)를 이용한 Dynamic Programming을 적용한 이차원배열인 \(DP\)가 있다고 했을 때 다음과 같은 조건이 필요하다. 점화식의 형태: \(DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j]\) \((i < k < j)\) 사각 부등식: \(C[a][c] + C[b][d] 더보기 [백준알고리즘] 11066번: 파일 합치기 -Python [백준알고리즘] 11066번: 파일 합치기 -Python https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 추가) 새로 풀어봤다. 밑에 나오는 크누스 최적화를 사용 안 하고 그냥 .. 더보기 [백준알고리즘] 9251번: LCS -Python [백준알고리즘] 9251번: LCS -Python https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이번 문제는 LCS(Longest Common Subsequence) 문제이다. 임의의 두 문자열에서 각각의 sub sequence가 같을 때, 가장 긴 길이를 구하는 문제다. 이와 같은 문제를 전에 풀었었는데 엉뚱한 데에 정신이 팔려서 시간을 많이 잡아먹었다.. 문제를 풀기 위해서는 작은 sub seq.. 더보기 [백준알고리즘] 2565번: 전깃줄 -Python [백준알고리즘] 2565번: 전깃줄 -Python https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 20200408 아래부분에 새롭게 푼 코드를 올렸다. 내용은 동일한데 코드가 더 깔끔하다. 전깃줄 문제를 풀어봤다. 저번 문제에 이어서 LIS를 응용하는 문제라고 설명이 되어있습니다. '이게 왜 LIS 문제이냐'라고 한다면, 최소.. 더보기 이전 1 2 3 다음
