알고리즘

정렬 알고리즘

 

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어가 매우 간단
삽입 정렬	O(N^2)	O(N)	데이터가 거의 정렬되어 있을 때는 가장 빠름
퀵 정렬	O(NlogN)	O(N)	대부분의 경우에 가장 적합하며, 충분히 빠름
계수 정렬	O(N+K) (K는 데이터 중에서 가장 큰 양수)	O(N+K) (K는 데이터 중에서 가장 큰 양수)	데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만, 매우 빠르게 동작

 

 

정렬 알고리즘	핵심 아이디어
선택 정렬	가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법
삽입 정렬	데이터를 앞에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법
퀵 정렬	기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
계수 정렬	특정한 값을 가지는 데이터의 개수를 '카운트'하는 방법

 

• 파이썬의 표준 라이브러리에서 기존제공하는 sort(), sorted()는 최악의 경우에도 시간 복잡도 O(NlogN) 보장
• 크루스칼 알고리즘은 간선의 정보를 정렬하는 과정이 반드시 필요

---

이진탐색 - bisect()

---

다이나믹 프로그래밍 

한 번 해결된 부분 문제의 정답을 메모리에 기록(Memoization)하고, 한 번 계산한 답은 다시 계산하지 않음

-> 점화식을 그대로 코드로 옮겨서 구현할 수 있다. 예) 피보나치 수열 점화식

 

• 탑다운 방식 : 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출
• 바텀업 방식 : 단순 반복문을 이용하여 작은 문제를 먼저 해결하고, 해결된 작은 문제를 모아 큰 문제를 해결

---

 

최단 경로 알고리즘

 

알고리즘 종류	시간 복잡도	구현 난이도	역할
다익스트라	O(ElogV)	어려운 편	한 지점에서 다른 모든 지점까지의 최단 경로를 계산
플로이드 워셜	O(V^3)	쉬운 편	모든 지점에서 다른 모든 지점까지의 최단 경로를 계산

 

• 다익스트라 : 그리디의 일종. 단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택한 뒤에, 그 노드를 거쳐 가는 경우를 확인하여 최단 거리를 갱신 -> 우선순위 큐를 이용
• 플로이드 워셜 : 다이나믹 프로그래밍을 이용, 단계마다 '거쳐 가는 노드'를 기준으로ㅡ 최단 거리 테이블을 갱신하는 방식으로 동작

플로이드 워셜 점화식

---

그래프 이론 

• 서로소 집합 : 서로소 집합 알고리즘 -> union-find 연산. 모든 노드는 자신이 속한 집합을 찾을 때 루트 노드를 재귀적으로 찾음
• 신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하는 부분 그래프를 의미 ex) 모든 섬을 이용해 연결하는 문제
• 크루스칼 알고리즘 : 최소 비용의 신장 트리 찾기 O(ElogE). 간선을 정렬한 뒤에 간선의 비용이 작은 순서대로 최소 신장 트리를 만들어 가는 그리디 알고리즘 
• 위상 정렬 알고리즘 : 방향 그래프의 모든 노드들을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 기법. 시간 복잡도는 O(V+E)

---

구현

• 완전 탐색 : 모든 경우의 수 다 계산 -> 반복문, 재귀함수+ 예외 케이스 -> DFS/BFS
• 시뮬레이션 : 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮김
• 문자열 처리
• 소스코드 많은 문제

 

원소를 나열하는 모든 경우의 수를 고려 -> 순열, 조합 라이브러리 사용 -> itertools 라이브러리 사용