suyeonme

동적 계획법(Dynamic Programming, DP)이란? 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. -- 위키피디아 동적 계획법의 특징 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장(memoization)하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유..

너비 우선 탐색(Breath-first-search, BFS) 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하여 그래프를 순회한다. 시작 정점을 방문한 뒤, 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문하는식으로 깊이를 더해가며 해당 깊이에 있는 모든 정점을 방문하며 나아가다가 더 이상 방문할 정점이 없을 때 탐색을 종료한다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 큐(queue)를 사용하여 구현한다. (방문한 노드들을 차례로 저장한 후 꺼낸다.) 너비 우선 탐색의 동작 방식 루트 노드를 방문한다. 큐에 방문된 노드를 삽입(enqueue)한다. 초기 상태의 큐에는 시작 노드만이 저장된다. 큐에서 꺼낸 노드..

탐욕 알고리즘(Greedy Algorithm)이란? 선택의 순간마다 당장 눈 앞에 보이는 최적의 해답(local optional solution)을 찾으며, 이를 바탕으로 최종 문제의 해답(global optional solution)에 도달하는 방법이다. 매 순간의 선택은 지역적으로는 최적의 해답이지만, 그 선택들을 반복하여 얻은 최종적인 해답이 최적이라는 보장은 없다. 항상 최적의 해답을 찾는 것은 아니지만, 최적에 근사한 값을 빠르게 찾을 수 있다. 따라서 근사 알고리즘(approximation algorithm)으로 사용할 수 있다. 동적 계획법보다 효율적이지만, 동적 계획법처럼 반드시 최적의 해를 구한다는 보장을 하지 못한다. 탐욕 알고리즘 조건 아래 두가지 조건을 만족하는 경우, 탐욕 알고리즘..

1. KMP(Knuth–Morris–Pratt) 알고리즘이란? 텍스트와 패턴 사이에 겹치는 부분을 찾아내 검사를 다시 시작할 위치를 구하여 패턴을 한번에 많이 옮기는 알고리즘이다. "몇번째 문자부터 다시 검색할지"에 대한 값을 미리 표로 만들어 검사를 시작할 위치를 구한다. 즉 패턴과 텍스트가 불일치할 경우, 그 전에 검사했던 텍스트의 문자를 표에 작성하여 불필요한 검사는 생략한다. 시간 복잡도는 O(n)이다. 2. 동작 방식 skip[]은 패턴에서 접두사(prefix)와 접미사(suffix)가 일치하는 최대 길이를 저장하는 배열이다. 접두사와 접미사가 일치하지 않으면, 접미사를 가리키는 인덱스를 1 증가한다. 접두사와 접미사가 일치하면, 접두사를 가리키는 인덱스와 접미사를 가리키는 인덱스를 1 증가한다..

1. 보이어-무어(Boyer-Moore) 알고리즘이란? 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하며 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정하는 알고리즘이다. 시간 복잡도는 O(n/m)으로 매우 빠르다.(n은 텍스트의 길이, m은 패턴의 길이) 2. 동작 방식 문자열 탐색은 패턴의 맨 마지막 글자부터 시작한다. 2.1 Bad Character 패턴의 현재 문자와 일치하지 않는 텍스트의 문자 (패턴: 찾을 문자열, 텍스트: 탐색을 수행할 문자열) Bad Character가 패턴에 존재하는 경우와 패턴에 존재하지 않는 경우를 나누어 접근한다. Bad Character가 패턴에 존재하는 경우 인덱스 2에서 불일치 발생 (C는 bad character) C는 패턴에 존재한다..

1. 브루트-포스법(Brute force method)이란? 선형 검색을 확장한 단순한 알고리즘이다. 효율이 좋지 않다. 2. 구현하기 public class BruteForceMethod { static int bruteForceMethod(String text, String pattern) { int textIdx = 0; int patternIdx = 0; while(textIdx != text.length() && patternIdx != pattern.length()) { if(text.charAt(textIdx) == pattern.charAt(patternIdx)) { textIdx++; patternIdx++; } else { textIdx = textIdx - patternIdx + 1;..

1. 도수 정렬(Counting Sort)이란? 요소의 대소 관계를 판단하지 않고 (다른 정렬 알고리즘들은 두 요소의 키 값을 비교해야 한다.) 단순하게 크기를 기준으로 세는 알고리즘이다. 데이터를 비교, 교환하는 작업이 없고 다중 for문이 아닌 단순 for문을 사용하고 재귀 호출과 중첩 for문이 없기 때문에 아주 효율적이다. 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고있을 경우, 즉 범위 조건(e.g. 5이하 자연수를 오름차순 정렬)이 있는 경우에만 사용할 수 있다. 각 단계의 for문에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값의 순서가 바뀌는 일이 없다. 따라서 안정적인 정렬 알고리즘이다. 시간 복잡도는 O(n)으로 매우 빠르다. 2. 동작 방식 총 4단..

1. 힙 정렬(Heap Sort)이란? 힙(heap)을 사용하여 가장 큰 값이 루트에 위치 하는 특징을 이용하는 정렬 알고리즘이다. 선택 정렬(selection sort)을 응용한 알고리즘이다. (선택 정렬은 아직 정렬되지 않은 부분의 모든 요소를 대상으로 가장 큰 값을 선택한다.) 시간 복잡도는 O(n log n)이다. 1.1 힙(heap)이란? 부못값이 자식값보다 항상 크다(부못값 >= 자식값)라는 조건을 만족하는 완전 이진 트리이다. (완전: 부모는 자식을 왼쪽부터 추가하는 모양을 유지 + 이진: 부모가 가질 수 있는 자식의 개수는 최대 2개) 트리의 최상단 노드를 루트(root), 트리의 최하단 노드를 리프(leaf), 노드의 상하 관계를 부모(parent)와 자식(child), 자식간의 관계를 ..