IT-garden

순차 탐색(Sequential Search)은 탐색 방법에서 가장 간단하고 직접적인 탐색 알고리즘입니다.

순차 탐색은 리스트의 요소를 처음부터 마지막까지 하나씩 검사해서 원하는 값을 찾는 방법입니다.

원하는 값은 key로 주어지고 탐색의 범위는 low와 high로 주어집니다.

탐색에 성공하면 원하는 값의 인덱스를 반환하고 그렇지 않으면 -1을 반환합니다.

순차 탐색은 선형 탐색(linear search)이라고도 합니다.

a=[1, 3, 5, 7, 2, 4, 6]

def Sequential_Search(key, low, high):

    for i in range(low, high+1):
        if a[i] == key:
            return i

    return -1

# 출력>>6
print(Sequential_Search(6, 0, 6))

# 출력>>-1
print(Sequential_Search(10, 0, 6))

# 출력>>0
print(Sequential_Search(1, 0, 3))

# 출력>>-1
print(Sequential_Search(2, 0, 3))

함수 Sequential Search이 순차 탐색 알고리즘입니다.

Sequential_Search(6, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key 6의 인덱스를 찾습니다.

Sequential_Search(10, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key 10의 인덱스를 찾습니다.

Sequential_Search(1, 0, 3)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 3까지에서 key 1의 인덱스를 찾습니다.

print(Sequential_Search(2, 0, 3)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 3까지에서 key 2의 인덱스를 찾습니다.

a=[1, 3, 5, 7, 2, 4, 6]

def Sequential_Search(key):
    for i in range(len(a)):
        if a[i] == key:
            return i

    return -1

# 출력>>6
print(Sequential_Search(6))

# 출력>>-1
print(Sequential_Search(10))

탐색의 범위를 low와 high로 설정하지 않고 리스트 전체에서 key를 찾는 순차 탐색 알고리즘입니다.

가장 많이 사용하는 순차 탐색 알고리즘 코드입니다.

정렬된 리스트와 정렬되어 있지 않은 리스트에 모두 사용 가능합니다.

순차 탐색은 탐색에 성공하면 평균 (n+1)/2번 비교하고 탐색에 실패하면 n번 비교합니다.

순차 탐색 알고리즘의 시간 복잡도는 O(n)입니다.

만약 리스트가 정렬되어 있다면 위의 코드는 오랜 시간이 걸려서 비효율적인 방법입니다.

그래서 정렬되어 있는 리스트에서는 좀 더 간단하게 순차 탐색을 할 수 있습니다.

정렬된 리스트는 순차 탐색을 실행하는 도중 key 값보다 큰 항목을 만나면 그 뒤의 항목들은 모두 key 값이 아니라는 점을 기억해야 합니다.

a=[1, 3, 5, 7, 9, 11, 13]

def Sequential_Search(key):
    for i in range(len(a)):
        if a[i] > key:
            return -1
        
        if a[i] == key:
            return i

    return -1
# 출력>>2
print(Sequential_Search(5))

# 출력>>-1
print(Sequential_Search(10))

# 출력>>-1
print(Sequential_Search(17))

리스트에 key 값이 존재하거나 key 값이 리스트의 맨 마지막 요소보다 큰 경우 위의 순차 탐색과 같습니다.

하지만 해당 항목이 리스트에 존재하지 않고 리스트의 맨 마지막 요소보다 작아서 비교 횟수가 반이 됩니다.

그러나 시간 복잡도는 O(n)으로 동일합니다.

깊이 우선 탐색(DFS : Depth First Search)은 시작점으로부터 갈 수 있는 점 중 한 곳을 가서 그 곳에서 또 방문할 수 있는 점을 가서 방문할 수 있는 점이 없을 때까지 깊게 갔다 나오는 탐색 방법입니다.

깊이 우선 탐색은 크게 2가지 문제에서 자주 사용됩니다.

1. 그래프를 모두 탐색하는 문제

2. 특정 조합을 뽑는 문제

깊이 우선 탐색의 방법은
1. 하나의 점을 방문하고
2. 하나의 점과 연결 되어 있는 곳을 모두 방문하고 나옵니다.

깊이 우선 탐색에서는 재귀 함수를 이용합니다.

위와 같은 그래프가 있다고 가정하고 깊이 우선 탐색을 실시해보겠습니다.

시작점은 1로 생각하고 모든 그래프를 탐색하려고 합니다.

점을 방문할때는 더 작은 순서로 방문하도록 하겠습니다.

방문했는지 확인하기 위한 배열에 모든 값을 0으로 초기화합니다.

기존 그래프에서 1을 처음 방문합니다.

방문 완료를 배열의 1 자리의 값을 1로 바꾸는 것을 통해 알려줍니다.

1과 연결된 점은 2와 3이 있는데 작은 것을 먼저 방문하기로 했으니 2를 방문합니다.

배열의 2 자리의 값을 1로 바꿔줍니다.

2과 연결된 점은 4와 5가 있는데 작은 것을 먼저 방문하기로 했으니 4를 방문합니다.

배열의 4 자리의 값을 1로 바꿔줍니다.

4와 연결된 점은 2인데 2는 이미 방문을 했고 더이상 방문할 점이 없습니다.

4번에서 직전에 방문한 점인 2로 되돌아옵니다.

그 후 2에서 방문하지 않은 5를 방문합니다.

배열의 5 자리의 값을 1로 바꿔줍니다.

5와 연결된 점은 2인데 2는 이미 방문을 했습니다.

2와 연결된 점은 1, 4, 5가 있는데 모두 방문을 했습니다.

그럼 1로 돌아갑니다.

1과 연결된 점은 2와 3인데 방문하지 않은 3으로 가서 방문을 합니다.

배열 3 자리의 값을 1로 바꿔줍니다.

3과 연결된 점 중 방문하지 않은 6을 방문합니다.

6과 연결된 점 중 방문하지 않은 점이 없으므로 3으로 돌아갑니다.

3에서도 방문하지 않은 점이 없기 때문에 1로 돌아갑니다.

1번에서도 방문할 점이 없습니다.

그럼 모든 점들의 방문이 끝나 탐색이 종료됩니다.

위의 그래프에서 깊이 우선 탐색의 방문 순서는 1 → 2 → 4 → 5 → 3→ 6 입니다.

재귀 함수를 이용한 깊이 우선 탐색의 파이썬 코드입니다.

n = 6 #정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 #시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a = [[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def dfs(node):
    ch[node] = 1
    print(node, end=' ')

    for i in a[node]:
        if ch[i] != 1:
            dfs(i)

dfs(v)

# 최종 출력>>1 2 4 5 3 6 

너비 우선 탐색(BFS : Breadth First Search)은 시작점으로부터 가까운 점을 먼저 방문하고 멀리 떨어져 있는 점을 나중에 방문하는 탐색 방법입니다.

특징은 시작점으로부터 거리가 가까운 점의 순서로 탐색이 진행됩니다.

거리의 의미는 시작점으로부터 어느 점까지의 경로 중 가장 짧은 경로의 길이를 의미합니다.

즉, 거리가 a인 점들을 모두 방문하고 거리가 a + 1인 점들을 모두 방문합니다.

너비 우선 탐색은 크게 2가지 문제에서 자주 사용됩니다.

1. 그래프를 모두 탐색하는 문제

2. 특정 그래프에서 가중치가 모두 같을 때 최단거리를 찾는 문제

너비 우선 탐색의 방법은

1. 큐에서 하나를 꺼내 제거하고(제거 하는 것이 방문한 점)

2. 해당 점과 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

너비 우선 탐색에서는 큐를 사용합니다.

큐는 방문한 점들을 저장하고 제거하는데 사용하고 큐가 공백이 될 때까지 탐색이 계속됩니다.

위와 같은 그래프가 있다고 가정하고 너비 우선 탐색을 실시해보겠습니다.

시작점은 1로 생각하고 모든 그래프를 탐색하려고 합니다.

점을 방문할때는 더 작은 순서로 방문하도록 하겠습니다.

기존 그래프에서 1을 큐에 넣어줍니다. 1이 시작점이기 때문입니다.

그리고 1을 방문하여 큐에서 1을 제거하고 1과 연결되어 있는 점들 중 방문하지 않은 점인 2와 3을 큐에 넣습니다.

큐에서 다음으로 2를 방문하여 큐에서 2를 제거하고 2와 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

여기서 1은 이미 방문했기 때문에 큐에 넣지 않고 4와 5를 넣습니다.

다음으로 3를 방문하여 큐에서 3를 제거하고 3와 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

여기서 1은 이미 방문했기 때문에 6만 큐에 넣습니다.

큐에서 4를 방문하며 4를 제거합니다. 이때 4에 연결된 점들 중 방문하지 않은 점이 없기 때문에 큐에 값을 넣어주지 않습니다.

마찬가지로 5도 방문하고 큐에서 제거해줍니다.

마지막으로 6도 방문하고 큐에서 제거해줍니다.

그럼 모든 점들의 방문이 끝나 탐색이 종료됩니다.

위의 그래프에서 너비 우선 탐색의 방문 순서는 1 → 2 → 3 → 4 → 5→ 6 입니다.

큐를 이용한 너비 우선 탐색의 파이썬 코드입니다.

import queue

n = 6 # 정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 # 시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a = [[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def bfs(start):
    q = queue.Queue()
    q.put(start)
    ch[start] = 1

    while not q.empty():
        now = q.get()
        print(now, end=' ')
        for i in a[now]:
            if ch[i] != 1:
                ch[i] = 1
                q.put(i)
                
bfs(v)

# 최종 출력>>1 2 3 4 5 6

덱을 이용한 너비 우선 탐색의 파이썬 코드입니다.

from collections import deque

n = 6 #정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 #시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a=[[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def bfs(start):
    de = deque()
    de.append(start)
    ch[start] = 1 

    while len(de) != 0:
        now = de.popleft()
        print(now, end=' ')
        for i in a[now]:
            if ch[i] != 1:
                ch[i] = 1
                de.append(i)
                
bfs(v)

# 최종 출력>>1 2 3 4 5 6

순열(permutation)은 순서를 고려해서 선택한 경우의 수를 의미합니다.

from itertools import permutations

permutations(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

순열의 기본 구조입니다.

순열의 개수는 n! / (n-r)! 입니다.

1, 2, 3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.
개수 : 3! / (3-2)! = 6 / 1 = 6
(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)

순서를 고려한다는 것은 (1, 2)와 (2, 1)를 다른 것으로 생각한다는 의미입니다.

from itertools import permutations

p=list(permutations([1, 2, 3], 2))

# 출력>>[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
print(p)

a=[1,2,3]

for i in permutations(a):
    # 출력>>(1, 2, 3) (1, 3, 2) (2, 1, 3) (2, 3, 1) (3, 1, 2) (3, 2, 1)
    print(i,end=' ')
    
for i in permutations(a,2):
    # 출력>>(1, 2) (1, 3) (2, 1) (2, 3) (3, 1) (3, 2) 
    print(i,end=' ')

조합(combination)은 순서를 고려하지 않고 선택한 경우의 수를 의미합니다.

from itertools import combinations

combinations(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

조합의 기본 구조입니다.

조합의 개수는 n! / r! (n-r)! 입니다.

1, 2, 3 숫자 3개가 있다고 할 때 순서를 고려하지 않고 2장을 뽑으면 다음과 같습니다.
개수 : 3! / 2! (3-2)! = 6 * 2 = 3
(1, 2), (1, 3), (2, 3)

순서를 고려하지 않는다는 것은 (1, 2)와 (2, 1)를 같은 것으로 생각한다는 의미입니다.

from itertools import combinations

c=list(combinations([1, 2, 3], 2))

# 출력>>[(1, 2), (1, 3), (2, 3)]
print(c)

a=[1,2,3]
    
for i in combinations(a,2):
    # 출력>>(1, 2) (1, 3) (2, 3)  
    print(i,end=' ')

중복 가능한 순열은 product를 이용해 표현할 수 있습니다.

from itertools import product

product(인자(반복 가능한 것 ex. 리스트, 문자열), repeat)

중복 가능한 순열의 기본 구조입니다.

중복 가능한 순열의 개수는 n^r 입니다.

repeat라는 인자를 통해 앞의 인자를 반복해서 뽑는 기능입니다.

1,2,3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.
개수 : 3^2 = 9
(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)

from itertools import product

a=list(product([1, 2, 3], repeat=2))

# 출력>>[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
print(a)

중복 가능한 순열은 combinations_with_replacement를 이용해 표현할 수 있습니다.

from itertools import combinations_with_replacement

combinations_with_replacement(인자(반복 가능한 것 ex. 리스트, 문자열),뽑을 개수)

중복 가능한 조합의 기본 구조입니다.

중복 가능한 조합의 개수는 (n+r-1)! / r! / (n-1)!  입니다.

1,2,3 숫자 3개가 있다고 할 때 순서를 고려해서 2장을 뽑으면 다음과 같습니다.

개수 : (3+2-1)! / 2! / (3-1)! = 24 / 2 / 2 = 6 
(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)

from itertools import combinations_with_replacement

a=list(combinations_with_replacement([1,2,3], 2))

# 출력>>[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
print(a)

계수정렬은 n이 정수면 입력 값들이 1부터 n까지의 정수라는 가정이 필요합니다.

그리고 입력 값들을 갯수만큼 세서 출력해주면 정렬을 할 수 있습니다.

속도가 빠르고 코드가 간결하다는 장점이 있습니다.

기존 리스트의 요소를 하나씩 검사하여 새로운 리스트에 그 요소의 위치에 값을 1씩 더해줍니다.

검사를 완료하면 새로운 리스트의 갯수들을 그 위치의 숫자만큼 출력해줍니다.

계수정렬의 파이썬 코드입니다.

b = [5, 2, 3, 4, 1, 1, 4, 4]

n=[0] * 5
a=[]

for i in range(len(b)):
    n[b[i]-1] += 1

for i in range(len(n)):
    for j in range(n[i]):
        a.append(i+1)
            
# 결과>>[1, 1, 2, 3, 4, 4, 4, 5]
print(a)

힙정렬은 리스트나 배열을 먼저 최소힙이나 최대힙으로 바꾸고 원소들을 순서대로 정렬하는 방법입니다.

최소힙은 최소값을 구할 때 사용하고 최대힙은 최대값을 구할때 이용합니다.

힙정렬은 완전 이진 트리입니다.

최소힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 형태의 완전 이진 트리

최대힙 : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 형태의 완전 이진 트리

기존 리스트를 최대힙으로 바꾸는 과정입니다.

9의 위치를 찾기 위해 9와 2를 비교했을 때 9 > 2 이기 때문에 9와 2를 교환합니다.

9가 2의 위치로 오고 9와 5를 비교했을 때 9 >5 이기 때문에 9와 5를 교환합니다.

최대힙으로 만들고 원소들을 순서대로 정렬합니다.

루트에 있는 원소를 리스트 끝에서부터 넣어줍니다.

루트 값 9를 4와 교환하고 9는 정렬을 완료합니다. 그리고 4의 자리를 찾아줍니다.

4가 자리를 찾으며 루트에 새로운 값이 오게 되는데 이 값은 9를 제외하고 리스트에서 가장 큰 값입니다.

다음에는 이 값을 2와 교환하는 식으로 정렬 과정을 거칩니다.

힙정렬의 파이썬 코드입니다.

def heap_sort(a):
    for i in range(1,len(a)): # 최대 힙 만들기
        c = i
        while c != 0:
            r = (c-1) // 2
            if a[r] < a[c]:
                a[r], a[c] = a[c], a[r]
                
            c = r

    for j in range(len(a)-1,-1,-1): # 힙 만들기
        a[0], a[j] = a[j], a[0]
        r = 0
        c = 1

        while c < j:
            c= 2 * r + 1
            if c < j -1 and a[c] < a[c+1]:
                c += 1
                
            if c < j and a[r] < a[c]:
                a[r], a[c]=a[c], a[r]
                
            r = c 

b = [5, 2, 3, 9, 6, 1, 8, 4, 7]
heap_sort(b)

# 결과>>[1, 2, 3, 4, 5, 6, 7, 8, 9]
print(b)