Algorithms/Algorithms

[알고리즘 기본] 완전 탐색 (브루트 포스 Brute Force)

완전 탐색, 브루트 포스(Brute Force) Brute Force 직역하면 짐승같은 힘, 무식한 힘이라는 뜻이다. 완전 탐색이라는 이름에서도 알 수 있듯이 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다. 모든 경우를 탐색하니 당연히 정답을 찾을 수 있다. 완전탐색 예시 3자리로 구성된 자물쇠의 비밀번호를 찾기 위해 000 ~ 999까지 모든 경우의 수를 입력해보는 것을 생각하면 이해하기 쉽다. 999까지 입력할 것을 생각하면 벌써부터 몸살이 난다. 왜냐? 더럽게 오래 걸리기 때문이다. (This is 경험담) 여기서 완전탐색 알고리즘의 장점과 단점을 알 수 있다. 완전탐색 장점 & 단점 장점 모든 경우를 다 고려하기 때문에 확실한 정답을 찾을 수 있다. 복잡한 알고리즘 없이 빠르게 구현이 가능..

[알고리즘 기본] 탐욕(Greedy) 알고리즘

1. 탐욕 알고리즘 (Greedy Algorithms) 탐욕(Greedy)은 말 그대로 지나치게 욕심이 많다는 뜻이다. 그렇다면 탐욕알고리즘은 무엇일까? 미래를 생각하지 않고 현재의 단계에서 가장 최선의 선택을 하는 것을 탐욕알고리즘이라고 한다. 동적프로그래밍은 간단한 프로그래밍에 사용 시 많은 단계를 거쳐 사용돼 비효율적이다. (동적프로그래밍 : 경우의 수를 모두 검토해 점화식을 통해 구성) 동적프로그래밍을 대체하는 것은 아니고 동적프로그래밍과 같이 상황에 맞게 쓰이는 것이 탐욕알고리즘이다. 2. 탐욕알고리즘의 성립 조건 탐욕적 선택 속성(Greedy Choice Property) : 탐욕적 선택이 전체 문제의 최적해를 구할 수 있다 , 앞의 선택이 다음 선택의 영향을 주지 않는다. 최적 부분 구조(O..

[알고리즘 기본] 하노이탑 알고리즘

1. 하노이탑 알고리즘 원리 하노이탑은 재귀를 이용한 대표적인 알고리즘으로 알려져 있다. 총 3개의 기둥이 존재한다. 주어진 n개의 원판을 다른 기둥으로 옮기는 것을 말한다. 이때 몇 가지 규칙들이 존재한다. 한 번에 딱 한 개의 원판만 이동할 수 있다. 옮겨진 원판은 무조건 맨 위에 올라간다. 맨 위에 있는 원판만 옮길 수 있다. 크기가 큰 원판은 작은 원판 위로 올라갈 수 없다. 하노이탑을 3번째 기둥으로 옮기는데 필요한 총횟수는 "2^n - 1" 번이다. 예를 들어 3개의 원판을 옮긴다고 생각해보자. A에 있던 3개짜리 기둥을 C로 B로 옮기는 과정이다. 우선 3번 원판을 옮기기 위해서는 위에 있던 1번과 2번 원판을 C로 옮겨야 한다. 1번 원판을 A에서 B로 이동 2번 원판을 A에서 C로 이동 ..