L.O.K

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 최소 동전 개수 ( Min Coin Change ) 동전 2원, 3원 5원이 있다. 각 동전은 무수히 많이 존재한다. 합이 11원이 되는 최소 동전 개수를 구하라. Top-Down 11원은 3가지 경우로 분할된다. 3가지 경우의 동전 개수 중 최소를 구해야 한다. 그럼 분할을 계속해보자. 4원은 3가지 경우가 있다. 2원 + 2원 1원 + 3원 -1원 + 5원 각 가격 별 최소 동전 개수의 배열은 아래와 같다. 1원 이나 음수인 경우 -1을 삽입하여..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 최소 경로 비용 합 ( Minimum Path Sum ) 타일 안에서 이동은 오른쪽이나 아래쪽만 가능하다. 각 타일에 비용이 할당되어 있을 때, 시작부터 끝까지 가는 최소 비용을 구하라. Top-Down 목적지에 도달할 수 있는 경우의 수는 A와 B 두 가지이다. A와 B의 비용을 구해 최소값을 선택하면 된다. A는 C와 D의 최소비용이다. Top-Down 방식을 적용하면 이렇게 하나씩 구하면 된다. 중복되는 경로의 비용을 저장하여 최소비용을 검토한..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Min Cost Climbing Stairs 사람은 한번에 한 칸 혹은 두 칸의 계단을 오를 수 있다. 계단을 오르는데 필요한 비용(cost)이 있다고 가정할 때, 꼭대기까지 오를 수 있는 최소비용을 얼마인가? Top-Down 계단4(꼭대기)에 도달하려면 계단2에서 두칸 뛰거나 계단3에서 한칸 뛰어야 한다. 계단을 뛰는데 걸리는 비용을 트리로 표현해보자. 계단2에서 계단4까지는 비용이 4가 든다. 그러나 Top-Down 방식이므로 계단2까지 오는데 ..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 피보나치 수열 F(n) = F(n-1) + F(n-2) F(n)은 F(n-1)과 F(n-2)로 나뉘어진다. F(n-1)은 F(n-2)와 F(n-3)으로 나뉘어진다. . . . 이처럼 가장 큰 단위가 작은 단위로 나뉘어지는 피보나치 수열은 동적계획법으로 풀기 적합하다. Top-Down F(7)은 피보나치 수열 공식에 따라 위 그림과 같이 분할되어 간다. F(1) = 1이고 F(0) = 0이라 주어지면 다시 위로 '결합'하며 올라간다. 이때 결과를 미리..

예제) 원을 따라 주유소가 다섯 곳이 있다. 주유소마다 주유할 수 있는 기름양은 다르다. 자동차는 한 곳의 주유소를 선택하여 주유를 한 뒤 이동한다. 주유소를 거칠 때 마다 주유소에서 제공하는 기름양만큼 주유가 가능할 때, 자동차가 원 한 바퀴를 돌 수 있으려면 어떤 주유소에서 출발해야 하는가? 주유소A에서 시작해보자. A B C D E 5 4 3 도착X ( 자동차가 각 주유소를 출발할 때 기름의 양) 주유소B에서 시작해보자. B C D E A 1 도착X ( 자동차가 각 주유소를 출발할 때 기름의 양 ) 이렇게 하나씩 접근하면 오래 걸린다. Greedy한 접근법을 사용하면 쉽게 처리할 수 있다. ( 현재를 기준으로 최적의 선택을 하는 방법 ) 주유소A 부터 다시 해보자. 현재 기준 : 주유소 A A B ..

예제 ) 주어진 문자열을 파티션으로 나누려 한다. 파티션에 포함된 문자는 다른 파티션에서 발견되면 안 될 때, 파티션 개수의 최솟값을 구하라. c가 파티션1과 파티션2에서 발견되므로 이와 같은 분류는 안 된다. 알고리즘 Greedy한 접근법을 이용해보자. ( 현재값을 기준으로 최적의 선택을 하는 방법 ) 1) 문자열의 문자를 좌측부터 하나씩 포인터로 지목한다. ( 현재 포인터 ) 2) 현재 포인터가 가리키는 문자의 마지막 포인터가 현재 포인터라면 파티션을 분리한다. ( 현재포인터 = 마지막 포인터 ) 그럼 마지막 포인터 정보를 알아야한다. 반복문을 돌려 문자열의 문자를 하나씩 체크한다. 문자의 마지막 인덱스가 무엇인지 HashMap 자료구조에 저장한다. 이제 Greedy한 접근법을 다시 해보자. 현재 포..

예제 ) 최소 몇 개의 구간을 없애야 겹치는 구간이 없을까? 몇 개를 없애야 할지 직관적으로 보이지 않는다. 이런 경우 문제를 뒤집어 보는 것도 좋다. 몇 개가 겹치는가 → 몇 개가 겹치지 않은가? 알고리즘 1) 시간이 빠른 순으로 정렬한다. 2) 0 부터 시작하여 하나씩 겹치는 구간은 제거한다. Greedy 접근법 ( 현재를 기준으로 최적의 값을 찾아가는 과정 ) 현재값 : 0 1은 0과 겹치므로 제거한다. 현재값 : 0 → 2 2는 0과 겹치지 않으므로 남는다. 현재값 : 2 3은 2와 겹치므로 제거한다. 현재값 : 2 4는 2와 겹치므로 제거한다. 3) 겹치지 않은 구간 2개이다. 총 5개의 구간에서 겹치지 않은 구간 2개를 빼면 겹치는 구간은 3개이다. 고로, 최소 3개의 구간을 없애야 겹치는 구..

예제) 미팅 스케줄이 아래 그림과 같을 때, 최소 몇 개의 미팅룸을 잡아야 하는가? 미팅룸에 시작시간 순서대로 미팅이 할당된다. 현재 생성된 미팅룸 중에서 가장 빨리 끝나는 시간(END)보다 START 시간이 빠르면 미팅룸을 하나 더 생성한다. 현재 가장 빨리 끝나는 시간을 기준으로 미팅룸을 만들지 안 만들지를 판단 ( Greedy 알고리즘 ) 알고리즘 1) 가장 빨리 끝나는 미팅룸 시간을 구하기 위해 최소 Heap을 생성한다. 미팅2는 9시에 시작하므로 최소 Heap 11시보다 작다. 미팅룸을 하나 더 생성한다. 미팅3은 10시에 시작하므로 최소 Heap 11보다 작다. 미팅룸을 하나 더 생성한다. 미팅4는 12시에 시작하므로 최소 heap 11보다 크다. 최소 heap 11을 제거하고 Heap을 재정..

예제3) 도시 A,B가 있다. 한 회사에서 직원 6명을 도시 A, B 각각 3명씩 출장 보낼 때 최소 비용을 구하라. A 도시와 B 도시에 직원을 할당 할 때, 어떤 직원을 우선적으로 할당해야 할까? 답 : A와 B 비용의 차이가 큰 직원 사람6의 경우 A도시를 가든, B 도시를 가든 100의 비용이 든다. 사람4의 경우 A도시를 가면 10의 비용이 들고 B 도시를 가면 100의 비용이 든다. 사람4를 A도시로 보내면 90을 절약할 수 있다. 절약할 수 있는 비용이 큰 직원부터 도시를 할당해야 된다. ( Greedy 알고리즘 ) 알고리즘 1) 비용의 차이를 기준으로 정렬한다. 2) 0부터 2까지는 B도시에 할당하고 3부터 5까지는 A도시에 할당한다. 참고영상

예제2) 문자 Arr에 반복되는 문자를 제거할 때 최소비용으로 제거하라. Greedy는 현재를 기준으로 최적을 선택하는 알고리즘이다. 알고리즘 Greedy한 접근방법 : 원소를 하나씩 접근할 때마다 현재를 기준으로 최소제거비용을 구한다. 현재의 Max 비용보다 낮으면 제거한다. 전체 범위 Max 비용을 고려하지 않는다. 참고영상