소웨공
알고리즘 개념 - 그리디, 구현, DFS, BFS, (선택/삽입/퀵/계수)정렬, 탐색, DP
애라니라니
2023. 6. 9. 11:30
- 2023.06.09
알고리즘 개념 정리
- 그리디
- 구현
- DFS
- BFS
- 선택정렬
- 삽입정렬
- 퀵정렬
- 계수정렬
- 탐색
- DP
그리디 알고리즘 (Greedy Algorithm)
▷ 탐욕법, 다음을 생각하지 않고 현재 단계에서 당장 좋은 것만 고르는 방법
- 탐욕적 선택 속성에 용이
=> 탐욕적 선택이 항상 안전하다는 것이 보장됨 - 최적 부분 구조 특성을 가지는 문제 해결에 용이
=> 부분 최적 값이 모여 전체 최적 값을 구할 수 있는 경우
아래의 사진과 같이 학교와 집의 최단 경로 + 집과 편의점의 최단 경로 = 학교와 편의점의 최단 경로
구현 알고리즘 (Implemetation Algorithm)
▷ 알고리즘을 소스코드로 바꾸는 과정
- 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
=> 완전 탐색, 시뮬레이션 문제 유형
DFS 알고리즘 (Depth-First Serach Algorithm)
▷ 깊이 우선 탐색 : 그래프의 깊은 부분을 우선적으로 탐색
- 모든 노드를 방문 하고자 하는 경우에 사용
- DFS가 BFS보다 좀 더 간단하지만, 검색 속도 자체는 느림
▷ 특징
- 자기 자신을 호출하는 순환 알고리즘 형태
- 어떤 노드를 방문했는지 여부를 반드시 검사 해야 한다 => 무한루프에 빠질 위험 O
▷ 과정
- a 노드를 방문 (방문한 노드는 표시)
- a와 인접한 노드를 차례로 순회 => 인접한 노드 없을 시 종료
- a와 이웃한 b를 방문 : a와 인접한 또 다른 노드를 방문하기 전 b의 이웃 노드들을 전부 방문
- b의 분기를 전부 탐색 했다면 a와 인접한 노드 중 방문하지 않은 노드 방문
=> b를 완벽하게 탐색해야 a의 이웃 노드 방문 가능
=> 방문하지 않은 노드가 없을 시 종료
=> 있다면 그 정점을 시작으로 DFS 다시 시작
BFS 알고리즘 (Breadth-First Search Algorithm)
▷ 너비 우선 탐색 : 루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법
- 두 노드 사이의 최단 경로
- 임의의 경로 찾을 때 사용
▷ 특징
- 직관적이지 않음
- 재귀적으로 동작하지 않음
- 어떤 노드를 방문했는지 여부를 반드시 검사 해야 한다 => 무한 루프에 빠질 위험 O
- 큐 사용 => 선입선출 원칙
▷ 과정
- a 노드를 방문
=> 큐에 방문된 노드 삽입 - 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문
=> 큐에서 꺼낸 노드를 방문
=> 꺼낸 노드와 인접한 노드 방문 : 인접한 노드가 없을 시 큐의 앞에서 노드를 꺼냄
=> 큐에 방문된 노드 삽입 - 큐가 소진될 때까지 반복
선택정렬 (Selection sort)
▷ 제자리 정렬 알고리즘의 하나, 정렬되지 않은 값들 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법
▷ 특징
- 자료 이동 횟수가 미리 결정됨
- 안정성을 만족하지 않음
=> 값이 같은 레코드가 있는 경우에 상대적인 위치가 변결될 수 있음
▷ 과정
- 주어진 배열 중에서 최솟값을 찾기
- 찾은 최솟값을 맨 앞의 위치와 교체
- 맨 앞의 위치를 뺀 나머지 배열을 같은 방법으로 교체
- 하나의 원소만 남을 때까지 1~3과정 반복
삽입 정렬 (Insertion sort)
▷ 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교, 자신의 위치를 삽입함
▷ 특징
- 안정한 정렬 방법
- 레코드의 수가 적을 경우, 알고리즘 자체가 매우 간단함
- 대부분 위 레코드가 이미 정렬되어 있는 경우에 효율적
- 비교적 많은 레코드들의 이동을 포함
- 레코드 수가 많고 레코드 크기가 클 경우 적합하지 않음
▷ 과정
- 처음 key 값은 두 번째 값.
- 그 앞쪽의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮김 -> 자료 삽입
- key 값을 두 번째, 세 번째 …로 옮겨가면서 반복
퀵정렬 (Quick sort)
▷ 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
=> 분할 (Divide) / 정복 (Conquer) / 결합 (Combine)
▷ 특징
- 속도가 빠르다
- 추가 메모리 공간을 필요로 하지 않는다
- 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 오래 걸린다
- 불균형 분할 방지 => 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택
▷ 과정
- 리스트 안에 있는 한 요소 선택 => 피벗
- 피벗을 기준으로 피벗보다 작은 요소들은 모두 왼쪽으로, 큰 요소는 오른쪽으로 옮긴다
- 피벗을 제외한 왼쪽 / 오른쪽 리스트를 다시 정렬 => 순환 호출
- 불가능할 때까지 반복
계수정렬 (Countiong sort)
▷ 배열 내에 특정한 값이 몇번 등장했는지에 따라 정렬 수행 => 비교 정렬 X
▷ 특징
- 데이터 범위가 작을 때는 O(n)의 시간 복잡도를 가지므로 매우 빠름
- 데이터 범위가 크면 만들어야 하는 배열의크기가 크므로 메모리 낭비가 심함
▷ 과정
- 배열 A의 요소값들의 등장횟수를 저장할 배열 B와 최종적으로 정렬된 값을 받을 배열 C 준비
- 값을 하나씩 꺼내 해당 값을 배열 B의 인덱스로 사용해 B의 요소 값을 하나 증가
- B 완성 시 B의 각 요소들을 누적합으로 갱신
- A의 맨 뒤부터 값을 꺼내 해당 값을 B 인덱스로 사용, 참조된 B의 값을 배열 C 인덱스로 사용해 C에 삽입
- 사용된 B의 값을 하나 감소
- A의 모든 요소에 대해 4, 5번 반복
탐색 알고리즘 (Searching Algorithm)
▷ 여러 개의 자료 중 원하는 자료를 찾는 작업
- 순차 탐색 (Sequential Search)
- 이진 탐색 (Binary Search)
- 색인 순차 탐색 (Indexed Sequential Search)
- 보간 탐색 (Interpolation Search)
▷ 순차 탐색
: 정렬되지 않은 리스트의 항목들을 처음부터 마지막까지 하나씩 순차대로 검사하여 원하는 항목을 탐색하는 방법
- 단방향 = 선형 탐색 (Linear Search)
- 탐색값과 일치하는 항목을 찾으면 그 항목의 인덱스를 반환하고, 일치하지 않는 경우 -1을 반환함
▷ 이진 탐색
: 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘
- 배열의 중간에 있는 임의의 값을 선택하여 탐색값과 비교
- 탐색값 > 중간값 => 오른쪽 데이터들 / 탐색값 < 중간값 => 왼쪽 데이터들 상대로 반복
DP (Dynamic Programming)
▷ 동적 계획법 : 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용
▷ 조건
- Overlapping Subproblems (겹치는 부분 문제)
- Optimal Substructure (최적 부분 구조)
▷ 과정
- DP 조건 파악
- 문제의 변수 파악
- 변수 간 관계식 만들기 (점화식)
- 메모하기 (memoization or tabulation)
- 기저 상태 파악
- 구현
▷ 구현
- Bottom-up (Tabulation 방식) => 반복문
: 아래에서 부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식
Tabulation => dp[0]부터 하나 하나씩 채우는 과정 "table-filling" - Top-Down (Memoization 방식) => 재귀
: 위에서부터 바로 호출을 시작
dp[0]의 기저 상테에서 출발하는 대신 dp[0] 상태까지 내려간 다음 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
Memoization => 가장 최근 값을 메모해 두어서 사용