Leo.K | To become a cooler Developer

알고리즘 풀이 챌린지 3일차이다. 평일에는 출근해서 점심시간에 짬짬이 풀고 포스팅을 하고 있지만,, 내일부터 시작될 설 연휴동안 문제를 풀 수 있을까 걱정이다.. ㅋㅋ 이왕 시작한거 연휴에도 쉬지 않고 매일 한 문제씩 꼭 진행해보자. 오늘은 프로그래머스 level2로 분류된 동적 계획법 문제를 가지고 왔다. https://school.programmers.co.kr/learn/courses/30/lessons/154538?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 동전으로 내야하는 금액을 맞추는 것과 아주 비슷한 ..

동적계획법 주어진 문제를 여러 부분 문제들로 나누어 푼 다음, 그 결과들로 큰 문제를 푸는 알고리즘 어떤 문제를 풀기 위해 해결해야 하는 부분 문제의 개수가 k개라고 한다면, 전체적으로 풀어야하는 문제의 개수는 O(kN)개가 될 것이다. 이때 k가 충분히 무시할 수 있을 정도로 작은 수이고, 각가의 문제를 푸는데 걸리는 시간이 O(1)이라면, 문제의 결과를 저장할 O(N)의 메모리가 필요하며, O(N)만큼의 시간이 소요된다. 분할 정복 vs DP 분할하는 점은 동일하지만 전자는 겹치는 부분문제가 없지만, 후자는 있다는 것이다. 따라서 메모이제이션 기법으로 비효율적인 반복 연산을 줄인다. Greedy vs DP 모든 경우를 메모리까지 소비해가며 샅샅이 체크하는 점에서 전자보다 후자가 실행 시간은 길지만, ..

동적 계획법 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 큰 문제를 푸는 것 F(N)을 구하기 위해서 풀어야 하는 문제의 개수는 O(N)개 이고, 이 답을 모두 저장할 O(N)의 메모리가 필요하며, 각각의 문제를 푸는 데 걸리는 시간이 O(1)이므로 O(N)개의 문제를 푸는 데 O(N)의 시간이 든다. 분할 정복 VS DP 분할정복과의 차이점은 분할정복은 문제를 분할했을 때 생성되는 부분 문제들 중 겹치는 문제가 발생하지 않는다. 하지만 DP는 겹치는 문제가 발생하기 때문에 메모이제이션 기법이 필요하다. EX) 피보나치 -> F(N)[구해야할 문제] = F(N-1) [ 부분 문제 ] + F(N-2) [ 부분 문제 ] Greedy VS DP 모든 경우를 메모리까지 소비해가며..