# Foundation/알고리즘
가장 긴 증가하는 부분 수열 (LIS - Longest Increasing Subsequence) 알고리즘
가장 긴 증가하는 부분 수열 (LIS)최장 증가 부분 수열 문제란, 주어진 수열에서 오름차순으로 되어있는 가장 긴 부분수열을 찾는 문제이다. 이 때, 부분수열은 반드시 연속적일 필요는 없으며,필요하다면 중간을 건너뛰는 것도 가능하다. 예를 들어, 수열 A = {10, 20, 60, 50, 30, 40, 20} 에서,가장 긴 증가하는 부분 수열은 A = {10, 20, 60, 50, 30, 40, 20} 이고, 길이는 4 이다. 대표적인 동적 계획법(Dynamic Programming) 문제이며,이 게시글에서 설명할 주제는 다음과 같다.LIS의 특성N^2 문제풀이N*logN 문제풀이경로 역추적 (백트래킹) LIS의 특성어떤 수열에 대해 적절히 n개를 삭제하여 최대한 긴 증가 부분 수열을 만드는 것이므로,이..
2019. 6. 30. 16:25
# Foundation/알고리즘
동적 계획법(Dynamic Programming) 알고리즘
동적 계획법 이름의 유래수학, 컴퓨터 공학, 경제학에서 사용되는 문제풀이 방법. 리처드 벨만이 처음 이 단어를 사용했으며,그의 자서전 '태풍의 눈'에서 다음과 같이 설명했다. 어떤 문제가 다단계로 이루어져 있으며, // sub-structure시간에 대해 가변적이고, // time-varying동적이다. // dynamic 시간에 대해 가변적이라는 특성은, 특히 경제학에서 주로 다뤄지는 것 같다. 동적 계획법이란?하나의 복잡한 문제를, 동일한 구조의 간단한 문제들의 합으로 푸는 방법. 하나의 문제를, 그것과 동일한 형태의 작은 문제들로 나눈 뒤.작은 문제들을 풀어내어 최종적인 문제에 접근하는 것이 그 목적이다. 또한 어떤 문제를 푸는 도중에, 작은 문제들의 결과값이 필요하다면,작은 문제를 푸는 과정으로 ..
2019. 6. 25. 16:16
# Foundation/알고리즘
이분탐색(Binary Serach) 알고리즘
이분탐색이란?매 단계마다 탐색범위를 절반씩 줄이는 방식.현재범위를 반으로 쪼갠 뒤, 답이 존재하지 않는 쪽을 제거한다. 업 다운 게임이 대표적인 예시인데,범위가 [0, 100]인 게임에서 최소횟수로 정답을 맞추려면, 정답이 있을법한 구간의 중간값을 골라서, 매번 정답의 범위를 절반으로 줄여야 한다. UP 이라면, 작은 구간에는 답이 없으며.DN 이라면, 큰 구간에는 답이 없다. 이분탐색의 제약이분탐색의 핵심은 정답이 없는 절반을 배제하는 것 이며,배제할 구간에 정답이 없다는 것을 확신할 수 있어야 한다. 업-다운 게임에서 이분탐색을 적용할 수 있는 이유는.50의 결과가 UP일때, 50이하에는 정답이 없다고 확신할 수 있기 때문이다. 중간값과의 비교를 통해 답의 위치를 알 수 있어야 하며, 수학적으로 풀어..
2019. 5. 24. 14:38
