[알고리즘] 알고리즘에서 배워야 할 기초

알고리즘은 문제를 해결하는 순서를 의미합니다.

 

알고리즘을 수행하기 위해서는 가장 먼저 자료가 있어야 합니다.

 

이를 위해서 가장 먼저 자료구조를 배웁니다.

자료구조는 문제 해결을 위해 가장 효율적으로 자료를 조직하고 구조화하는 활동을 의미합니다.

 

자료구조는 크게 선형과, 비선형으로 나뉩니다.

선형에서는 스택, 큐, 배열, 연결리스트 등이 있습니다.

비선형 구조에서는 트리와 그래프가 있습니다.

 

 

 

 

 

자료가 저장이 되어있다면, 자료를 보기 좋게 정렬합니다.

버블정렬, 삽입정렬, 선택정렬이 가장 기본적인 정렬입니다.

좌우가 붙은 것이 버블처럼 움직인다고 해서 버블정렬이라고 이름붙였습니다.

삽입정렬은 특정 기준 점 이전에 것을 전부 비교한 뒤에 삽입한다고 해서 삽입정렬입니다.

선택정렬은 i이후에 가장 작은 것을 찾아서(선택해서) 하나씩 늘려간다고 해서 선택정렬입니다.

 

 

왼쪽이 버블정렬, 가운데가 삽입정렬, 오른쪽이 선택정렬이다.

약간 더 심화해서 퀵정렬, 병합정렬, 힙정렬을 배웁니다.

퀵정렬은 피봇이라는 기준점을 중심으로 큰 값과 작은 값을 먼저 나눈뒤, 또 다시 피봇을 중심으로 큰 값과 작은 값으로 나누는 방식으로 정렬하게 됩니다.

병합정렬은 전부 하나씩 나눈 뒤에, 2개를 비교해서 순서대로 병합하고, 4개를 비교해서 순서대로 병합하고, 8개를 순서대로 병합하는 방식으로 정렬하게 됩니다.

Heap정렬은 level 0부터 완전 이진 트리로 나눈 뒤에, 가장 끝단에 있는 값이 바로 위에있는 값과 비교해서 크면 level을 하나씩 올려가는 방식으로 정렬하게 됩니다.

 

 

 

 

자료가 정렬되었다면, 내가 원하는 값을 검색하는 알고리즘을 구현하게 됩니다.

검색에는 선형검색(Linear Search, Sequenstial Search), 제어검색(Controlled Search), 이진 트리 검색(Binary Tree Search), 해싱 검색(Hashing Search)가 있습니다.

 

 

해싱은 함수에 넣으면 특정한 값으로 변환시켜서 값을 찾아주게 하는 형태입니다.

 

 

 

검색 이후에는 특정한 문제를 위한 식을 세우는 알고리즘을 선택하게 됩니다.

기본적으로 너비우선탐색이나 깊이우선탐색 알고리즘을 배울 수 있습니다.

또 자주 나오는 알고리즘으로 최소신장비용트리가 있습니다.

최소신장비용트리는 크루스칼, 다익스트라가 있으며, 다익스트라는 DP(Dynamic Programming)의 방식으로 해결합니다.