알고리즘이란?

코딩하는 포로리·2022년 2월 28일

algorithm

Algorithm

목록 보기

1/1

📌 1. 알고리즘(Algorithm)

📎 알고리즘이란?

어떠한 문제를 해결하기 위한 일련의 절차나 방법을 공식화한 형태로 표현한 것을 의미한다.

👉 예시

집에서 학교로 가는 길 찾기
된장찌개 만드는 법
물건 구매하는 방법

📎 알고리즘의 조건

👉 입력: 외부에서 제공되는 자료가 0개 이상 있어야 한다.

👉 출력: 적어도 2개 이상의 서로 다른 결과를 내어야 한다. 즉, 모든 입력에 하나의 출력이 나오면 안된다.

👉 명확성: 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.

👉 유한성: 유한번의 명령어를 수행 후 유한 시간 내에 종료한다.

👉 효율성: 모든 과정은 명백하게 실행(검증 가능)한 것이어야 한다.

📎 좋은 알고리즘의 분석 기준

👉 정확성: 적당한 입력에 대해서 유한 시간 내에 올바른 답을 산출하는가를 판단한다.

👉 작업량: 전체 알고리즘에서 수행되는 가장 중요한 연산들만으로 작업량을 측정한다.

👉 기억 장소 사용량: 기억 장소 사용량은 메모리 사용량의 뜻으로, 수행에 필요한 저장공간을 가능한 최소화했는가를 판단한다.

👉 최적성: 그 알고리즘보다 더 적은 연산을 수행하는 알고리즘이 없어야 한다.

📎 코딩 테스트 관련 알고리즘 분류

👉 알고리즘

👉 시간/공간 복잡도

👉 점화식과 표기법

👉 in-place와 stable

👉 재귀 함수와 분할 정복

👉 정렬 알고리즘

선택 정렬
삽입 정렬
버블 정렬
계수 정렬
병합 정렬
퀵 정렬
기수 정렬
힙 정렬

👉 탐색/검색 알고리즘

BST
AVL와 Red-Black Tree

👉 DFS/BFS

깊이 우선탐색(DFS)과 백트래킹
너비우선탐색(BFS)

👉 그래프 관련 알고리즘

최소 신장 트리(MST) 관련 알고리즘
- 크루스칼
- 프림
최단 경로 관련 알고리즘
- 다익스트라
- 벨만-포드
- A* (에이스타)
- 플로이드-와샬
기타
- 위상정렬
- Union & Find
- 강연결요소

👉 동적계획법(DP)

👉 탐욕법(Greedy)

👉 문자열 관련 알고리즘

문자열 매칭
- 라빈-카프
- KMP
- 보이어-무어

📌 2. 시간 복잡도와 공간 복잡도

📎 알고리즘 계산 복잡도

알고리즘 계산 복잡도는 시간 복잡도와 공간 복잡도로 평가된다. 따라서 좋은 알고리즘은 실행 기간도 짧고, 저장 공간도 적게 쓰는 알고리즘이다.

하지만 2가지 모두 만족시키기는 어렵다. 시간과 공간은 반비례적하는 경향이 있으며, 최근 대용량 시스템이 보편화되면서 공간 복잡도보다는 시간 복잡도가 우선이기 때문이다.

그래서 알고리즘은 시간 복잡도가 중심이된다.

📎 공간 복잡도(Space Complexity)

공간복잡도란 프로그램의 성능을 분석하는 방법 중 하나로, 얼마나 저장공간(메모리)를 차지하느냐를 분석하는 방법이다. 하지만 최근에는 컴퓨터 성능의 발달로인해 메모리의 여유 공간이 충분하기 때문에 공간복잡도의 중요성이 많이 줄어들었다.

📎 시간 복잡도(Time Complexity)

시간복잡도란 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 의미한다. 같은 결과를 가져오는 프로그래밍 소스도 어떻게 작성하느냐에 따라 걸리는 시간이 달라질 수 잇다. 같은 결과를 나타내는 소스 중 가장 시간이 적게 걸리는 소스가 가장 좋은 소스라고 볼 수 있다.

📎 시간 복잡도를 표기하는 방법

알고리즘 분석 시, 평균성능과 최악의 성능이 가장 많이 활용된다. 하지만 평균을 구하는 세타 표기법이 가장 정확한 것에 비해 알고리즘이 복잡해질수록 평가하기가 어려워서 최악을 구하는 빅오 표기법을 가장 많이 사용한다.

👉 Big-O(빅-오): 최악의 입력을 한 상태에서 작업 완료까지 가장 느린 시간을 측정
👉 Big-Ω(빅-오메가): 최적의 입력을 한 상태에서 작업을 완료하는데 가장 빠른 시간을 측정
👉 Big-θ(빅-세타): 여러가지 다른 경우의 수를 입력하여, 총실행시간을 계산하고 시행횟수로 나눠서 평균을 측정