알고리즘 개요

원래 예정은 웹이나 안드로이드 먼저 포스팅이었지만 다음주의 면접을 위해 알고리즘부터 한번 쭉 훑으며 복습하고자 한다.

알고리즘은 흔히, '어떤 문제를 해결하기위해 명확히 정의된 유한개의 규칙과 절차의 모임' 을 의미한다. 즉 문제를 푸는 방법이다. 이에 따라 알고리즘의 공부에는 보통 자료구조의 학습이 선행되어야 한다. 

대학에 따라 과목도 자료구조론/알고리즘 으로 나눠져있기도 하지만 자료구조와 알고리즘 과 같이 묶어서 가르치는 과목도 있더라.

자료구조에는 리스트, 스택, 큐, 트리, 그래프 등이 있다.

리스트는 목록형 자료구조라 하는데 말그대로 일렬로 자료들을 이어놓은 구조이다. 그래서 보통 리스트 중에도 링크드 리스트(Linked List)를 흔히 사용한다. C에서는 포인터를 이용해 노드라 불리는 자료덩어리들을 연결시켜 구현한다. 노드는 보통 구조체 형태로 만들어서 한 노드에 여러 자료들을 저장할 수 있다.

스택은 한쪽이 막힌 관으로 표현할 수 있는 자료구조이다. 한쪽이 막혔기 때문에 데이터를 일렬로 넣었을 때, 가장 먼저 들어간 데이터가 가장 늦게 나올 수 있다. 이를 Last In First Out, LIFO라고 표현한다. 스택에 데이터를 삽입하는것을 Push, 가장 위의 데이터를 제거하는것을 Pop이라 부른다. C++에서 <Algorithm> 헤더파일에도 구현이 되어있지만 배열을 이용해 손쉽게 구현할 수 있기 때문에 나는 배열을 주로 이용하는 편이다. 스택의 데이터를 저장할 배열과 배열안에 들어있는 데이터의 갯수를 나타내는 int형 변수 하나면 스택을 표현할 수 있다. 

큐는 반대로 양쪽이 모두 뚫힌 관으로 표현할 수 있다. 즉 양 쪽 다 뚫혀있기 때문에 넣은 순서대로 그대로 나오게 된다. First In First Out ,FIFO라고 표현한다. 큐에 데이터를 넣는 것을 인큐(enqueue), 빼는 것을 디큐(dequeue)라 부른다. 이 역시 <Algorith> 헤더파일에 구현되어있는데 이 역시 배열로 구현할 수 있다. 하지만 스택을 구현하는 것 처럼 배열로 구현하면 디큐할때마다 배열의 데이터를 한칸씩 앞으로 옮기거나 아니면 아예 큐의 첫 구간을 나타내는 변수를 하나 더 만들어줘야한다. 스택보다 귀찮기 때문에 나는 알고리즘 헤더파일에 구현된 큐를 사용하는 편이다.

트리는 수학 시간에 배우는 수형도 처럼 생긴 자료구조이다. tree라는 이름 자체가 나무처럼 생겼다해서 붙여진 이름인데 실제로 사용할 땐 위아래로 뒤집어서 사용한다(?). 즉 실제로 트리 구조를 보면 나무뿌리처럼 위가 적고 아래로 갈수록 옆으로 퍼진다. 트리의 용어는 부모노드, 자식노드나 뿌리(루트), 리프,가지, 차수 등 아주 많은데 나중에 다시 설명하도록 한다. 주로 한 노드에 최대 2개까지의 자식노드를 가지는 이진트리를 이용한다. 이 트리는 정렬, 탐색, 압축 등 여러 분야에서 자주 사용된다. 

그래프는 노드에 해당하는 정점(vertex)와 이를 잇는 간선(edge)로 이루어진 자료구조이다. 이 정의에 의하면 트리도 그래프의 일종이라 할 수 있다. 그래프에 대한 세부 내용은 알고리즘에서 다시 나오기 때문에 자료구조로서의 그래프의 설명은 이정도 까지 하겠다.

위와 같이 자료구조의 학습이 끝나면 알고리즘을 배우게 된다. 알고리즘의 종류는 매우 다양한데 정렬, 탐색, 문자열, 그래프 등 이외에 많은 알고리즘이 있다.

각 알고리즘은 한 포스트에 다루기에 너무 광대해서 추후에 따로 정리할 것이다.

또한 알고리즘의 설계 기법? 이라 부를 수 있는 것들이 있다.

분할 정복은 어떠한 문제를 작은 범위의 문제로 나누어 해결하는 방법이다.

동적 계획법은 보통 영어로 DP, Dynamic Programming 이라고도 자주 부른다. 단계적으로 문제를 풀어나가는, 즉 문제의 점화식을 구해서 구현하는 방법이다.

탐욕 알고리즘, 흔히 그리디(Greedy)라고 부르는 알고리즘은 무작정 바로 보이는 상황만을 고려해서 답을 구하는 방법이다. 

백트래킹은 여러 후보 해들을 탐색하면서 잘못 되면 재귀등을 이용해 다시 전으로 가고 다른 해를 탐색하는 식으로 문제를 해결하는 방법이다. 미로찾기를 생각하면 이해하기 쉽다.

다음 알고리즘 포스팅은 내가 제일 약한 그래프 복습을 위해 그래프에 관한 내용이 될 것같다.