ongaussian

최장증가부분수열(LIS; Longest Increasing Subsequence)부분수열(subsequence)은 하나 이상 수를 지우거나 심지어 지우지 않은 모든 수열을 말한다.예를 들어 10 7 4 9 의 부분 수열에는 7 4 9, 10 4, 10 9 등이 있다. 단, 10 4 7 은 원래 수열 순서와 다르므로 10 7 4 9 의 부분 수열이 아니다. 즉 부분 수열은 원래 수열의 순서를 지켜야 한다.다음으로 증가부분수열(increasing subsequence)이란 부분수열에 포함된 숫자들이 순증가(strictly increasing)하는 부분수열이다. 순증가는 수열에서 모든 두 인접한 숫자 중 앞의 것이 항상 더 작다. 참고로 단조 증가(monotonically increasing)는 같은 경우도 ..

동적 계획법(Dynamic Programming)동적 계획법은 프로그래밍 대회 문제에 가장 자주 출현하는 디자인 패러다임이다. 이름만 가지고는 무엇을 의미하는지 알기가 어렵기 때문에 많은 오해를 불러일으키는 주제이기도 한다. 동적 계획법(Dynamic Programming)이란 말은 최적화 문제를 연구하는 수학 이론에서 왔다. 여기서 'Dynamic'은 전산학에서 일반적으로 사용하는 동적의 의미와는 아무 관련이 없다. 동적 계획법의 고안자 벨만은 Dynamic이라는 단어가 멋있어서 선택했다고 한다. 'Programming'이란 말은 최적화 연구분야에서 최적의 프로그램을 찾아낸다는 의미로 사용된다. 동적 계획법은 주어진 문제를 더 작은 부분 문제(subproblem)로 분할하여 해결한 뒤, 그 결과들을 통..

Introduction 우리는 P문제와 NP문제를 정의를 알아보았다. 2021/01/24 - [IT/Algorithms] - Class P & Class NP 간단히 다시 정리하자면 아래와 같다. P문제 - 다항시간안에 풀 수 있는 판별문제 (결정적/비결정적 알고리즘 모두) NP문제 - 비결정적 알고리즘으로 다항시간안에 풀 수 있는 판별문제 P문제는 우리에게 익숙한 결정적 알고리즘으로 해결이 가능한 문제들이다. 그리고 P문제는 비결정적 알고리즘으로도 충분히 해결이 가능한 문제이다. (결정적 알고리즘은 비결정적 알고리즘의 조금 특수한 경우) 따라서 ClassP로 분류된 문제들은 Class NP에도 포함된다. (예를 들어, 합성수 판별문제는 P문제이면서 동시에 NP문제이다.) 위 그림은 Class P와 Cl..

Introduction 계산복잡도는 알고리즘의 특성이지 우리가 풀고자 하는 문제 그 자체의 특성은 아니다. 즉 문제는 하나지만, 문제에 대해 다른 복잡도를 가지는 다수의 알고리즘이 존재할 수 있다. 효율적인 알고리즘에 찾는것에 무게를 두는 것이 아니라 문제의 본질 그 자체에 관심을 두고를 연구하는 학문이 있다. 이 학문에서는 문제들을 문제의 해결 난이도에 따라 분류하고 분류된 문제들의 특성을 연구한다. Tractable? Intractable? 계산복잡도 이론에서 문제의 난이도는 그 문제를 해결하는 빠른 알고리즘의 존재유무에 달려있다. 그리고 빠른 알고리즘은 다항시간(polynomial time)안에 답을 찾는 알고리즘을 말한다. 다항시간내에 풀 수 있는 알고리즘이 존재한다면, 해당 문제를 Tractab..

Overview 하나의 문제를 해결하는 알고리즘은 여러가지가 존재할 수 있다. 우리는 이 중에서 어떤 알고리즘이 성능이 좋고 나쁜지 평가하는 기준이 필요하다. 알고리즘 성능의 평가기준은 크게 시간(Time)과 공간(Space)이 있다. 시간은 알고리즘이 답을 내기까지 걸리는 소요시간(수행시간), 공간은 알고리즘이 사용하는 (메모리)공간을 말한다. 아쉽게도 두 기준은 서로 상충하는 경우가 많다. 메모리 사용량을 늘려 속도를 높이거나, 속도를 희생하고 메모리 사용량을 줄이는 알고리즘도 있다. 보통은 속도를 중시하는 경우가 많다. 시간복잡도(Time Complexity) 시간복잡도는 일종의 함수로 입력크기(n)에 대해서 알고리즘이 결과를 내는데 필요한 연산의 수를 나타낸다. 예를 들어, 1부터 n까지 정렬된 ..

Overview 정렬 문제는 임의의 배열이 주어졌을때, 규칙에 맞게 정렬된 배열을 만드는 문제이다. 이번 장에서 다룰 정렬 알고리즘은 Merge sort, Quick sort, Heap sort이다. Merge sort와 Quick sort는 Divide & Conquer기법을 사용하는 대표적인 정렬법으로 매우 중요하고 자주 언급된다. 합병 정렬(Merge sort) 합병 정렬(Merge sort)는 분할 정복(Divide & Conquer) 패러다임의 대표 알고리즘이다. 분할 정복 알고리즘은 보통 세 가지 구성된다. Divide, Base, Conquer가 그것 인데 합병 정렬에서 Divide는 정렬되지 않은 배열을 절반으로 나누는 작업을 한다. Base는 더 이상 나누어지지 않는 과정에 이르러 Div..

Overview 정렬 문제는 임의의 배열이 주어졌을때, 규칙에 맞게 정렬된 배열을 만드는 문제이다. 올바른 규칙이란 오름차순 또는 내림차순을 말하는데 특별히 언급이 없다면 오름차순을 올바른 규칙으로 하겠다. 이번에 다룰 정렬 알고리즘은 순서대로 Selection Sort, Insertion Sort, Bubble Sort이다. 참조한 링크 사진의 출처를 제목에 적어두었다. 이렇게 잘 정리된 자료를 공유해주어 감사를 표한다. 선택 정렬(Selection Sort) 선택 정렬은 선택 자리를 하나 정하고 그 자리에 맞는 값을 찾아 넣는 과정을 수차례 반복한다. 선택 정렬은 제자리 정렬(in-place sorting) 알고리즘으로 정렬을 위해서 추가 메모리 공간이 필요없다. 위 그림에서 회색 화살표가 바로 선택..