백준

[python] 백준 - 11052. 카드 구매하기 / 16194. 카드 구매하기 2

🤔문제 해결 S1 | 다이나믹 프로그래밍 dp 리스트를 만든다. dp[i]: 카드 i장을 구매하기 위한 지불 금액의 최솟값 dp[0] = float('inf') (파이썬에서의 최댓값) dp[i-j] + dp[j]: 카드를 j장 구매하기 위한 최솟값과 카드를 i-j장 구매하기 위한 최솟값의 합 ex) dp[2] + dp[3]: 카드를 2장 구매하고 3장구매할 때의 최솟값 dp[i-j] + dp[j] 와 dp[i] 의 값을 비교하여 더 작은 값을 dp에 저장 테스트케이스 1번 예시 dp[0] = float('inf') dp[1] = 1 dp[2] = 5 | dp[2] = min(dp[2], dp[1]+dp[1]) | dp[2] = 2 dp[3] = 6 | dp[3] = min(dp[3], dp[2]+dp[1..

[python] 백준 - 1722. 순열의 순서

🤔문제 해결 S1 | 수학, 조합론 순열을 보면 itertools의 permutation이 생각난다. 하지만 이 문제에서는 N이 20까지 이므로 20!을 구하는것은 불가능. 먼저 소문제1일 때의 경우를 살펴보자. N = 5, K = 35 일 때(5개의 숫자, 35번째 순열) N = 5 이므로 5! = 120이다. 120 / N 으로 나누면 24가 되는데, 이는 각각의 앞자리 5개가 가지는 경우의 수이다. 앞자리가 1이면 1 ~ 24번째, 앞자리가 2이면 25 ~ 48번째, 앞자리가 3이면 49 ~ 72번째 ... 이다. K = 35이면 25~48이므로 앞자리가 2라는 것을 알 수 있다. 다음 스텝으로 넘어가면 n = 4, k = 35 - 24 = 11이다. 즉, 맨 2 이전의 숫자인 1이 맨 앞자리에 오..

[python] 백준 - 2240. 자두나무

🤔문제 해결 S1 | 다이나믹프로그래밍 1. 답은 X초에 Y번 움직여서 먹은 최대의 자두 갯수! 변수가 2개이니 2차원 리스트를 만든다. 다른 분들의 답을 보면 자두(사람 헷갈림)의 위치까지 저장하여 3차원으로 만든다. 하지만 이동 횟수에 따라 자두(사람)의 위치는 저절로 정해진다. 홀수번 움직이면 2번 나무에, 짝수번 움직이면 1번 나무에 있다. 2. 행을 초(0~자두갯수) 열을 움직일 수 있는 횟수(0~W) 만큼 2차원 리스트를 만든다. dp의 0번째 행은 0초때, 0번째 열은 움직이지 않았을 때 3. %중요% (1) 받아 먹는 조건: a. i초에 자두가 1번에서 떨어지고 이동 횟수가 짝수(j % 2 == 0, 1번 나무에 위치)하면 b. i초에 자두가 2번에서 떨어지고 이동 횟수가 홀수(j % 2 ..

[python] 백준 - 9084. 동전

🤔문제 해결 1. S1 | 다이나믹 프로그래밍 2. target(만들어야 하는 금액)의 길이만큼의 리스트를 만든다. 3. 내가 가진 동전을 하나하나 꺼내서 리스트의 인덱스(내가 만들 수 있는 금액)과 비교하여 만들 수 있으면 카운트를 세어준다. 4. 위의 표 처럼 각 동전을 꺼냈을 때 미리 만들어진 금액(인덱스)에 꺼낸 동전을 더해서 값을 쌓는다. 💨 다이나믹프로그래밍은 한번 해결한 문제는 다시 해결하지 않는다. 그리고 작은 문제를 해결하여 큰 문제를 해결한다는 의미!!!!!!!!! DP는 항상 어렵다.... 💻소스 코드 def _dp(): dp = [0] * (target + 1) # 경우의 수를 업데이트 할 리스트 dp[0] = 1 for coin in coins: # print('꺼낸 동전: ',c..

[python] 백준 - 1309. 동물원

🤔문제 해결 1. S1 | DP 2. 사자가 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 오른쪽에 있는 경우의 리스트를 만든다. 3. i번째에서 i-1번째에 사자의 상태에 따라 i번째의 경우의 수가 결정된다. (1) i번째에 사자가 없는 경우는 i-1번째에 사자가 왼쪽, 오른쪽 그리고 없어도 된다. (2) i번째에 사자가 왼쪽에 있는 경우는 i-1번째에 사자가 오른쪽에 있는 경우와 없는 경우만 가능하다. (i-1번째에 왼쪽에 있으면 i번째에서는 왼쪽에 있을 수 없다) (3) 오른쪽도 마찬가지 4. 경우의 수를 점차 더해나가면서 마지막 경우의 수를 다 더해준다. 💨 마지막에만 9901로 나누려고하면 메모리초과가 발생한다. 값을 쌓을 때 부터 나눠주면서 하자. 💻소스 코드 if __name__ == "__..

[python] 백준 - 1992. 쿼드트리

🤔문제 해결 1. 분할정복 | S1 2. 재귀함수를 이용했다 3. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 를 차례로 쪼개서 모두 1이나 0으로 이루어져 있는지 확인하고 4. 아닐 경우 다시 쪼개서 확인한다. 💨 맨 처음 배열이 모두 1인지 0인지 확인을 안해서 잠시 고민을 했던 문제!!! 답이 0이나 1이 될 수 있다 문제를 이해하는 것은 쉬우나 재귀함수를 사용했기 때문에 답을 출력하는게 힘들 수 있다. 맨 처음 함수에 들어왔다는 것은 하나의 묶음을 생성해야 하기 때문에 괄호를 사용해서 적절히 묶어준다.( 시작할 때 끝날 때) 💻소스 코드 from itertools import chain # 2중 리스트를 단일 리스트로 바꾸기 위해서 chain 함수 사용했음 def compression(lst)..