병합 정렬(merge sort)
병합 정렬 알고리즘은 주어진 수열을 가운데에서 쪼개 비슷한 크기의 수열 두 개로 만든 뒤 이들을 재귀 호출을 이용해 각각 정렬합니다. 그 후 정렬된 배열을 하나로 합침으로써 정렬된 전체 수열을 얻습니다. 병합 정렬은 각 단계마다 반으로 나눈 부분 문제를 재귀 호출을 이용해 해결...
Recent posts
[백준 BOJ_9461] 파도반 수열 Python 풀이
출처: 백준 온라인 저지 문제 풀이 파도반 수열이라 해서 피보나치 수열과 크게 다를 바가 없습니다. 피보나치 수열은 fib(N) = (N-1) + (N-2) 이라면, 파도반 수열은 (N-2) + (N-3) 입니다. 동적계획법으로 간단하게 cache[0], cache[...
[백준 BOJ_9251] LCS Python 풀이
출처: 백준 온라인 저지 문제 풀이 예시로 주어진 문자열을 비교하는 표를 만들어보았습니다. 이 표가 그대로 memoization을 위 한 cache가 됩니다. 비교하는 문자가 같을 경우 이전의 공통부분(cache[i-1][j-1])에 문자를 추가해주어야 합니다. 문...
[백준 BOJ_9184] 신나는 함수 실행 Python 풀이
출처: 백준 온라인 저지 문제 풀이 코드 def w(a, b, c): if a <= 0 or b <= 0 or c <= 0: return 1 if cache[a][b][c] == -51: if a > 20 ...
[백준 BOJ_2579] 계단 오르기 Python 풀이
출처: 백준 온라인 저지 문제 풀이 주어진 조건을 예시 input으로 이해해 보았습니다. # stairs = [10, 20, 15, 25, 10, 20] 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. Start $ \rightarrow ...