[알고리즘] 알고리즘 종류 및 시간복잡도 정리

알고리즘(Algorithm) 이란?

"문제를 해결하는 방법" 이다.

특히, 컴퓨터에서 알고리즘이란 거의 안 쓰이는 곳이 없을 정도로 널리 이용되고 있다.

알고리즘의 개념

어떠한 Input 데이터가 주어지면 이것을 사용하기 편하게 문제를 해결한 형태의 Output을 만든다.

여기서 계속 문제를 해결한다고 하는데, 컴퓨터에서 알고리즘을 사용하는 이유는 대개 다음과 같은 이유로 사용하게 된다.

1. 자료구조 - 정렬, 탐색, 트리, 힙
2. 트리구조 - DFS, BFS
3. 그래프 - 최단거리
4. 정수론, 난수발생, 해석기하, 그래픽 등.

대부분의 경우 "자료구조"와 관련된 알고리즘이 직접적으로 사용할 일이 많아서 주로 쓰게 된다.

간단하게 하나 하나 정리해보면

1. 자료구조(Data Structure)

"정렬"에 관련된 알고리즘이 가득하다.

데이터를 왜 정렬하는가? 라는 문제에 대해 생각해볼 필요가 있다. 그대로 사용해도 되는 데이터를 정렬할 필요가 있을까? 의문을 품고 접근해본다면

"효율성" 이라는 측면에서 정렬을 사용해야 할 필요가 있다고 볼 수 있다.

예를 들어 한 통신사의 고객수가 1200만인데, 이 때 정렬을 하지 않은 상태로 데이터가 무수히 분포 되어 있다고 했을 때, 원하는 데이터를 쉽게 찾을 수 있을까?

또한 그 때 걸리는 시간은 어떻게 될 것인가?

1200만이 정렬이 안 되어 있다고 가정했을 때, 사용할 수 있는 탐색은 "순차 탐색" 일 것이다. 말 그대로 1200만개 다 찾아보는 것이다.

비록 혼자 간간히 코딩할 때는 별로 데이터가 없으니 순차탐색을 하던 어떤 탐색을 하던 별 체감이 안 들겠지만, 저렇게 극단적일 경우엔 결과 또한 극단적일 수 있다.

사내 시스템을 이용하는 직원들이 고객 정보 조회를 하려면 매번 순차탐색을 해야하는데, 그 직원 하나만 있는게 아닌만큼 서버&데이터베이스의 부담이 심각해질 수 밖에 없다.

이렇게 어떤 데이터가 어느정도 쌓이고 특히, "탐색"을 할 필요가 많은 데이터가 있다고 했을 때 정렬을 통해서 데이터를 정렬해둔다면 확실히 빠른 탐색이 가능해진다.

정렬은 크게 쓰이는 두 가지 방법이 있다.

• 오름차순 정렬(ASC)
• 내림차순 정렬(DESC)

이 방식 또한 말 그대로 데이터를 작은 것->큰 것 순서대로 오름차순으로 하는 방법과 큰 것-> 작은 것 순서대로 내림차순으로 하는 방법이 존재한다.

정렬 알고리즘은 따로 포스팅 해야할 정도로 양이 많다. + 탐색 알고리즘 약간

2. 트리구조

트리구조에서 어떤 알고리즘이 적용될까? 라는 생각을 할 텐데, "탐색" 범주에 관련된 알고리즘이 두 가지 있다.

• DFS : 깊이 우선 탐색(Depth First Search)
• BFS : 너비 우선 탐색(Breath First Search)

트리는 차수(Degree)라는 개념을 가지고 있는데, 트리가 깊어질 수록 이 차수가 깊어지게 된다.

또한 트리가 양 옆으로 자식노드들을 많이 가지게 되면 양 옆으로 넓이가 넓어지게 된다.

이럴 때, 찾고자 하는 특정 노드를 검색하려 할 때 어떻게 탐색을 할 것인가에 대한 방법이다.

BFS(너비 우선 탐섁)

너비 우선 탐색은 가로, 세로가 있다고 했을 때 가로를 기준으로 탐색하는 알고리즘이라 보면 편하다.

위 그림처럼, 여러 노드들이 있을 때 왼쪽에서 오른쪽으로 가면서 찾고자 하는 노드를 탐색한다.

DFS(깊이 우선 탐색)

반대로 깊이 우선 탐색은 가로, 세로가 있다고 했을 때 세로를 기준으로 탐색하는 방법이다.

한 자식 노드를 잡고, 맨 밑까지 내려가서 해가 있나 뒤져보는 방식이다.

대개 두 방식의 차이는

DFS : 메모리 사용 적음, 속도 빠름, 최적의 해 찾지 못함

BFS : 메모리 사용 큼, 속도 느림, 최적의 해 찾을 수 있음

이런식으로 알려져있다. 최적의 해란 기준은 "깊이가 최소"인 노드에서 해를 찾는 방법을 뜻한다.

너비 우선 탐색으로 탐색할 때, 깊이가 얕은 곳부터 깊은곳까지 탐색하는 방식이므로 해가 얕은 곳(차수가 낮은곳)에 있을 때 알아차릴 수 있다.

하지만, 깊이 우선 탐색은 맨 밑까지 내려갔다 올라오는 방법을 사용하므로, 그 해를 알기 전까지 오래 걸릴 수 있고

혹은 맨 밑에 있는 비슷한 해를 찾을 수도 있으므로 최적의 해를 구할 수 없다고 말한다.

메모리 사용과 속도의 개념은 최근 컴퓨터의 발전에 따라 크게 문제가 되지 않는 부분이다.

이 두 알고리즘을 혼합한 Iterative Deepning 등의 여러 알고리즘 등이 있는데 이는 인공지능 분야라 추후에 알아볼 일이 있으면 다시 포스팅 해야겠다.

3. 그래프

매우, 매우매우 매우 게임에 사용하기 적합한 알고리즘이다.

최단거리를 탐색하는 것은 여러 곳에서 사용하고 있다.

예를 들어 스타크래프트에서 유닛을 선택하고 맵 특정 부분에 우클릭을 하면 유닛이 거기로 이동한다.

어떻게 이동할까??? 라는 의문을 가지고 이 그래프 알고리즘을 본다면 아하! 하고 이해할 수 있다.

어쩌다보니 예시를 스타크래프트로 잡았는데, 이는 모든 온라인게임이나 경로 탐색을 하는 게임에 적용되어 사용될 수 있다

(효율성 측면에서 사용하는 알고리즘이 달라질 뿐, 이론은 똑같다)

그래프 알고리즘(?)

예를 들어 위와 같이 맵이 있다고 가정했을 때 좌측 상단의 히드라가 우측 하단의 드론에게 접근하는 경로를 알아야 할 것이다.

이럴 때 그래프 탐색 알고리즘을 사용하면 된다.

스타크래프트의 맵 또한 무수히 작은 조각으로 이뤄진 그래프로 이루어져있다고 생각하면 편하다.

그 중 한가지 알고리즘이 유명한데 얼핏 들어봤을 수도 있는 "다익스트라 알고리즘" 이다.

그래프 출처 : 나무위키

다익스트라 알고리즘은 이런 식으로 주변 그래프와의 가중치(낮을 수록 짧은 거리)를 판단하여 가장 최단거리를 구하는 알고리즘인데,

위와 같은 행렬과 동일한 맥락이다.

처음 노드를 기준으로 주변의 노드들을 확장하면서 각 노드 간 거리의 최소값을 계속 갱신하는 알고리즘이다.

이렇게 조사된 최단거리를 기준으로 탐색하고자 하는 노드까지의 거리를 계산하여 돌려준다.

시간복잡도가 매우 느려서 실시간 게임에는 이보다 발전된 방식인 우선순위 큐를 이용한 다익스트라 알고리즘이나, A* 탐색등이 사용된다.

4. 정수론, 난수발생, 해석기하, 그래픽 등.

사실 이분야는 거의 논문 연구 주제가 되므로 내가 알지 못하는 분야이므로 과감하게 생략(?) 한다.