L.O.K

예제) 아래 이름 나열을 '가나다' 오름차순으로 나열하려고 할 때, 이름을 최소 몇 번 이동하면 구현이 가능할까? 위 이름 나열을 가나다 오름차순으로 나열하면 다음과 같다. 최소 횟수로 구현하려면 얼마나 공통된 순서로 배치되었는지를 확인하면 된다. 예를들어, 위치는 다르지만 류다영 → 신서리 → 이다영 → 홍원주 순은 두 배열 모두 동일하다. 그러므로 공통된 순서에 있지 않은 이름을 이동시키면된다. [동적계획법] 최장공통문자열 ( Longest Common SubSequence ) 동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우 lordofkang..

예제 ) 두 문자열의 최장 공통 문자열의 길이를 찾으시오 ASEFSDCA 와 SESDASEF Common SubString은 연속적으로 공통된 부분 문자열을 의미한다. ASEFSDCA 와 SESDASEF 인간은 직관으로 공통된 문자열을 찾을 수 있지만 최장 공통 문자열을 찾기란 쉽지않다 또한 컴퓨터는 직관을 갖고 있지 않다. 그러므로 포인터를 사용하여 두 문자열의 문자를 하나씩 비교해야 한다. 두 문자열을 비교하려면 두 개의 포인터가 필요하다. 두 개의 포인터를 움직이며 두 문자열의 문자를 하나씩 비교해본다. 포인터가 비교하는 모든 경우를 살펴보려면 이차원 테이블이 필요하다. 이차원 테이블에서 '대각선'은 의미가 크다. 포인터A와 포인터B가 동시에 한 칸씩 이동하면 대각선으로 한 칸 이동한다. 포인터A로..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 최장 공통 문자열 ( Longest Common SubSequence; LCS ) 예제) 주어진 두 문자열의 최장 공통 문자열을 구하라. [ abdcg , bdag ] SubString과 SubSequence 의 차이는 연속적이냐 비연속적이냐의 차이다. 두 문자열의 bd는 SubString이다. 두 문자열의 b , g는 SubSequence이다. 비연속적이지만 순서가 맞다. 한 마디로 LCS는 얼마나 두 문자열이 공통된 순서대로 배치되었는가를 확인하..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Longest Palindrome SubString 예제) 문자 수열이 주어질 때, 대칭을 이루는 부분수열 중 최대길이를 구하라. [ b, a, a, b, c ] Palindrome이란, 정방향으로 읽어도 역방향으로 읽어도 같은 배열을 의미한다. b, a, a, b 는 → 으로 읽어도 ← 으로 읽어도 같다. 이런 성질을 가진 부분수열 중 최대길이를 구해야 한다. Palindrome은 몇가지 특징을 가진다. 1) Prlindrome 성질을 가진 가장 ..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Maximum Product SubArray 예제) 정수로 구성된 한 수열이 주어질 때, 곱이 최대가 되는 부분수열을 구하라. [ 3, -2, 1, 0, -8, 9 ] 동적계획법을 발상하기 어려운 문제다. 부분수열로 분할할 수 있는 경우의 수가 너무 많다. Top에서 Down하면서 분할하기가 쉽지 않다. 그래서 일반적으로는 브루트포스 방법을 생각하게 된다. [ 3 ], [ 3, -2 ] [ 3, -2, 1] [ 3, -2, 1, 0 ] [ 3, -2..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Maximum Sum SubArray 예제) 정수로 구성된 한 수열이 주어질 때, 합이 최대가 되는 부분수열을 구하라. [ 5, -2, 9, -15, 8 ] 동적계획법을 발상하기 어려운 문제다. 부분수열로 분할 할 수 있는 경우의 수가 너무 많다. Top에서 Down하면서 분할하기가 쉽지 않다. 그래서 일반적으로는 브루트 포스 방법을 생각하게 된다. [ 5 ] , [ 5 ,-2 ] , [ 5, -2, 9 ] , [ 5, -2, 9, -15 ] , [..

동적계획법(Dynamic Programing)이란? 복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법 동적계획법은 분할된 모든 경우의 수를 검토한다. 중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. Decoding Ways A, B, C, D , ... , X, Y, Z가 1, 2, 3, 4, ... , 24, 25, 26 에 매칭될 때 , 주어진 수들로 만들 수 있는 디코딩 개수는 몇 개인가? [ 2, 3, 1, 1, 2, 4, 5 ] Top-Down 문자는 한 자리수 거나 두 자리수로 표현된다. 2는 B를 의미하고 23은 W를 의미한다. [ 2, 3, 1, 1, 2, 4, 5 ] 는 [ B , 3, 1, 1, 2, 4, 5 ] 와 [ W, ..

동적계획법(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까지 오는데 ..