LIS LIS는 Longest Increasing Subsequence 의 약자로 한글로는 ‘최장 증가수열’, 또는 ‘최대 증가 부분수열’로 불린다. 이것은 어떤 수열에서 특정 부분을 지워서 만들어낼 수 있는 증가 부분수열 중 가장 긴 수열을 말하는데 이때 부분수열의 숫자들은 원 배열에서 위치가 이어져 있지 않아도 된다는 주요한 특징이 있다. 예를 들어 원 배열이 [1,4,6,8,3,5,6,7]일 때 [1,6,8], [4,6,8], [1,7]은 증가 부분수열인데, 이 중 가장 긴 부분수열은 [1,3,5,6,7]이 된다. https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작..
백트래킹 백트래킹이란 말 그대로 '되추적'의 의미를 가진다. 즉 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가서 다른 자식 노드를 찾는 방법을 의미한다. 브루트 포스 알고리즘과 다른 점은, 모든 경우의 수 중에서 가능성이 존재하지 않는다면(=더 이상 유망하지 않다면) 더이상 탐색하지 않는다는 점이다. 이를 위해서는 상태공간트리를 그려 DFS와 같은 탐색 알고리즘을 통해서 구현할 수 있다. DFS의 특징 자기 자신을 호출하는 순환형태의 알고리즘 형태를 가진다. (재귀 호출이 이루어진다) 상태공간트리에서 탐색한 노드에 대한 정보를 검사해야 한다. 상태공간트리에서 탐색할 노드가 유망한지를 검사해야 한다. 트리의 branch의 끝까지 탐색해야 다음 branch를 탐색하기 때문..
4. Mergesort 병합정렬은 divide and conquer의 방법을 사용하는 분할 정복 알고리즘이다. divide and conquer란 DP에서 설명했듯 큰 문제를 작은 문제들로 나누어 각각을 푸는 것으로, top-down approach의 방식으로 접근한다. divide and conquer의 특성을 이용하는 만큼 재귀호출을 이용한다. //pseudocode mergeSort(left, right) { if(left
정렬 알고리즘 정렬 알고리즘은 n개의 input이 주어졌을 때, 이것들을 특정한 기준을 정해(오름차순, 내림차순) 정렬하여 출력하는 알고리즘이다. 효율적인 정렬은 데이터의 정규화를 통해 정렬된 상태에서 사용 가능한 다른 알고리즘을 수행하기 위해 필요하다. 이러한 정렬 알고리즘은 여러 종류가 있으며, 그 방법에 따라 다양한 수행시간을 가진다. 대부분 O(nlgn)과 O(n^2) 사이의 시간복잡도를 가지지만, input이 특수한 성질을 만족하는 경우에는 O(n) sorting도 가능하다. 1. Selection Sort 범위 내의 최소/최대값을 선택해서 한쪽으로 열외시키는 것 반복 선택정렬은 배열을 한쪽 방향부터 정렬하는 제자리 정렬 알고리즘이다. 제자리 정렬 알고리즘이란 input에 필요한 메모리 외에 추..
피보나치 문제의 예시를 보자. 피보나치의 경우 재귀함수를 이용한 Divide-and-Conquer 방법으로 풀 수도 있지만, 재귀의 방법을 사용하면 모든 호출된 재귀함수들이 fib(1)에서부터 계산해나가야 하기 때문에 수행시간이 길다. //재귀를 사용한 피보나치, Top-down public int fibInRecursive(int n) { if(n=1) { fib[1]=1; for(int i=2; i
탐색 알고리즘 주어진 input에서 원하는 data를 찾기 위한 알고리즘. 1. Sequential search 리스트에서 저장된 데이터를 차례로 검사한다. 무작위로 저장된 리스트를 탐색할 수 있지만, 최악의 경우(리스트에 찾으려는 데이터가 존재하지 않거나, 리스트의 마지막에 데이터가 존재하는 경우) n개의 input size를 갖는 리스트를 탐색할때 O(n)의 시간복잡도를 가진다. public int seqSearch(int[] arr, int target) { for(int i=0; i
0. Analysis of Algorithms 1. Search 1-1. Sequential Search 1-2. Binary Search 1-3. Static Searching - Binary Search Tree 1-4. Dynamic Searching - B-tree 1-5. Hashing 2. Sorting 2-1. Selections Sort 2-2. Bubble Sort, Exchange Sort 2-3. Insertion Sort 2-4. Merge Sort 2-5. QuickSort 2-6. HeapSort 2-7. Counting Sort 2-8. Radix Sort 3. Matrix Multiplication - Strassen's 4. Dynamic Programming 4-1. Bi..