분류 전체보기

[python] 백준 - 2225. 합분해

🤔문제 해결 G5 | dp, 조합론 DP는 역시 손으로 해야 제맛이다. 예시의 20, 2는 너무 크기 때문에 6, 4로 바꿔서 구해봤다. 열은 N 행은 K이다. 즉 2열 3행은 2를 숫자 3개로 만드는 방법의 가짓수다. 딱 보면 규칙이 보일 것이다. i, j 는 i-1,j 와 i,j-1의 합이라는 것을... 원래의 규칙은 경우의 수를 모두 직접 구해보면 3열4행을 구할 때는 3행의 0~4열까지의 숫자를 더한 값이다. 그 이유는 0을 숫자 2개로: (0,0) 1을 숫자 2개로: (0,1), (1,0) 2를 숫자 2개로: (0,2), (1,1), (2,0) 각각의 경우의 수 뒤에 2, 1, 0 을 붙여주면 숫자 2를 3개로 구성하는 경우의 수는 6이 나온다. 💨 💻소스 코드 N, K = map(int, in..

[python] 백준 - 9251. LCS

🤔문제 해결 G5 | 다이나믹프로그래밍, 문자열 LCS란 최장 공통 부분 문자열(Longest Common Subsequence)이다. 순서는 맞지만 연속하지 않아도 되는 같은 문자열을 찾는 것이다. 예를 들어 ABCAB와 BDCB가 있다. ABCAB 와 BDCB 의 LCS는 BCB이다. LCS가 뭔지 안다고 해도 처음 접하면 구하는건 당연히 어렵다. 완전탐색을 하려고 했지만 역시나 시간초과가 발생했다. 문제 해결법이 DP이고 다른 고수들의 풀이방법을 참고해서 해결했다. 먼저 위와 같이 DP를 구성한다. 먼저 1번 째 행을 채워보면 AC와 C가 만나서 LCS는 1이다. 두번 째 행을 보자. A와 CA가 만나서 LCS는 1이다. ACA와 CA가 만나서 LCS는 2이다. 세번 째 행을 보자. A와 CAP =..

[python] 백준 - 11497. 통나무

🤔문제 해결 S1 | 정렬, 그리디 알고리즘 왼쪽과 오른쪽 끝을 최솟값으로 점점 채우는 방식으로 문제를 해결했음 리스트에서 최솟값을 꺼내는 방법은 힙큐를 사용 예시 [1, 2, 3, 4, 5, 6, 7] 위의 그림을 보면 가장 앞의 1과 가장 뒤의 2의 차이도 최소로 할 수 있음 다음 리스트 앞뒤로 값의 차이의 최댓값을 답으로 저장 💨 💻소스 코드 import heapq def solution(N, logs): heapq.heapify(logs) my_logs = [0] * N left = 0 right = -1 for _ in range(N // 2): my_logs[left] = heapq.heappop(logs) my_logs[right] = heapq.heappop(logs) left += 1 r..

버블 정렬(bubble sort)

📔 버블 정렬(bubble sort) 이란 서로 인접한 두 원소의 대소를 비교하여 정렬하는 알고리즘 2개의 반복문을 중첩해서 구현하기 때문에 시간복잡도는 O(n^2) 오름차순의 경우 1세트(바깥쪽 반복문)이 끝나면 가장 큰 수가 맨 뒤에 오게 된다. 내림차순의 경우 반대 📔 버블 정렬(bubble sort) 예제 위의 예제는 오름차순일 경우의 예제이다. 앞뒤의 숫자를 비교해서 앞의 숫자가 크면 뒤의 숫자랑 바꾼다. 1세트가 끝나면 가장 큰 수가 맨 뒤로 온다. 다음 세트부터는 맨 뒤의 숫자를 빼고 비교를 해준다. (이미 가장 큰 수이기 때문) 📔 버블 정렬(bubble sort) 구현 numbers = [5, 3, 8, 1, 2] print(f'정렬 전: {numbers}') print() for i i..

[python] 백준 - 2410. 2의 멱수의 합

🤔문제 해결 S1 | 다이나믹프로그래밍 유사한 문제 [python] 백준 - 9084. 동전 🤔문제 해결 1. S1 | 다이나믹 프로그래밍 2. target(만들어야 하는 금액)의 길이만큼의 리스트를 만든다. 3. 내가 가진 동전을 하나하나 꺼내서 리스트의 인덱스(내가 만들 수 있는 금액)과 비교하�� deok2kim.tistory.com 동전 문제와 다른 점은 동전은 처음부터 사용할 값이 정해져 있지만 이 문제는 N의 크기에 따라 사용할 수 있는 값이 늘어난다. N이 7이면 1,2,4 이지만 N이 8이면 1,2,4,8 을 사용할 수 있다. 💨 💻소스 코드 def solution(N): nums = [2 ** x for x in range(21)] dp = [0] * (N + 1) dp[0] = 1 fo..

[python] 백준 - 4883. 삼각 그래프

🤔문제 해결 S1 | 다이나믹프로그래밍 최소가중치? 라고 생각해서 별 생각없이 다익스트라로 풀었더니 바로 시간초과 다시 읽어보니 경로가 각 지점마다 단순해서 다이나믹프로그래밍으로 푸는 문제였다. 문제에서 주어진 삼각그래프와 똑같은 크기의 2차원리스트를 만든다. 리스트의 각 요소는 i,j에 도달 할 때의 가장 최솟값을 저장한다. 이제 dp 값을 저장하는 방법을 설명하면 먼저 1행까지는 직접 값을 채워 넣고, 나머지는 for문을 돌린다. (1,0): (0,1)에서 오는 값 (1,1): (0,1), (1,0)에서 오는 값 (1,2): (0,1), (1,1), (0,1)+(0,2) 에서 오는 값 여기서 중요한건 노란색으로 표시한 저 부분이다. 문제에서 각 노드의 가중치는 정수이다. 다시 말해서 음수가 포함되어 ..