본문 바로가기
728x90

Dynamic

[백준알고리즘] 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.. 더보기
[백준알고리즘] 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 별생각 없이 딕셔너리를 이용해서 풀었다. 현재까지의 누적 계산량과 인덱스를 쌍으로 하는 튜.. 더보기
[백준알고리즘] 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 할 때 문자열을 직접 넣어주었다. .. 더보기
[백준알고리즘] 2096번: 내려가기 -Python [백준알고리즘] 2096번: 내려가기 -Python https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 최대와 최소를 동시에 구해주어야 한다. 처음에는 large와 small을 구해주는 리스트를 처음에 주어진 크기와 같은 크기로 이중 리스트를 만들어 주었었다. 메모리 제한이 4MB이기 때문에 메모리 초과가 발생하게 되는데, 그래서 아래처럼 크기가 3인 리스트 두 개를 이용해서 최대 점수와 최소 점수를 구하도록 했다. n = int(input()) table = .. 더보기
[백준알고리즘] 1915번: 가장 큰 정사각형 -Python [백준알고리즘] 1915번: 가장 큰 정사각형 -Python https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 이게 왜이리 오래 걸렸는지 모르겠다. 엄청 많이 틀렸다.. 틀린 이유는 시간초과였는데, 결국 다른 풀이들을 찾아봤다. 처음에 시간 초과가 걸리게 푼 방법은 재귀 방식을 사용했다. 현재 위치를 정사각형의 왼쪽 위 꼭짓점이라고 생각을 하고 만들어지는 최대 정사각형의 변을 구했다. 다음 세개의 길이의 최솟값+1을 해줌으로써 현재 구할 수 있는 정사각형의 가장 큰 길이를 구했다. 가로로 이어지는 길이 세로로 이어지.. 더보기
[백준알고리즘] 1965번: 상자넣기 -Python [백준알고리즘] 1965번: 상자넣기 -Python https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 www.acmicpc.net 앞에 자신보다 앞에 있었으면서 자신보다 작은 상자가 포함하고 있는 최대의 상자 개수를.. 더보기
[백준알고리즘] 1937번: 욕심쟁이 판다 -Python [백준알고리즘] 1937번: 욕심쟁이 판다 -Python https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 www.acmicpc.net 재귀를 사용한 동적 계획법으로 문제를 풀었다. 시작점이 주어지지 않았기 때문.. 더보기
728x90

티스토리툴바