알고리즘 스터디 6일차

1. 기수 정렬

2. DFS

3. BFS

4. 이진 탐색

5. 그리디 알고리즘

출처

Do it! 알고리즘 코딩테스트 with Python

1. 기수 정렬

값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교

시간복잡도 : O(kn)

예시 : 일의 자리를 기준으로 데이터를 정렬 후 저장 -> 저장된 데이터를 십의 자리를 기준으로 데이터 저장 -> ... -> 최종 정렬 데이터

2. DFS (깊이 우선 탐색)

시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색

(깊이를 우선으로 시작점에서 한 쪽 방향으로 끝까지 간 후, 인접한 주변 깊이로 이동한다는 뜻)

그래프 완전 탐색, 재귀 함수로 구현, 스택 자료구조 (FILO)

시간복잡도 : O(V+E) - (노트수 : V, 엣지수 : E)

위의 그림에 DFS로 탐색하면 순서는 1-2-3-4-5 순으로 탐색하게 된다.

3. BFS (너비 우선 탐색)

가까운 노드를 먼저 방문하면서 탐색

그래프 완전 탐색, FIFO 탐색, Queue(큐) 자료구조 이용

시간복잡도 : O(V+E)

위의 그림에 BFS로 탐색하면 순서는 1-2-5-3-4 순으로 탐색하게 된다.

4. 이진 탐색

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘

(대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음)

타킷 데이터 탐색, 중앙값 비교를 통한 대상 축소 방식, (쉽고 일반적)

시간복잡도 : O(logN)

5. 그리디 알고리즘

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

3단계를 반복하면서 수행

1) 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택

2) 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에서 벗어자니 않는지 검사

3) 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사, 해결하지 못한다면 1)로 돌아가 반복

데이터람쥐