우주의 IT 소행성

DFS (Depth First Search, 깊이 우선 탐색)

- 그래프에서 깊은 부분을 우선 탐색하는 알고리즘

그래프란?

- 노드와 간선(정점)으로 표현된 자료구조

- 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 그래프 탐색이라고 한다.

- 두 노드가 간선으로 이어져 있으면 '두 노드는 인접(Adjacent) 하다'라고 표현한다.

그래프의 표현 방식

- 그래프를 프로그래밍에서 표현하는 방식은 크게 2가지이다

1. 인접 행렬 방식 (Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현

표로 표현했을 때

INF = 999999999 # 무한

# 2차원 리스트의 인접 행렬 표현
graph = [
	[0, 3, 5],
    [3, 0, INF],
    [5, INF, 0]
}

print(graph)

파이썬 코드로 표현했을 때

- 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을수록 메모리의 낭비가 심함

- 인접 행렬 방식이 인접 리스트 방식보다 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 빠름

2. 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현

graph = [[] for _ in range(3)]

graph[0].append((1, 5))
graph[0].append((2, 3))

graph[1].append((0, 5))

graph[2].append((0, 3))

print(graph)

- 인접 리스트 방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용함

- 인접 리스트 방식은 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느림 (데이터를 하나씩 확인)

# DFS
def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ')
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph, i, visited)

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
dfs(graph, 1, visited)

BFS (Breadth First Search, 너비 우선 탐색)

- 가까운 노드부터 탐색하는 알고리즘

- DFS와 반대(가장 가까운 노드부터 / 가장 먼 노드부터)

- 선입선출의 큐 자료구조를 사용

- 재귀로 DFS를 구현하면 수행 시간이 느려질 수 있음

- 스택을 사용하여 DFS구현을 빠르게 동작시킬 수 있음

- 일반적인 경우 DFS보다 BFS의 동작이 빠름

# BFS
from collections import deque

def bfs(graph, start, visited):
	queue = deque([start])
    visited[start] = True
    while queue:
    	v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True

graph = [
	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9
bfs(graph, 1, visited)

그리디 알고리즘이란?

- 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘 설계 기법

- 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.

- 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형

- 주로 정렬과 짝을 이뤄 출제

- '가장 큰 순서대로', '가장 작은 순서대로'등의 기준을 알게 모르게 제시한다.

- 부분의 최적해들의 집합이 곧 전체문제의 해답일 경우 사용

대표적인 예시

- 거스름돈, 최소 신장 트리, 다익스트라, 허프만, 크리스컬....

거스름돈 문제

말 그대로, 돈을 거슬러 주는 문제인데, 가지고 있는 잔돈의 종류를 탐욕적으로 이용하여 가장 적은 잔돈의 종류를 내 주어야 한다.

거스름돈으로 사용할 동전의 종류

- 500원, 100원, 50원, 10원 (동전의 양은 무한하다고 가정)

1) 2340원을 받았다고 가정했을 때

- 500원 4개 -> 현재 동전 : 4 / 남은 돈 : 340

- 100원 3개 -> 현재 동전 : 7 / 남은 돈 : 40

- 10원 4개 -> 현재 동전 : 11 / 남은 돈 : 0

이므로 최적의 동전 개수는 11개이다.

2) 1260원을 받았다고 가정했을 때

- 500원 2개 -> 현재 동전 : 2 / 남은 돈 : 260

- 100원 2개 -> 현재 동전 : 4 / 남은 돈 : 60

- 50원 1개 -> 현재 동전 : 5 / 남은 돈 : 10

- 10원 1개 -> 현재 동전 : 6 / 남은 돈 : 0

이므로 최적의 동전 개수는 6개이다.

cost = int(input()
coins = [500, 100, 50, 10]
count = 0

for coin in coins:
	count += n
    n %= coin
 
print(count)

거스름 돈 알고리즘 코드

예시문제 1. 큰 수의 법칙 (2019 국가 교육기관 코딩 테스트 문제)

해당 문제에서 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 4라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다.

(서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.)

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 결과를 출력하시오.

<입력 예시>

5 8 3

2 4 5 4 6

<출력 예시>

46

n, m, k = map(int, input().split())
data = list(map(int, input().split()))
data.sort(reverse = True)
target = 0
result = 0
count = 0

while count < m:

    if target == 0:
        for j in range(k):
            result += data[target]
            count += 1
        target = 1

    else:
        result += data[target]
        target = 0
        count += 1

print(result)

이는 M의 숫자가 커지면 시간 초과가 될 수도 있는 코드이다.

주어진 배열의 1, 2 번째로 큰 수만을 사용하여 일정한 규칙을 나타내기 때문에

이를 일반항으로 도출하여 풀어낼수도 있지만, 시작의 장이기에 넘어가도록 하겠다.

다익스트라 알고리즘 (추가 예정)

오늘은 가장 기초적인 알고리즘 중 하나인 이분 탐색 (이진 탐색)에 대해서 알아보겠습니다.

이분 탐색에 앞서 순차 탐색에 대해서 복습을 해볼 텐데요.

N개의 데이터가 들어있는 어떤 데이터의 모음 DATA가 있을 때 DATA의 0번째 데이터부터 N번째 데이터까지 모두 방문하여 탐색하는 것을 순차 탐색이라고 합니다.

# 리스트에서 주어진 1개의 값을 찾는 소스코드
data = [12, 255, 156, 8798, 15, 487, 212, 11, 98, 9, 878, 999, 445, 54563, 546779, 78]
print("탐색할 데이터는 : , end='')
target = int(input())

for i in data:
	if i == target:
    	print(target, "을 찾았습니다!")
    	break

당연히 N개의 데이터가 들어있으니 탐색에도 N번만큼의 시간이 소요되겠습니다.

그렇다면 데이터가 1억 개가, 10억 개가, 아니 1조 개가 넘게 유입되어도 과연 순차 탐색으로 탐색을 해낼 수 있을까요?

정답은 "아니오" 입니다.

실제 코딩 테스트나 실무에서 사용하게 되는 알고리즘은 항상 최적의 시간 복잡도를 가져야 합니다.

1조 개의 데이터를 1조 번만큼 탐색하지 않고 더 적은 횟수를 탐색하는 알고리즘이 있다면 정말 좋겠습니다.

그런 알고리즘이 바로 오늘 배울 이분 탐색 알고리즘입니다.

이분 탐색 알고리즘이란?

- 탐색 범위를 절반으로 줄여나가면서 탐색하는 알고리즘

조건 : 배열 내부의 데이터가 오름차순으로 정렬되어 있어야 함

사용 시점 (보편적) : 1000만 이상의 데이터 탐색할 때, 정렬되어 있는 데이터를 탐색할 때

장점

- 매우 빠르게 데이터를 찾을 수 있음

- 탐색 범위를 절반씩 좁혀나가며 데이터를 탐색함

- O(logN)의 시간 복잡도를 가짐

이분 탐색은 탐색 범위의 시작점, 끝점, 중간점 세 점 간의 비교로 원하는 데이터를 빠르게 찾아내는 알고리즘입니다.

이분 탐색에 대해서 간단히 알아보도록 하겠습니다.

먼저 1부터 100까지 오름차순으로 정렬된 리스트가 있다고 가정합시다.

이 리스트에서 이분 탐색을 이용해 67을 탐색해봅시다.

시작점 = start = 1

끝 점 = end = 100

중간점 = mid = (시작점 + 끝점) // 2 = 50

타겟(target)인 67이 중간점보다는 크고 끝 점보다는 작습니다.

오름차순으로 정렬되어있는 리스트이기 때문에 중간점부터 끝점 사이에는 50 ~ 100까지의 숫자만 들어있으므로

우리는 시작점 ~ 중간점 ( 1 ~ 50 )를 탐색할 필요가 없습니다.

따라서

시작점 = 50

끝 점 = 100

중간점 = 75로 수정을 해 줍니다.

이번에는 타겟이 시작점보다 크고 중간점 보다 작습니다 (start <= target <= mid)

따라서

시작점 = 50

끝 점 = 75

중간점 = 62로 수정을 해 줍니다.

계속해서 타겟을 찾을 때 까지 탐색 범위를 좁혀줍니다.

축하드립니다! 계속해서 반복하다보니 중간점에 우리가 그토록 찾던 타겟이 나타났습니다!

이처럼 탐색 범위를 절반의 절반으로 줄여가는 방법을 이분 탐색이라고 합니다.

1 ~ 100까지 전체 데이터의 개수는 100개 이지만 이분 탐색을 이용해 총 7번의 탐색으로 원소를 찾았습니다.

만약 순차 탐색이였다면 더 많은 시간이 소요되었을 것입니다.

이제 이분 탐색을 파이썬으로 구현해보겠습니다.

재귀 함수로 구현한 이분 탐색법

def binary_search(array, target, start, end):
	if start > end:
    	return None
    mid = (start + end) // 2
    if array[mid] == target:
    	return mid
    elif array[mid] > target:
    	return binary_search(array, target, start, mid - 1)
    else:
    	return binary_search(array, target, mid + 1, end)

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

반복문으로 구현한 이분 탐색법

def binary_search(array, target, start, end):
	while start <= end:
    	mid = (start + end) // 2
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	end = mid - 1
        else:
        	start = mid + 1
    return None

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n - 1)
if result == None:
	print("원소가 존재하지 않습니다.")
else:
	print(result + 1)

질문, 추가, 오류, 오타, 지적 환영합니다.