자료구조와 밀접한 관련이 있는 "알고리즘" 은 문제를 해결하기 위한 일련의 절차를 뜻합니다. 즉, 어떤 작업을 수행하기 위해 명령어를 입력받아 결과를 출력해 내는 과정입니다. 알고리즘을 제대로 익혀야 더 효율적인 프로그램을 작성할 수 있습니다.
알고리즘을 공부할 때, 이론적인 부분도 중요하나 실제 문제들 (백준, 프로그래머스…)에서 실제로 공부하며 익히는 것이 너무나 중요합니다. 이 포스팅은 컴퓨터 공학 개론 포스팅이기에 현재 포스팅에서 다루는 정렬 알고리즘이나, 검색 알고리즘은 간단히 개념만 살펴보고 넘어가고 추후에 알고리즘 포스팅에서 더 자세하게 다뤄보겠습니다!!
01. 알고리즘 개요
1) 알고리즘 표현 방법
알고리즘은 “어떤 문제를 해결하기 위한” 일련의 절차를 공식화한 형태로 표현한 것입니다.
이러한 알고리즘울 표현하는 방법에는 "자연어", "순서도", "의사코드", "프로그래밍 언어" 등이 있습니다.
(1) 자연어
자연어는 사람이 사용하는 자연 언어를 뜻합니다. 자연어를 표현된 알고리즘은 사람에게 친숙한 언어로 구성되어 있어 쉽게 작성할 수 있으나, 명확하지 않은 표현으로 인해 오해가 발생할 수 있다는 단점도 있습니다.
(2) 순서도
순서도는 기호와 선을 이용해서 문제 핵결에 필요한 처리 과정을 표현한 방법입니다. 전체적인 구조 흐름을 파악하는 데 적합하지만, 복잡한 알고리즘의 경우 그림이 복잡해져 효과가 떨어집니다.
(3) 의사코드
의사코드는 프로그래밍 언어로 작성된 코드와 비슷한 형태로 알고리즘을 표현하는 방법입니다. 구조는 프로그래밍 언어와 비슷하나 특정 프로그래밍 언어의 문법을 따르지는 않습니다. 즉, 가짜 코드라는 의미로 의사코드라고 부릅니다.
(4) 프로그래밍 언어
프로그래밍 언어는 프로그래밍을 할 때 사용하는 언어로, 컴퓨터가 이해할 수 있는 언어입니다. 이전 포스팅에서 자세히 다뤘으므로 생략하겠습니다.
2) 알고리즘 설계
알고리즘 설계는 가장 효율적인 문제 해결 방법을 찾아내는 과정입니다. 알고리즘을 설계할 때는 문제의 현 상태와 목표가 무엇인지를 명확히 해야 합니다. 그래야 문제를 해결하기 위해서 어떠한 작업이 수행되어야 하는지 파악할 수 있기 때문입니다. 알고리즘 명령이 실행되는 순서를 결정하는 제어 구조로는 “순차 구조”, “선택 구조”, “반복 구조”가 있습니다.
- 순차 구조: 명령을 시간 순서대로 하나씩 수행하는 구조입니다.
- 선택 구조: 조건의 결과에 따라 명령을 선택해서 실행하는 구조입니다.
- 반복 구조: 같은 동작을 여러 번 반복해 수행해야 할 때 실행하는 구조입니다.
02. 알고리즘 분석
1) 알고리즘 복잡도
알고리즘이 복잡하거나 처리해야 하는 데이터가 많으면 알고리즘의 효율성이 프로그램 성능에 많은 영향을 끼치는데 분석을 통해 알고리즘의 복잡도를 알 수 있습니다. “알고리즘의 복잡도”는 해당 알고리즘이 특정 기준에 따라 얼마나 빠르고 느리게 실행되는 지를 나타내는 것입니다.
알고리즘의 효율성을 판단하는 기준은 여러 가지가 있는데, 그 중에서도 ‘CPU의 실행 시간’이 가장 중요한 평가 기준입니다. 이 기준으로 알고리즘 효율성을 측정하는 가장 좋은 방법은 “시간 복잡도”를 분석하는 것입니다.
2) 시간 복잡도
“시간 복잡도”는 알고리즘이 실행되고 종료될 때까지 어느 정도의 시간이 필요한 지를 측정하는 방법입니다. 컴퓨터의 실행 시간을 직접 측정하기 어려우므로, 알고리즘 실행문이 실행된 횟수를 파악하여 측정합니다.
3) 빅오 표기법 (Big O Notation)
”빅오 표기법”은 알고리즘의 시간 복잡도를 표현하는 방법입니다. 입력된 값의 크기에 따라 알고리즘 처리 횟수가 얼마나 증가하는지 나타낼 때 사용합니다. 입력된 데이터의 개수에 따른 알고리즘 효율성을 분석할 때, 빅오 표기법을 이용하면 알고리즘의 복잡도를 근삿값으로 나타낼 수 있습니다.
\begin{align} O(n) : \text{알고리즘의 수행 횟수가 }n\text{ 만큼 커진다.} \end{align}
\begin{align} O(n^2) : \text{알고리즘의 수행 횟수가 }n^2\text{ 만큼 커진다.} \end{align}
03. 정렬 알고리즘 (Sort)
“정렬”이란 데이터를 일정한 규칙에 따라 재배열하는 것입니다. “정렬 알고리즘”은 주어진 데이터를 정해진 순서대로 나열합니다. 기준에 따라 데이터를 정렬해 두면 이후에도 효과적으로 데이터를 사용할 수 있어 어떻게 적용하는 지가 매우 중요합니다.
대표적인 정렬 알고리즘 종류로는 “선택 정렬”, “버블 정렬”, “삽입 정렬” 등이 있습니다.
1) 선택 정렬
“선택 정렬”은 아무렇게나 놓인 데이터 중 가장 작은 데이터의 위치를 가장 앞에 있는 데이터 위치와 바꾸는 방식입니다. 데이터들 중 기준 위치에 맞는 데이터를 하나 선택하여 자리를 교환하는 방식으로 정렬합니다.
2) 버블 정렬
“버블 정렬”은 나란히 놓인 데이터 두 개 중 숫자가 큰 데이터를 뒤로 보내며 정렬하는 방식입니다. 왼쪽에 놓인 데이터에서부터 시작하며, 크기 순으로 자리를 서로 바꿉니다.
3) 삽입 정렬
“삽입 정렬”은 아직 정렬되지 않은 데이터를 이미 정렬된 부분 중 한 곳에 삽입하여 정렬하는 방식입니다. 해당 데이터가 들어갈 적절한 위치를 찾아 주는 것입니다.
04. 검색 알고리즘 (Search)
“검색”이란 특정 데이터 집합에서 어떤 조건이나 성질을 만족하는 데이터를 찾는 것입니다. “검색 알고리즘”은 데이터를 추가하거나 삭제하고 싶을 떄, 해당 데이터가 이미 있는지 찾아보고 싶을 때 아주 유용합니다.
대표적인 검색 알고리즘 종류로는 “순차 검색”, “이진 검색”, “해싱” 등이 있습니다.
1) 순차 검색
“순차 검색”은 일렬로 나열된 데이터를 처음부터 끝까지 순서대로 검색하는 방법입니다. 가장 간단하고 직접적인 방법이라 구현하기 쉬운 알고리즘입니다. 배열이나 연결 리스트로 구현된 선형 자료구조에서 자주 쓰이는 방법입니다. 순서대로 데이터를 비교하며 원하는 항목을 찾는데, 이때 검색해야 하는 자료의 양에 따라서 효율이 달라지게 됩니다. 또한, 검색해야 할 데이터가 정렬이 된 상태인지 아닌지에 따라서 검색 실패를 판단하는 시점도 달라집니다.
2) 이진 검색
“이진 검색”은 데이터 가운데에 위치한 항목을 검색 값과 비교해서 검색 값이 더 크면 ‘오른쪽 부분’을 검색하고, 검색 값이 더 작으면 ‘왼쪽 부분’을 검색하는 방법입니다. 정렬된 데이터에서만 사용할 수 있으며, 굉장히 효율적인 방식입니다. 원하는 값을 찾을 때까지 검색 범위를 계속 줄여 가며 빠르게 반복 수행하며, 검색 대상인 데이터 개수를 평균 1/2씩 줄이기 때문에 데이터 양이 많을 때 활용하면 매우 빠른 속도로 결과를 얻을 수 있다는 장점이 있습니다.
3) 해싱
“해싱”은 산술적인 연산을 이용해 키가 있는 위치를 계산하고, 그 위치를 바로 찾아갑니다. 키 값을 데이터 위치로 변환하는 함수를 “해시 함수”라고 하며, 해시 함수에 따라 계산된 주소 위치에 항목을 저장한 표를 “해시 테이블”이라고 합니다.
해시 함수는 문자열을 ‘위치를 파악할 수 있는 숫자 값’으로 바꾸는 역할을 합니다. 검색해야 할 키 값을 입력받아 “해시 주소”를 만들고 이 해시 주소가 해시 테이블의 인덱스로 사용됩니다.
이처럼 해싱은 인덱스를 이용하여 원하는 항목에 접근할 수 있습니다. 즉, 인덱스의 번호만 알면 어떤 항목이든 동일한 시간 안에 접근할 수 있다는 것입니다. 그렇기에 해싱은 검색, 삽입, 삭제 등의 연산을 효율적으로 수행할 수 있습니다.
