분류 전체보기

백준 2579 풀이 (다이나믹 프로그래밍, bottom-up, 계단 오르기)

이번 문제는 매번 그렇듯이 나에게 상당히 어려웠다. 재귀로 풀면 안된다는 느낌은 단박에 왔고, 다이나믹 프로그래밍을 써야한다는 느낌이 들었다. 물론 어떻게 써야할지 몰라서 문제였다. 그래서 다이나믹프로그래밍의 강좌를 듣고 bottom-up형식으로 풀어야한다는 것을 알게 되었다. bottom-up이란 작은 문제부터 풀어나가면서 결과를 저장시켜서 for 구문을 사용하여 푸는 방식이다. 일단 계단 오르기의 규칙은 다음과 같다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 여기서 중요한 ..

다이나믹 프로그래밍(동적 계획법)

다이나믹 프로그래밍이란 동적 계획법이라고 한다. 간단히 설명하자면 어떠한 문제를 한번에 해결하기 어렵기 때문에 작은 문제로 쪼개어 작은것 부터 하나씩 해결하여, 마지막에 문제를 해결하는 것이다. 솔직히 무슨 말인지 바로 와닿지 않는다. 그러나 원래 모를때는 일단 들으면서 알때까지 자료를 찾아보면 얼추 이해가 되기 마련이다. 다이나믹 프로그래밍에는 2가지가 존재한다. 1. Bottom-up : 작은 문제를 처음부터 풀어가는 방식이다. 주로 점화식을 세우고 for 구문으로 빠르게 해결해준다.(리스트나 배열에 직관적으로 구할 수 있는 값들이 넣어넣고 for 구문을 시작한다.) 2. Top-down : 재귀함수로 주로 구현하기 때문에 큰 문제를 풀기위해 작은 문제로 파고들어가서 작은 문제를 해결하면서 큰문제를 ..

백준 1932 풀이 (동적 계획법)

저번 문제가 1149 였는데 이때 굉장히 신기한 방식을 사용했다. 재귀로 풀어야할것 같은 최댓값 최소값을 구할때 뒤로 더해서 누적값을 만들어 주면 모든 경우를 염두하여 푸는 방식이 된다. 만약 이 삼각형의 각 층별 총합을 구하여 최댓값을 구하려면 재귀함수를 써야한다. 문제는 이러한 경우 재귀함수의 호출 갯수가 비약적으로 많아지게 된다는 것이다. 그래서 저번 1149 문제에서는 누적값을 만들어서 최솟값을 구했다. 이번에도 비슷한 방식으로 누적값을 만들어서 최댓값을 구하면된다. 아래에서 부터 어떤 선택을 할때 최댓값이 되는지 구하면서 올라가면 1층의 7은 최댓값으로 값이 변경된다. 코드는 굉장히 간단해진다. n = int(input()) tmp = [] for _ in range(n): tmp.append(..

백준 1149 풀이 (다이나믹 프로그래밍)

상당히 헤맸던 문제였다. 역시 더 열심히 해야겠다. 처음에는 R,G,B중에 하나를 정하고 이후부터 비용이 싼것만 골라나가면 최소의 비용을 찾을 수 있을거라고 생각했다. 물론 계속 생각하다보니 누락되는 최소비용들이 존재할거라는 생각이 들긴했다. 그렇다고 재귀함수를 짜서 값을 구하자니 시간제한이 0.5초 밖에 되지 않았다. 아무래도 재귀함수는 아닌거 같아서 고민을 상당히 많이 했다. 고수들의 코드를 슬쩍 보고오니, 최소 비용을 누적시켜서 확인하는 것을 알게 되었다. 즉, i번 집이 R로 칠해진다면 i-1번 집이 칠해지는 값중 가장 싼값을 선택해서 현재의 최종적인 최소비용을 구하는 방식이었다. 따라서 i번째 까지의 최종 비용을 누적 시켜서 n번째 집까지의 최종 비용을 구하는 것이었다. 이게 재밌는게 누적값을 ..

백준 9461 풀이 (파도반 수열, 메모제이션, 다이나믹 프로그래밍)

이번 문제는 상당히 쉽게 풀었다. 왜냐하면 이전에 피보나치수열을 경험해보았기 때문이다. 파도반 수열은 아래와 같다. [1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16 ......] 이 수열의 점화식을 세우면...... f(n) = f(n-1) + f(n-5) 단, n>5이어야한다. 따라서 제약조건을 토대로 재귀함수를 만들면 피보나치와 거의 유사하다. 하지만 이번에는 메모제이션 기법을 이용하여 효율적인 코딩을 해보기로 한다. (내 머리속 지우개는 굉장히 부지런하다보니 안쓰면 굉장히 빨리 까먹는다. 써볼 수 있을때 많이 써봐야한다.) n = int(input()) tmp = [0 for i in range(100)] tmp = [1,1,1,2,2] + tmp def pado(n): if n..

백준 1904 풀이 (재귀함수 인척하는 점화식 풀이)

이거 문제도 파악하고 금방 식을 세웠다. 그런데 재귀함수로 풀으려 했더니 메모리 초과나고, 출력도 초과나고 난리도 아니었다. 결국에 고수분들 푼거 슬쩍 보고오니 재귀함수로 푸는게 아니었다. 낚였다. 사실 재귀함수를 써야할 때가 있고 재귀함수를 안써도 되는 경우가 존재한다. 예를 들어 연산이 너무 많아지는 경우에는 재귀함수를 정말 써야하는지 고민해보아야한다. 만약 재귀함수를 써야하는 경우에는 다이나믹 프로그래밍을 염두해 보고, 그래도 초과가 난다면 최대 재귀 제한을 풀어주면 된다. import sys sys.setrecursionlimit(재귀횟수) 난 점화식도 세웠고 딱히 재귀함수를 써야할 필요성이 없음에도 재귀함수로 푸는 것이라 추측하고 재귀를 놓지를 못했다. 그래서 이렇게 뻘한 삽질을 반복했다. 그래..

백준 9184 풀이 (재귀함수, 메모제이션, 다이나믹 프로그래밍)

우선 이 문제를 보고 당혹감을 감출 수 없었다. 식을 그냥 줬다. 그냥 풀어보라고 줘버린것이다. 이런건 유저가 만들어야하는데 주는 이유가 있을것이다. 처음에는 규칙을 찾아야하나?하고 고민을 했다. 솔직히 저렇게 복잡하게 얽히고 섥혀있는데 규칙을 어떻게 찾나 고민을 했다. 그러다가 9184를 구글링 했더니 메모제이션이라는 기법이나 DP가 같이 쓰여있는 것을 확인했다. 그래서 메모제이션을 찾아보았다. 메모제이션이란 일반적인 재귀에서 이미 같은 인자를 연산했더라도 또 연산하는 경우가 존재한다. 그래서 이미 연산한 결과는 저장해두고, 만약 같은 연산이 필요할때 꺼내어 쓰자는 의도이다. ssminji.github.io/2020/02/05/the-cake-thief/ [알고리즘] Memoization(메모이제이션)..

백준 14889 풀이 (itertools,combinations)

이번에 itertools를 처음 배웠다. itertools는 자신만의 반복자를 만들기 위해서 사용되는 모듈이다. 즉 무엇인가 반복되는 요소를 쉽게 만들기 위해서 사용한다. 이 문제는 조합을 만들어야 하기 때문에 combinations를 함수에 대해서만 공부했다. combinations는 조합을 만들어 주는 함수이다. combinations([1,2,3,4], 2) 를 하면 4개의 수를 2조합으로 만들겠다는 의미다. 따라서 이러한 값을 이용해서 조합을 빠르게 구한다. 나는 조합을 못구해서 얼타다가 결국 고수의 코드를 참고하여 이해했다. from itertools import combinations N = int(input()) Nlist = [i for i in range(N)] Map = [] for _..