23.02.15

기수 정렬(radix sort) 은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 자릿수를 정한 다음 당당 자릿수만 비교한다.
기수 정으의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터 자릿수를 말한다.

기수정렬 핵심
기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다.
대상 데이터 16 80 18 77 03 24 88 23
일의 자릿수 기준으로 데이터 저장
0 1 2 3 4 5 6 7 8 9
80 03,23 24 16 77 88,18

--> 80 03 23 24 16 77 18 88
일의 자리에서 정렬된 순서 기준으로 십의 자리에 저장하는것이 중요

기수 정렬은 시간 복잡도가 가장 짧은 정렬이다. 만약 코딩테스트에서 정렬해야하는 데이터의 개수가 너무 많으면 기수 정렬 알고리즘을 활용해보자.

수 정렬하기3
10989번
1번 줄에 수의 개수
2번째 줄 부터 N개의 줄에 숫자가 주어진다.

input
11
215
15
344
372
294
100
8
145
24
198
831

import sys
input = sys.stdin.readline

n = int(input())
count = [0] * 10001
arr = [0]*n

for i in range(n):
    # arr[i] = int(input())
    count[int(input())] +=1

for i in range(10001):
    if count[i] != 0:
        for _ in range(count[i]):
            print(i)

---

깊이 우선 탐색(DFS)은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이 까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.
깊이 우선 탐색
기능 : 그래프 완전 탐색
특징 : 재귀 함수로 구현, 스택 자료구조 이용
시간 복잡도 : O(V+E)

깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로우에 유의해야한다. 깊이 우선탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 차기, 사이클 찾기, 위상 정렬 등이 있다.

깊이 우선 탐색의 핵심 이론
DFS는 한번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 리스트가 필요하며, 그래프는 인접 리스트로 표현하겠다.
그리고 DFS의 탐색 방식은 후입 선출 특성을 가지므로 스택을 사용한다.

1. DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기
   DFS를 위해 필요한 초기 작업은 인접 리스트로 그래프 표현하기, 방문 리스트 초기화하기, 시작 노드 스택에 삽입하기이다. 스택에 시작 노드를 1로 삽입할 때 해당 위치의 방문 리스트를 체크하면 T,F,F,F,F,F가 된다.

2. 스택에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 스택에 삽입하기
   이제 pop을 수행하여 노드를 꺼낸다. 꺼낸 도느를 탐색 순서에 기입하고 인접 리스트의 인접 노드를 스택에 삽입하여 방문 리스트를 체크한다. 방문 리스트는 T,T,T,F,F,F가 된다.

3. 스택 자료구조에 값이 없을 떄 까지 반복하기
   앞선 과정을 스택 자료구조에 값이 없을 떄 까지 반복한다. 이때 이미 다녀간 노드는 방문리스트 바탕으로 재 삽입 하지 않는것이 핵심

---

연결 요소의 개수 구하기
11724번
DFS 호출 횟수 = 연결 요소의 개수

방향 없는 그래프가 주어졌을 때 연결 요소 connected component 개수를 구하는 프로그램을 작성하시오.
1번째 줄에 노드의 개수 n, 에지의 개수 m
2번째 줄부터 m개의 줄에 에지의 양 끝점 u,v가 주어진다.

input

1. 6 5
   1 2
   2 5
   5 1
   3 4
   4 6

2. 6 8
   1 2
   2 5
   5 1
   3 4
   4 6
   5 4
   2 4
   2 3
   output

3. 2

4. 1

import sys

sys.setrecursionlimit(10000)
제귀함수 기본 제한은 1000 인데, 10000으로 강제로 늘려준다.

input = sys.stdin.readline
n,m = map(int,input().split())
a = [[] for _ in range(n+1)]
visited = [False] * (n+1)

def DFS(v):
    visited[v] = True
    for i in a[v]:
        if not visited[i]:
            DFS(i)

for _ in range(m):
    s,e = map(int,input().split())
    a[s].append(e)
    a[e].append(s)
count = 0

for i in range(1,n+1):
    if not visited[i]:
        count +=1
        DFS(i)
print(count)

---