다익스트라 알고리즘은 플로이드 워셜(Floyd-Warshall)과 함께 최단 경로를 찾는 대표적인 알고리즘이다. 다익스트라는 구현이 간단하지만 오래 걸리는 방법과 구현은 복잡하지만 성능이 개선된 방법 두 가지가 존재한다.

다익스트라의 특징

• 시작점에서 도착점(특정 노드 또는 모든 노드)까지의 최소 비용을 구할 때 사용한다.
• 단, 가중치가 음수일 경우 사용하지 못한다.
  • 가중치가 음수일 때는 벨만-포드 알고리즘(Bellman-Ford Algorithm)이 사용 가능한데 이 경우에도 제약 사항이 존재한다. (음의 사이클이 존재하면 사용하지 못한다.)
• 원래는 O(V^2)의 시간복잡도를 가진다. 하지만 heapq(우선순위 큐)를 사용하면 O(ElogV)의 속도로 개선 가능하다. 이를 개선된 다익스트라라고 부른다.
  • V: 노드의 개수, E: 간선의 개수 참고: https://techblog-history-younghunjo1.tistory.com/248

💡다익스트라 동작 방식

1. 출발 노드를 설정
2. 최단 거리 테이블을 inf(아주 큰 값)으로 초기화
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
   1. 방문 여부를 나타내기 위한 visited 배열이 필요
4. 해당 노드를 경유지로 삼아 다른 노드로 가는 비용을 계산하여 다이렉트로 가는 비용보다 작을 시 최단 거리 테이블을 업데이트
5. 위 과정에서 3, 4번을 반복

순차 탐색으로 구현

# 시작점-도착점 바로 가는 거랑 시작점-경유지-도착점 비용 비교해서, 작은 것으로 업데이트
st, ed = 0, 4
arr = [
    [0,3,21e8,9,5], # 연결되어 있지 않은 노드는 21e8로 초기화
    [21e8,0,7,21e8,1],
    [21e8,21e8,0,1,21e8],
    [21e8,21e8,21e8,0,21e8],
    [21e8,21e8,1,21e8,0]
]
used = [0]*5
result = arr[0][:] # 최단 거리 테이블 초기화
used[st] = 1 # 시작점을 방문 처리

for _ in range(len(arr)-1): # 경유지를 총 N-1번 고르면서 바꿔감

    # 경유지로 선택하지 않았던 것 중에 최소 비용을 가지는 노드를 경유지로 선택
    Min, Min_idx = 21e8, 0 
    for i in range(len(result)):
        if result[i] < Min and used[i] == 0: ## 중요
            Min = result[i]
            Min_idx = i

    mid = Min_idx # 경유지
    used[mid] = 1 # 방문 처리

    for i in range(len(result)):
        dest = i # 도착점

        # direct: 시작점 - 도착점 비용
        direct = result[i]

        # detour: 시작점 - 경유지 - 도착점 비용
        detour = result[mid] + arr[mid][dest]

        if direct > detour: # detour가 더 작을 경우 업데이트
            result[i] = detour
print(*result)
print(result[ed]) # st -> ed의 최단 거리

💡우선순위 큐로 구현

# 개선된 다익스트라
'''
5 정점의 개수
7 간선의 개수
0 1 3 시작점, 도착점, 비용
0 3 9
0 4 5
1 2 7
1 4 1
2 3 1
4 2 1
0 3 최소비용이 알고 싶은 출발점과 도착지 
'''
import heapq

def dijkstra(start):

    # 비용, 경유지/ 적은 비용 순으로 pop하기 위해 이런 순서로 push
    heapq.heappush(heap, (0,start)) 
    result[start] = 0                   # 시작점 최단 거리 초기화
    while heap:
        cost, mid = heapq.heappop(heap) # 시작점 > 경유지 비용, 경유지

        if result[mid] < cost: continue # 업데이트 되어있는 시작점 -> 경유지 값 vs
                                        # 큐에서 방금 뽑은 시작점 -> 경유지 값 비교

        # 경유지에서 갈 수 있는 도착점을 모두 순회
        for i in arr[mid]:  
            detour = cost + i[1]
            if detour < result[i[0]]:
                result[i[0]] = detour
                heapq.heappush(heap, (detour, i[0])) # 갱신된 비용(우선순위), 도착지 

name = 'ABCDE'
N = int(input())
M = int(input())

arr = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    arr[a].append((b,c))          # 도착점, 비용 순으로 append

st, ed = map(int, input().split())
inf = 21e8
result = [inf]*N                  # 최단 거리 테이블 초기화
heap = []

dijkstra(st)
print(*result)

다익스트라 활용 문제

• SWEA
  • 최소 이동 거리

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것을 말한다. 데이터 추가는 어떤 순서로 해도 상관 없지만, 제거될 때는 가장 작은 값을 제거하는 특징을 가진 자료구조이다. Python에서는 이런 로직이 내부적으로 구현되어 있는 heapq 모듈을 제공한다.

힙(Heap) 자료구조란?

heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(Min heap) 자료구조를 제공한다. 부모노드와 서브트리간 대소 관계가 성립한다. 즉, 반 정렬된 상태를 유지하며 항상 루트 노드에 최솟값이 들어가게 된다. 그렇다고 힙(Heap)이 완벽하게 정렬된 것은 아니다. 부모 자식 간의 대소 관계만 명확할 뿐이다.

cf) 최소 힙(Min heap)이란?

부모 노드의 값이 자식 노드보다 크거나 같은 완전이진트리이다.

이미지 출처 - https://suyeon96.tistory.com/31

💡Python의 heapq 모듈

• 최소 힙(Min Heap)의 구조
• 모든 k에 대해 heap[k] <= heap[2*k+1]와 heap[k] <= heap[2*k+2]를 만족
• 가장 작은 원소가 heap[0]에 위치한다.
• heap을 만들기 위해서는, lst = [](초기화된 리스트)를 heap.heappush(lst, 숫자) 이렇게 heappush 함수의 매개변수로 사용하거나, heapify를 통해 값이 들어있는 리스트를 힙으로 변환 가능

💡우선순위 큐의 시간복잡도

이미지 출처 - https://suyeon96.tistory.com/31

cf) 스택(Stack), 큐(Queue)의 시간복잡도

삽입과 삭제는 O(1)의 시간복잡도를 가지고, 검색은 O(n)의 시간복잡도를 가진다.

heapq 활용 예시 코드

import heapq # 우선순위 큐를 사용하기 위한 모듈

# 초기화 배열을 heappush하면 heap의 자료형으로 바꾼다. 
# (heapify가 저절로 된다고 생각하면 됨)
arr = [] 

heapq.heappush(arr, 4)  
heapq.heappush(arr, 15)
heapq.heappush(arr, 2)
heapq.heappush(arr, 7)
heapq.heappush(arr, 5)
heapq.heappush(arr, 9)

print(heapq.heappop(arr)) # logN의 속도로 우선순위가 가장 높은 값을 출력

# 최솟값부터 출력이 되도록 코드 적어보기
arr2 = [9,7,6,7,5,26,47,62,5,1]
tmp = arr2[:]
heapq.heapify(tmp)

for _ in range(N):
    print(heapq.heappop(tmp), end=' ') # 최솟값부터 pop

# 최솟값을 삭제하지 않고 읽기만 하고 싶을 땐
# heap[0]으로 접근

Max heap 만들기

# max heap
arr3 = [8,7,64,9,12,5,7,56]

heap = []

for i in range(len(arr3)):
    heapq.heappush(heap, -arr3[i]) # 음수로 만들어서 heap에 push
for i in range(len(arr3)):
    print(heapq.heappop(heap)*-1)  # heappop은 원소를 삭제하면서 그 원소를 return 

# 람다 이용
rev = lambda x: x*-1
heap1 = list(map(rev,arr3))
heapq.heapify(heap1)               # 이미 값이 들어있기 때문에 heapify 필요
for i in range(len(arr3)):
    print(-heapq.heappop(heap1))

# 튜플
for i in range(len(arr3)):
    heapq.heappush(heap, (-arr3[i], arr3[i])) # (원본, -원본)을 heapq에 push
for i in range(len(arr3)):
    print(heapq.heappop(heap)[1])

nsmallest(), nlargest() 함수 사용

• nsmallest(n, lst): n개의 작은 수를 오름차순으로 담은 리스트를 반환
• nlargest(n, lst): n개의 큰 수를 내림차순으로 담은 리스트를 반환

# 함수를 import
from heapq import nsmallest, nlargest

tmp = nsmallest(3, [4, 1, 7, 3, 8, 5])[:]
print(tmp) # [1, 3, 4]
print(tmp[-1]) # 원본 배열에서 n번째로 작은 수를 출력

tmp2 = nlargest(3, [4, 1, 7, 3, 8, 5])[:]
print(tmp2) # [8, 7, 5]
print(tmp[-1]) # 원본 배열에서 n번째로 큰 수를 출력

Python의 PriorityQueue 모듈

파이썬에는 우선순위 큐의 활용을 위해 PriorityQueue라는 모듈을 추가로 제공하고 있다. 소스 코드를 보면 PriorityQueue 클래스가 heapq 모듈을 이용하고 있는 것을 알 수 있다.

둘의 차이는 Thread-Safe 하느냐 Non-Safe 하느냐에 있다. Thread-Safe를 요구하는 상황이면 PriorityQueue를 사용하고, Thread-Non-Safe해도 되는 상황이면 heapq를 쓰는 것이 시간적 측면에서 효율이 좋다.

🎈우선순위 큐 활용 문제

• 백준
  • 가운데를 말해요
  • 카드 정렬하기

메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법이다. 또한 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이기도 하다.

DP의 핵심은 ‘메모제이션’(캐싱) 기법이다. 이미 계산된 결과(작은 문제)를 별도의 메모리에 저장해 다시 계산하지 않고 필요한 경우 사용하는 기법이다. 이 기법을 사용하면 시간복잡도가 훨씬 줄어들기에 수행 시간 효율이 비약적으로 향상된다.

• 처음 진행되는 연산은 기록한다.
• 이미 진행된 연산이라면 기록된 값을 호출한다.
• 시간과 자원 절약이 가능하다.

💡DP 사용 조건

• 최적 부분 구조(Optimal substructure)
  • 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
• 부분 문제 반복(Overlapping subproblems)
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

💡DP 문제 해결 과정

1. 주어진 문제가 DP 유형이 맞는지 확인 후, 최종적으로 풀어야 할 큰 문제를 확인한다.
2. 큰 문제를 작은 문제로 분해하여 그 사이의 관계를 점화식의 형태로 나타낸다.
3. Memoization(Top-Down, 하향식) 방식 혹은 Tabulation(Bottom-up, 상향식) 방식을 통해 문제를 풀어나간다.

동적 계획법(DP) vs 분할 정복(Divide and Conquer)

동적 계획법의 경우 작은 문제가 큰 문제에 영향을 끼친다. 즉, 작은 문제가 종속적 특징을 가진다.

반면, 분할 정복은 작은 문제가 큰 문제에 영향을 끼치지 않는다. 즉, 각 문제들은 서로 독립적이다.

동적 계획법(DP) vs 탐욕법(Greedy)

탐욕법의 경우 현재의 상태에서 최적을 고르기 때문에, 문제에 따라 최적해를 보장하지 않는 경우도 있다.

하지만, 동적 계획법의 경우 모든 가능성을 고려하므로 어떤 문제든 항상 최적해를 보장한다.

🎈대표 문제 1

• SWEA 보급로, Bottom-up 방식

point > 출발점에서 도착점까지 가는데 드는 최소 비용 출력

for tc in range(1,int(input())+1):
    N = int(input())
    arr = [list(map(int, list(input()))) for _ in range(N)]

    dist = [[21e8]*N for _ in range(N)] # 최소 비용을 저장할 배열
    q = [(0,0)]                         # 출발점을 q에 append
    dist[0][0] = arr[0][0]              # 출발점 최소 비용 초기화
    dy = [0,0,1,-1]                     # 움직일 수 있는 반경
    dx = [1,-1,0,0]
    while q:
        y, x = q.pop(0)
        for i in range(4):
            ny, nx = dy[i]+y, dx[i]+x
            if not(0<=ny<N and 0<=nx<N): continue
            tmp = arr[ny][nx] + dist[y][x]  # 기존 위치의 최소 비용 + 움직인 위치의 비용
            if tmp < dist[ny][nx]:          # 비교 후 더 작은 값으로 갱신
                dist[ny][nx] = tmp
                q.append((ny,nx))
    print(f'#{tc} {dist[-1][-1]}')

🎈대표 문제 2

• 최소 동전 개수를 사용하여 입력 받은 돈을 거슬러 주는 문제, Bottom-up 방식

point > 동전이 서로 배수 관계가 아님

coin = [1,7,10] 
N = int(input()) # 입력 받은 돈

# 코인의 개수(y), 돈(x)을 기준으로 2차원 배열 생성
arr = [[0 for _ in range(N+1)] for _ in range(len(coin)+1)] 

for i in range(1,len(coin)+1): # 사용할 코인의 idx
    for j in range(1,N+1): # 확인하는 금액
        value = coin[i-1]
        if j//value == 0: # 몫이 없으면 위의 값 그대로
            arr[i][j] = arr[i-1][j]
        else: # 몫이 있고
            if j % value == 0: # 나머지가 0이면
                arr[i][j] = j//value
            else: # 나머지가 0이 아니라면
                arr[i][j] = min(arr[i-1][j], j//value + arr[i][j % value])

print(arr[len(coin)][N])

🎈대표 문제 3

• Knapsack - 배낭 채우기 문제

가방의 용량이 정해져 있을 때, 배낭에 넣을 수 있는 물건들의 총가치가 최대일 때를 구하여라.

N, K = map(int, input().split()) # 총 물건의 개수, 가방의 용량(무게)

# 물건의 개수(y), 무게(x)를 기준으로 2차원 배열 생성
arr = [[0]*(K+1) for _ in range(N+1)]

for k in range(1,N+1): # 1~K번째 물건으로 i kg 을 만들 때 최대 가치

    W, V = map(int, input().split()) # 물건의 무게, 물건의 가치

    for i in range(1,K+1): # i kg

        if i-W >= 0: # 넣을 수 있으면
            Sum = V # 새로 확인해주는 물건의 가치 + 나머지 무게의 최대 가치
            Sum += arr[k-1][i-W]
            # Sum과 이 물건을 사용하지 않았을 때 최대 가치를 비교하여 최댓값을 선택
            arr[k][i] = max(Sum, arr[k-1][i]) 

        else: # 넣을 수 없으면 위의 값을 그대로
            arr[k][i] = arr[k-1][i]

print(arr[N][K])

추가 문제

• SWEA 전기버스2
• [SWEA 최소 비용] (https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYHO7a2JoDFAVT#)

그리디 알고리즘은 탐욕 알고리즘이라고도 불린다. 여러 경우 중 하나를 결정해야 할 때마다, 현재 상황에서 최적이라고 생각되는 경우를 선택하여 정답를 구하는 알고리즘이다. 그리디 알고리즘은 현재의 선택이 나중에 미칠 영향을 고려하지 않기 때문에, 항상 최적해를 보장하는 건 아니다. 그래서 그리디는 주로 근사치 추정에 활용된다.

알고리즘 문제를 풀 때, 그리디로 풀 수 있는지 여부를 빠르게 판단하는 것이 중요하다. 보통 그리디 알고리즘 문제의 경우 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준이 제시되어 있다.

그리디 알고리즘의 정당성

그리디 알고리즘이 이 문제의 최적해를 보장하는가?를 판단하는 기준은 다음과 같다.

• 탐욕적 선택 속성(greedy choice property)
  • 탐욕적 선택이 항상 최적해를 보장해야한다.
• 최적 부분 구조(potimal substructure property)
  • 하나의 선택을 하면 풀어야 할 하위 문제가 남아야 한다. (Top-down 방식)

💡대표적인 그리디 알고리즘 종류

🎈Greedy(탐욕 기법) vs DP(동적 계획법)

• SWEA 화물 도크

문제의 point > 최대 몇 대의 화물차가 도크를 이용할 수 있는지를 출력하시오.

for tc in range(1, int(input())+1):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    arr.sort(key = lambda x: x[1]) # 작업 종료 시간을 기준으로 정렬
    ed = arr[0][1] # 선택 작업의 종료 지점
    cnt = 1 # 도크를 사용한 화물차의 개수
    for i in range(1,N):
        if arr[i][0] >= ed:
            cnt += 1
            ed = arr[i][1]
    print(f'#{tc} {cnt}')

대표 문제 2

• SWEA 쉬운 거스름돈

문제의 point > 최소 개수로 거슬러 주기 위하여 각 종류의 화폐가 몇 개씩 필요한지 출력하여라.

for tc in range(1, int(input())+1):
    money = int(input())
    coin = [50000,10000,5000,1000,500,100,50,10]
    result = [0]*8
    for i in range(8): # 가장 큰 금액의 화폐부터 몫을 저장해줌
        if money >= coin[i]:
            result[i] += money//coin[i]
            money = money%coin[i]
    print(f'#{tc}')
    print(*result)

대표 문제 3

• SWEA 베이비진 게임

def isbabygin(lst): # 베이비진을 확인하는 함수
    flag = False
    for i in range(len(lst)):
        if lst[i] == 3: # 같은 카드 세 장이면
            flag = True
            break
        if i < len(lst)-2:
            if lst[i]>=1 and lst[i+1]>=1 and lst[i+2]>=1: # 연속된 카드 세 장이면
                flag = True
                break
    return flag

for tc in range(1, int(input())+1):
    arr = list(map(int, input().split()))
    bst1, bst2 = [0]*10, [0]*10 # 플레이어 1, 2의 0 ~ 9 카드 개수를 저장
    flag = 0
    for i in range(12):
        if i%2 == 0:
            bst1[arr[i]] += 1
            if isbabygin(bst1):
                flag = 1
                break
        else:
            bst2[arr[i]] += 1
            if isbabygin(bst2):
                flag = 2
                break
    print(f'#{tc} {flag}')

🎈추가 문제

• SWEA 컨테이너 운반

소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수이다. 보통은 2부터 N-1(자신-1)까지 돌며 나누어 떨어지는 수가 있는지 확인한다.

어떤 수의 약수는 그 수의 제곱근을 기준으로 곱셈 연산에 대해 대칭을 이룬다. 이런 성질로 인해 어떤 수의 2부터 제곱근까지만 나누어 떨어지는 수가 있는지 확인하면 된다.

💡에라토스테네스의 체 알고리즘이란?

에라토스테네스의 체(Sieve of Eratosthenes)는 N보다 작거나 같은 모든 소수를 찾을 때 사용하는 알고리즘이다.

• 에라토스테네스의 체 동작 과정
  • 2부터 N까지의 모든 자연수를 나열한다.
  • 2부터 시작하여 n의 제곱근 까지 돌며, 그 수의 배수에 해당하는 수를 모두 지운다. 지울 때 자기 자신은 지우지 않고, 이미 지워진 수는 건너뛴다.
  • 순회를 다 돌고 남아있는 수를 모두 출력한다.

import math

a=int(input()) # a보다 작거나 같은 소수를 구할 것임
answer=[]
check=[True for i in range(a + 1)]
for i in range(2,int(math.sqrt(a))+1): # 2부터 입력받은 수의 제곱근 까지 모두 확인
    if check[i] == False: continue # 확인하는 값이 이미 제거되었으면 스킵
    for j in range(i+i,a+1,i): # 확인하고자 하는 배수에 해당하는 값을 False
        check[j]=False

# 위에 for문이 끝나면, 소수가 아닌 곳에는 False 체크가 되어 있고
# 소수인 숫자들에는 True 가 남아 있다.

for i in range(2,a+1):
    if check[i]==True:
        print(i,end=' ')

💡에라토스테네스의 체 시간복잡도

• 에라토스테네스의 체는 선형 시간에 가까울 정도로 빠른 O(nlog(logn))이다.
• 하지만 각 자연수에 대한 소수 여부를 저장해야 하므로 숫자가 클 경우 메모리가 많이 필요하다.

두 수의 최대공약수(GCD)를 구하는 알고리즘으로, 유클리드에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.

유클리드 호제법 동작 과정

유클리드 호제법에는 모듈러 연산(나머지 연산)이 사용된다.

• 큰 수를 작은 수로 나눈 나머지를 구한다.
• 나눴던 수와 그 나머지로 또 모듈러 연산을 한다.
• 위의 과정을 반복하다가 나머지가 0이 되었을 때, 마지막 연산에서 나누는 수로 사용된 수가 최대공약수(GCD)이다.

cf) 이 알고리즘의 포인트는 두 수가 모두 GCD의 배수라는 점이다. 그렇기 때문에 나머지 연산의 반복으로 GCD를 구할 수 있다.

'''
1. 최대공약수(Greatest Common Divisor)
숫자 2개 입력받고 최대공약수를 구하는 일반적인 방법
2부터 둘중 작은 수 까지 나누었을 때 나눠지는 수 중 가장 큰 수

32 16 -> 16
24 16 -> 8
'''
answer=0
a,b=map(int,input())
for i in range(2,min(a,b)+1):
    if a%i==0 and b%i==0:
        answer=i
print(answer)

'''
2. 최대공약수를 위 코드보다 조금 더 빠른 속도로 구하고 싶을 때
유클리드 호제법(최초의 알고리즘라는 것에 의미가 있음)
'''

a,b=map(int,input())
answer=0
while b:
    answer = a % b
    a = b
    b = answer
print(a)
'''
최소공배수(Least Common Multipe)
a와 b의 최소공배수는 GCD를 먼저 구한 다음에
LCM = a*b/GCD 이렇게 구한다.
'''

💡유클리드 호제법 활용 문제

• 프로그래머스 N개의 최소공배수

사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다.

특정 공정을 수행하기 위해선 선행 되어야 하는 공정이 다 수행되어야 할 때 많이 쓰인다.

• 진입차수(Indegree): 특정한 노드로 들어오는 간선의 개수
• 진출차수(Outdegree): 특정한 노드에서 나가는 간선의 개수

위상 정렬의 특징

• 위상 정렬을 수행할 그래프는 사이클이 없는 방향 그래프(DAG)여야 한다.
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있다.
• 위상 정렬에는 여러가지 답이 존재할 수 있다.

💡위상 정렬 알고리즘 동작 과정

1. 진입차수가 0인 모든 노드를 큐에 넣는다.
2. 큐가 빌 때까지 다음의 과정을 반복한다.
   1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
   2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

→ 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과이다.

# 인접 행렬로 그래프가 표현되어 있을 때
from collections import deque

name=['cs','language','datastructure','algorithm','project','codingtest','to be a programmer']

arr = [
    [0,0,0,0,0,0,1],
    [0,0,1,1,0,0,0],
    [0,0,0,0,0,1,0],
    [0,0,0,0,0,1,0],
    [0,0,0,0,0,0,1],
    [0,0,0,0,0,0,1],
    [0,0,0,0,0,0,0],
]

acc=[0]*len(name)           # 사전 작업 개수를 등록할 배열 (진입 차수 표현)
used=[0]*len(name)          # 사전 작업이 0개 남았을 때 used를 1로 바꿔줄 예정

q = deque()
for j in range(len(name)):  # 사전 작업 개수 등록
    for i in range(len(name)):
        if arr[i][j]==1:
            acc[j]+=1

for i in range(len(name)):  # 바로 작업 착수 가능한 것들은 (진입 차수 0)
    if acc[i]==0:           # used에 1체크 하고 q에 등록
        used[i]=1
        q.append(i)

while q:
    now = q.popleft()
    print(name[now])
    for i in range(len(name)):
        if arr[now][i]==1 and used[i]==0: 
            if acc[i]==1:   # 사전 작업이 1개 남았을 때
                used[i]=1
                acc[i]-=1
                q.append(i)
            else:           # 사전 작업이 1개 이상 남았을 때
                acc[i]-=1
'''
cs
language
project
datastructure
algorithm
codingtest
to be a programmer
'''

# 인접 리스트로 그래프가 표현되어 있을 때
from collections import deque

name=['cs','language','datastructure','algorithm','project','codingtest','to be a programmer']

arr = [
    [6],
    [2,3],
    [5],
    [5],
    [6],
    [6],
    [],
]

acc=[0]*len(name)           # 사전 작업 개수를 등록할 배열 (진입 차수 표현)
used=[0]*len(name)          # 사전 작업이 0개 남았을 때 used를 1로 바꿔줄 예정

for i in range(len(arr)):   # 사전 작업 개수 등록
    for j in range(len(arr[i])):
        acc[arr[i][j]] += 1

q = deque()
for i in range(len(name)):  # 바로 작업 착수 가능한 것들은 (진입 차수 0)
    if acc[i]==0:           # used에 1체크 하고 q에 등록
        q.append(i)

result = []
while q:
    now = q.popleft()
    result.append(name[now])
    for i in arr[now]:
        acc[i] -= 1
        if acc[i] == 0:     # 사전 작업이 다 끝났을 때
            q.append(i)

print(*result, sep='\n')
'''
cs
language
project
datastructure
algorithm
codingtest
to be a programmer
'''

💡위상 정렬 활용 문제

• 백준
  • 줄 세우기
  • 작업

원소 수에 해당하는 N개의 비트열을 이용한다. n번째 비트값이 1이면 n번째 원소카 포함 되었음을 의미한다. 이는 부분 집합(개수가 정해져 있지 않은 조합)을 구하는 문제에서 활용된다.

구현 코드

# 바이너리 카운팅
arr = [3,6,7,1,5,4]
n = len(arr)

for i in range(0, (1<<n)): # 부분집합의 개수만큼 print
    for j in range(0, n):  # 원소의 수만큼 비트를 비교함
        if i & (1<<j):     # i의 j번째 비트가 1이면 원소 출력
            print(arr[j], end = ' ')
    print()

💡유사 문제

바이너리 카운팅처럼 각 원소가 포함되는지 아닌지 여부를 배열에 표시하여 부분 집합을 나타내면 효율적으로 문제를 해결할 수 있다.

# power=[50,40,99,5,25,6,37]
       # a ,b ,c ,d ,e ,f ,g

# 서바이벌 게임
# a ~ g 를 두팀으로 나누어서 게임을 하고자 합니다.
# 두 팀으로 나누었을 때, 두 팀의 전투력 차이가 최소를 구하시오.
# 모든 선수는 경기에 참가를 하며, 팀 인원은 자유입니다. (1인팀도 가능)

power=[50,40,99,5,25,6,37] # 전력을 나타내는 배열
check=[0]*7 # 팀에 포함 여부를 0과 1로 나타냄
Min=21e8

def dfs(start,level,sum): # level은 뽑은 사람의 수
    global Min,power
    # 아래의 과정을 재귀 돌 때 마다 매번 확인(팀 인원이 정해져 있지 않으니까)
    against = 0 # 상대 팀의 전력을 더해줄 변수
    for i in range(7):
        if check[i] == 0:
            against+=power[i]
    gap = abs(sum - against) # 우리 팀 전력 - 상대팀 전력의 절댓값
    Min = min(Min,gap)

    if level==6: # 6인 팀(우리), 1인팀(상대)일 때 리턴
        return

    for i in range(start,7):
        check[i] = 1 # i를 우리팀으로 뽑음
        dfs(i+1,level+1,sum+power[i]) # 뽑은 사람을 제외하고(중족 제외) 그 뒤에서
                                      # 더 뽑을 경우를 위해 재귀 돌림
        check[i] = 0 # 원상 복구

dfs(0,0,0) # start,level,sum
print(Min)

• 백준 스타트와 링크도 비슷한 유형의 문제다.

다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 해당 알고리즘은 그림판의 채우기 기능과 지뢰 찾기 프로그램에 이용된다. 주변에 같은 성질을 가지는 셀을 모두 찾아준다는 공통점이 있다.

플러드 필은 보통 DFS(재귀)와 BFS(Queue)를 이용하여 구현한다. 이 포스팅에서는 BFS를 이용한 구현을 알아볼 것이다.

💡예시 코드

# 섬의 개수, 최대 섬의 크기, 최소 섬의 크기 구하기
from collections import deque

N = int(input())
arr = [list(input()) for _ in range(N)]
cnt = 0
Max, Min = -21e8, 21e8

dy = [0,0,1,-1]
dx = [1,-1,0,0]

def bfs(y, x):
    global Max, Min
    q = deque()
    q.append([y, x])
    arr[y][x] = '0'
    size = 1
    while q:
        node = q.popleft()
        a, b = node[0], node[1]
        for i in range(4):
            ny = dy[i] + a
            nx = dx[i] + b
            if not (0<=ny<N and 0 <=nx<N): continue
            if arr[ny][nx] == '0': continue
            arr[ny][nx] = '0'
            q.append([ny,nx])
            size += 1
    return size

for i in range(N):
    for j in range(N):
        if arr[i][j] == '1':
            cnt += 1
            result = bfs(i,j)
            Min = min(Min, result)
            Max = max(Max, result)

print(Min, Max) # 가장 작은 섬, 가장 큰 섬의 크기       
print(cnt) # 섬의 개수

'''
입력
5
01100
00010
11011
01010
10000

출력
1 4 # 최소, 최대 사이즈
4   # 섬의 개수
'''

# 최대 섬에서 최소 섬의 최단 거리 구하기 (위 문제 응용)
from collections import deque

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

cnt = 1 # 이 값으로 섬의 영역을 치환, 값이 1과 겹치지 않게 1로 시작 
Max, Min = -21e8, 21e8

dy = [0,0,1,-1]
dx = [1,-1,0,0]

def bfs(y, x, cnt): # 섬의 영역을 다른 숫자로 바꾸고, size 출력
    global arr
    q = deque()
    q.append([y, x])
    arr[y][x] = cnt
    size = 1
    while q:
        node = q.popleft()
        a, b = node[0], node[1]
        for i in range(4):
            ny = dy[i] + a
            nx = dx[i] + b
            if not (0<=ny<N and 0 <=nx<N): continue
            if arr[ny][nx] != 1: continue ## 중요
            arr[ny][nx] = cnt
            q.append([ny,nx])
            size += 1
    return size

def find_path(y, x): # Max_num이 있는 좌표까지의 최단 거리 리턴
    used = [[False]*N for _ in range(N)]
    que = deque()
    que.append([y, x, 0]) # 0은 level
    used[y][x] = True
    while que:
        a, b, level = que.popleft()
        if arr[a][b] == Max_num:
            return level
        for i in range(4):
            ny = dy[i] + a
            nx = dx[i] + b
            if not (0<=ny<N and 0 <=nx<N): continue
            if arr[ny][nx] == Min_num: continue ## 중요
            que.append([ny,nx,level+1])

for i in range(N):
    for j in range(N):
        if arr[i][j] == 1:
            cnt += 1 
            result = bfs(i,j,cnt) # 섬의 영역을 다른 숫자로 바꾸고, size 출력
            if Min > result: 
                Min = result
                Min_num = cnt # 최소 섬에 넣어준 값을 표시
            if Max < result:
                Max = result
                Max_num = cnt # 최대 섬에 넣어준 값을 표시

answer = 21e8
for i in range(N):
    for j in range(N):
        if arr[i][j] == Min_num:
            tmp = find_path(i,j)
            answer = min(answer, tmp)

print(answer)

'''
입력
5
0 1 1 0 0
0 0 0 1 0
1 1 0 1 1
0 1 0 1 0
1 0 0 0 0

출력
4
'''

💡응용 문제

# 벽(1)은 최대 두 번 부술 수 있으며 tank -> prince로 가는 최소 이동 횟수 구하기
from collections import deque

map = [
    [0,0,1,1,1,1],
    [0,0,1,0,0,1],
    [0,0,1,0,1,1],
    [0,0,1,0,1,0]
]

tank = [0,0]
prince = [3,5]

dy = [0,0,1,-1]
dx = [1,-1,0,0]

def bfs():
    q = deque()
    q.append([tank[0],tank[1],0,0]) # 마지막 두 개 level, crack
    # used = [[False]*6 for _ in range(4)]
    # used[tank[0]][tank[1]] = True

    while q:
        y, x, level, crack = q.popleft()
        if y == prince[0] and x == prince[1]: 
            break
        for i in range(4):
            ny = dy[i] + y
            nx = dx[i] + x
            if not (0<=ny<4 and 0<=nx<6): continue
            # if used[ny][nx] == True: continue

            if map[ny][nx] == 1: 
                crack += 1
                if crack <= 2:
                    # used[ny][nx] = True
                    q.append([ny,nx,level+1,crack])
            else:
                # used[ny][nx] = True
                q.append([ny,nx,level+1,crack])

    return level

print(bfs()) # 8

'''
주의 사항
used 배열을 쓰면 안되는 이유: 
경로가 여러가지 존재하는데 단순히 used 배열을 하나만 쓰면 그 경로마다 used 상태가 다른 것이 반영이 안된다. 
그래서 단순 최단 거리만 구하는 것이니까 used를 쓰지 않거나, used 배열을 queue에 append하여 상태를 존재하는 경로 별로 관리해야 한다.
'''

💡Flood Fill 활용 문제

• 백준
  • 줄 세우기
  • 작업
  • 유기농 배추
• 프로그래머스
  • FloodFill

최소 신장 트리를 찾는 데 사용되는 알고리즘 중 하나이다.

1. 신장 트리(Spanning Tree)란?

하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 예를 들어 아래와 같은 그래프 G가 있을 때, 이 그래프에서 가능한 신장 트리는 하단의 3가지 그래프이다.

모든 노드들이 연결되어 있지만 사이클이 존재해선 안된다. 이럴 때 우리는 신장 트리라고 하고, 최소 신장 트리는 간선의 가중치가 존재할 때 그 가중치들의 합이 최소가 될 때의 트리를 최소 신장 트리라고 한다. 즉, 최소 비용으로 만들 수 있는 신장 트리를 최소 신장 트리라고 한다.

2. 크루스칼 알고리즘의 동작 과정💡

• 비용을 기준으로 오름차순으로 정렬한다. (비용이 적은 것부터 연결하기 위해)
• 간선의 개수만큼 for문 돌리면서 union해준다.
  • 그룹화 할 대상이 다른 그룹이면 그룹화 해주고 비용을 더한다.
  • 이미 같은 그룹이라면 그냥 넘어간다.
  • 그룹화 성공이 (정점의 개수 - 1)이면 멈춰준다.

크루스칼 알고리즘은 그리디 알고리즘으로 분류된다. 먼저 모든 간선에 대하여 정렬을 수행한 뒤, 가장 비용이 적은 간선부터 집합에 포함시키므로, 항상 최적의 해를 보장할 수 있다.

3. 크루스칼 알고리즘의 시간 복잡도

간선의 개수가 E개일 때, O(E*log*E)의 시간 복잡도를 가진다. 왜냐하면 크루스칼 알고리즘에서 시간이 가장 오래 걸리는 부분은 간선을 정렬하는 작업이며, 이 과정의 시간 복잡도가 O(ElogE)이기 때문이다. 크루스칼 내부에서 사용되는 서로소 집합 알고리즘의 시간 복잡도는 정렬 알고리즘의 시간 복잡도보다 작으므로 무시한다.

💡구현 코드

N = int(input()) # 정점의 개수
M = int(input()) # 간선의 개수
graph = [list(input().split()) for _ in range(M)] # 간선의 정보 입력

graph.sort(key=lambda x: int(x[2]))

arr = [0]*200

def findboss(target):
    if arr[ord(target)]==0:
        return target
    ret=findboss(arr[ord(target)])
    arr[ord(target)] = ret # 최적화
    return ret

def union(x,y):
    global arr

    fx,fy = findboss(x), findboss(y)
    if fx == fy: return False         # 이미 같은 그룹일 때 그룹화 실패
    arr[ord(fy)] = fx
    return True

cnt, sum = 0, 0
for i in range(M):
    if union(graph[i][0], graph[i][1]): # 그룹화 성공
        cnt += 1
        sum += int(graph[i][2])
        if cnt >= N-1:
            break
print(sum)

'''
입력
5       #정점의개수
8       #간선의개수
C D 1   #간선의 정보 입력
A C 3
C E 5
A E 7
A B 9
B D 11
B C 14
A D 20

출력
18      #최소 비용
'''

💡크루스칼 알고리즘 활용 문제

• SWEA
  • 최소 신장 트리

각각의 독립된 데이터들을 그룹화 시켜 관리할 때 사용하는 자료구조이다. 두 그룹울 그룹화 시킬 때 각 그룹의 보스 데이터를 하나로 합친다. 그래서 임의의 두 데이터가 같은 그룹인지 아닌지를 확인할 때 각 데이터가 속한 그룹의 보스가 같은지 여부를 판단한다.

🎈Union-Find의 시간 복잡도

Union-Find의 시간 복잡도는 구하기가 꽤 까다롭다. 최적화 여부, 순서 등에 따라 매번 달라지기 때문이다. 코드를 살펴보면 전체 시간 복잡도와 Union 함수의 시간 복잡도는 Find 함수의 시간 복잡도에 따라 결정되는 것을 알 수 있다.

경로 압축 최적화를 하지 않은 경우, 트리가 한 쪽으로 치우칠 수 있기 때문에 Find 함수의 시간 복잡도는 최악의 경우O(N)이다.

경로 압축 최적화를 한 경우, 트리가 짧고 넓은 형태가 될 가능성이 높아지므로O(logN) 정도로 생각하면 된다.

실제 시간 복잡도는O(α(N))라고 한다. α(x)는 애커만 함수라고 하는데, x가 2의 65536제곱일 때 함수 값이 5가 된다. 따라서, 그냥 상수라고 봐도 무방하다.

구현 코드

arr=[0]*200 # 어떤 데이터의 보스를 저장할 배열, 데이터의 아스키 코드가 index가 된다. 

def findboss(member):
    global arr
    if arr[ord(member)]==0: # 매개변수에 해당하는 곳의 값이 0이라면
        return member       # 자기 자신이 보스!!
    ret=findboss(arr[ord(member)]) # 배열에 적혀있는 값으로 다시 보스 찾아보기
    return ret

def union(a,b):
    global arr
    aboss=findboss(a)  # boss 찾기
    bboss=findboss(b)
    if aboss == bboss:  # boss가 같다 -> 이미 같은 그룹
        return
    arr[ord(bboss)] = aboss  # 두보스가 다르다면 b의 보스를 a그룹의 보스로 만든다.

union('A','B') # 두 그룹을 하나의 그룹으로 합치는 함수
union('D','E') 
union('B','E')
union('B','D')
union('F','E')

y,x=input().split()

if findboss(y)==findboss(x): # 같은 그룹 여부를 print
    print("같은그룹")
else: print("다른그룹")

# union find 자료구조를 이용하여 양방향 그래프에서의 cycle 존재여부 확인

n=int(input())
edge=[]
for _ in range(n):
    edge.append(input().split()) 

arr=[0]*200

def findboss(member):
    global arr
    if arr[ord(member)] == 0:
        return member
    ret=findboss(arr[ord(member)])
    arr[ord(member)] = ret             # 경로 압축(Path Compression)
    return ret

# union 함수
def union(a,b):
    global arr

    fa,fb=findboss(a),findboss(b)
    if fa==fb: return 1                # 같은 그룹이면 return 1 (사이클 완성)
    arr[ord(fb)]=fa

answer=0
for i in range(n):
    a,b=edge[i]
    ret=union(a,b)
    if ret==1:
        answer=1
        break
if answer: print("cycle 발견")
else: print("cycle 미발견")

# 입력
# A B
# C D
# B C
# A E

# 출력
# cycle 발견

💡Union-Find 활용 문제

• 민코딩
  • Minco 스테이크 하우스
  • 춘추 전국 시대
• SWEA
  • 그룹 나누기

이진 탐색 트리란 다음과 같은 속성을 만족하는 이진 트리 자료구조이다.

• 각 노드에 중복되지 않는 값이 있다.
• 한 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들을 가진 노드들로 이루어져 있다.
• 한 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들을 가진 노드들로 이루어져 있다.
• 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.

이진 탐색 트리(BST)의 등장 배경

이진 탐색 : 탐색 시간복잡도 O(logN), 삽입이나 삭제 불가능 연결 리스트 : 탐색 시간복잡도 O(N), 삽입이나 삭제 시 O(1) 소요

이 둘의 장점을 챙긴 자료구조가 이진 탐색 트리이다. 탐색 시 O(logN)의 시간복잡도를 가지며, 자료의 삽입과 삭제도 가능한 자료구조이다.

💡이진 탐색 트리(BST)의 시간 복잡도

빅오 표기법을 기준으로, 만약 타겟 노드가 가장 깊은 레벨에 있다고 하면 높이(h)만큼의 노드를 탐색해야한다.

모든 노드가 빈 자리 없이 채워져 있는 이진 탐색 트리를 포화 이진 탐색 트리라고 하는데, 이렇게 트리가 구성되어있는 경우가 가장 최적의 상황이다. 이 때 노드의 개수를 n이라고 하면

$$ n=2h−1 $$

$$ 2h=n−1 $$

$$ h=log(n−1) $$

$$ O(h)=O(log(n−1))=>O(logn) $$

이렇게 되므로 시간복잡도는 O(logn)이 된다.

💡이진 탐색 트리(BST)의 구현

이진 탐색 트리는 간단하게는 1차원 배열로도 표현할 수 있다.

현재 노드의 값과 비교했을 때 삽입되어야 하는 값이 더 작으면 현재 노드의 index에 2를 곱한 곳으로 이동하여 다시 삽입을 시도한다. 더 크면 현재 노드의 index에 2를 곱하여 1을 더한 곳으로 이동하여 시도한다.

BST=[0]*20 # 충분히 길어야할 것
lst=[4,2,9,7,15,1,3] # 트리에 하나씩 삽입될 값들

# tree에 값을 삽입하는 매서드
def insert(target):
    now = 1 # 루트 노드는 0이 아니라 1부터 저장 (index)
    while True:
        if BST[now] == 0:
            BST[now] = target
            return
        if BST[now] < target: now = now*2+1 # target이 현재 노드 값보다 클 때
        else: now = now*2                   # target이 현재 노드 값보다 작을 때

# bst에 특정 값의 존재 여부를 판단하는 매서드
def search(target):
    now = 1
    while True:
        if now >= len(BST): return False  # 배열범위 벗어날 경우
        if BST[now] == 0: return False # 찾고자 하는 값이 없을경우
        if BST[now] == target: return True # 찾았을 경우

        if BST[now] < target: now = now*2+1
        else: now = now*2

# 리스트의 값들을 tree에 저장
for i in range(len(lst)):
    insert(lst[i])

n=int(input())   # 숫자 하나 입력받고
answer=search(n)    # 입력받은 숫자가 존재하는지 search하는 함수
if answer: print("존재")
else: print("존재하지 않음")

BST 심화 구현

BST는 클래스를 정의하여 구현할 수도 있다. 아래 링크를 참고하면 좋다.

[자료구조/Data Structure] 파이썬으로 이진 탐색 트리(Binary Search Tree) 자료구조 알아보기

DFS와 함께 대표적인 그래프 탐색 알고리즘이다. BFS는 넓이 우선 탐색(Breadth First Search)이라는 알고리즘이며, 정점에서 가까운 노드부터 우선적으로 탐색한다.

• BFS는 Queue라는 자료구조를 이용하여 구현할 수 있다.
  • 탐색 시작 노드를 Queue에 삽입하고 방문 처리를 한다.
  • Queue에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에 방문하지 않은 노드들을 모두 Queue에 삽입하고, 방문 처리 해준다.
  • Queue에 남은 요소가 없을 때까지 반복해준다.

# 순회 경로 출력 (인접 행렬)
from collections import deque

def bfs(start_node):
    queue = deque([start_node])
    used = [False] * 4
    used[start_node] = True

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for i in range(len(arr[node])):
            if arr[node][i] == 1:
                if used[i] == False:
                    used[i] = True
                    queue.append(i)
arr = [
    [0, 1, 1, 0],
    [0, 0, 1, 1],
    [0, 0, 0, 1],
    [0, 0, 0, 0]
]

bfs(0)

# 순회 경로 출력 (인접 행렬)
from collections import deque

# BFS 함수 정의
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 = [
  [1,2],
  [2, 3],
  [3],
  []
]

# 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = [False] * 9
bfs(graph, 0, visited)

• BFS 알고리즘 문제💡
  • 백준 스타트링크
  • 백준 아기상어2

대표적인 그래프 탐색 알고리즘이다. DFS는 깊이 우선 탐색(Depth First Search)이라는 알고리즘이며, 정점의 자식을 먼저 탐색하는 방식이다.

위의 그래프를 DFS 방식으로 순회하면 A - B -D - E - F - C - G - H - I - J 순으로 돌게 된다.

그래프(Graph)란?

그래프(Graph)란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조이다. 그래프는 정점(vertex)과 간선(edge)들의 집합으로 구성된다.

1. 인접 행렬을 이용한 그래프 구현

그래프의 정점을 2차원 배열로 만든 것이다. 정점의 개수가 N개라면 N*N 형태의 2차원 배열로 나태낸다. 행과 열은 정점을 의미하고 각 원소들은 정점 간의 간선의 유무(또는 가중치)를 나타낸다.

• 단점
  • 간선의 수와 무관하게 항상 N^2 크기의 2차원 배열이 필요하므로 메모리 공간이 낭비된다.
  • 인접 행렬 전체를 확인할 때 O(n²)의 시간이 소요된다.

2. 인접 리스트를 이용한 그래프 구현

그래프의 각 정점에 인접한 정점들을 연결리스트(Linked List)로 표현하는 방법이다. 즉 정점의 개수만큼 인접 리스트가 존재하며, 각각의 인접 리스트에는 인접한 정점 정보가 저장되는 것이다. 그래프는 각 인접 리스트에 대한 헤드포인터를 배열로 갖는다.

무방향 그래프의 경우 간선이 추가되면 각각의 정점의 인접 리스트에 반대편 정점의 노드를 추가해야 한다.

• 장점
  • 존재하는 간선만 관리하면 되므로 메모리 사용 측면에서 인접 행렬보다 효율적이다.
  • 모든 인접 리스트를 탐색할 때 O(n+e)의 시간이 소요된다.
• 단점
  • 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하므로 정점의 차수만큼의 시간이 필요하다. O(degree(v))
  • 구현이 비교적 어렵다.

이미지 출처 : https://kingpodo.tistory.com/46

💡DFS의 구현

1. 재귀 함수로 구현

# 0,0 -> 3,3까지 가는 길이 존재하는지 안하는지를 출력

arr=[[0,0,0,0],
     [1,0,1,0],
     [1,0,1,0],
     [0,0,0,0]]  # 0=>길 and 1=>벽
visit=[[0]*4 for _ in range(4)]   # 중복 방지
flag=0 # 도착시 1로 바꿀 예정

def dfs(y,x):
    global flag
    if y==3 and x==3:
        flag=1
        return

    directy=[-1,1,0,0]
    directx=[0,0,-1,1]
    for i in range(4):
         dy=y+directy[i]
         dx=x+directx[i]
         if dy<0 or dx<0 or dy>3 or dx>3: continue  # 배열 범위 벗어나면 안됨
         if visit[dy][dx]==1: continue              # 이미 방문했던 곳이면 안됨
         if arr[dy][dx]==1: continue                # 벽이면 못감
         visit[dy][dx]=1
         dfs(dy,dx)

visit[0][0]=1
dfs(0,0)    # y,x 좌표값
if flag==1:
    print("갈수있습니다.")
else:
    print("도착할수 없습니다.")

# 0,0 -> 1,3 좌표까지 최소 이동 횟수 출력

arr=[[0,0,0,0,1],
     [1,0,1,0,1],
     [1,0,1,0,1],
     [0,0,0,0,0]]
visit=[[0] * 5 for _ in range(4)]

Min=int(21e8)
def dfs(y,x,level):

    global Min
    if y==1 and x==3:
        if level<Min:# 최소레벨 갱신
            Min=level
        return
    directy=[-1,1,0,0]
    directx=[0,0,-1,1]

    for i in range(4):
        dy=y+directy[i]
        dx=x+directx[i]

        if dy<0 or dx<0 or dy>3 or dx>4: continue
        if arr[dy][dx]==1: continue
        if visit[dy][dx]==1: continue

        visit[dy][dx]=1
        dfs(dy,dx,level+1)
        visit[dy][dx]=0

visit[0][0]=1
dfs(0,0,0)  # y,x level-> 이동횟수

print(Min)

2. Stack으로 구현

from collections import deque # deque 패키지 불러오기

def dfs2(graph, start_node):

    visited = []
    need_visited = deque()

    #시작 노드 설정해주기
    need_visited.append(start_node)

    # 방문이 필요한 리스트가 아직 존재한다면
    while need_visited:
        # 시작 노드를 지정하고
        node = need_visited.pop()

        #만약 방문한 리스트에 없다면
        if node not in visited:

            # 방문 리스트에 노드를 추가
            visited.append(node)
            # 인접 노드들을 방문 예정 리스트에 추가
            need_visited.extend(graph[node])

    return visited

def dfs(start_node):
    stack = [start_node]
    used = []

    while stack:
        node = stack.pop()
        if node not in used:
            used.append(node)
            for i in range(len(arr[node])-1, -1, -1):
                if arr[node][i] == 1:
                    stack.append(i)
    print(used)

arr = [
    [0, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0]
]

dfs(0)

🎈 stack을 구현할 때 list로 구현하는 것 보다 deque로 구현하는 것이 훨씬 성능면에서 좋다!

DFS 심화 문제

• 프로그래머스 - 여행경로

순열이란 서로 다른 n개 중 r개를 뽑아 그룹을 만드는 가짓수를 말한다. nCr로 표시한다. 사실 순열은 itertools를 이용하면 쉽게 구현할 수 있다. (아래 링크 참고)

[알고리즘] 재귀-순열(Permutation), 백트래킹(Backtracking)

1. 일반 조합

# 4개의 원소 중에 3개를 중복, 순서 없이 뽑는 경우의 수

# 1. 매개변수 1개만 사용
arr=['a','b','c','d']
path=['']*3

def abc(level):
    if level==3:
        print(*path)
        return

    for i in range(4):
        #1 path[level-1] -> 그전 단계에서 타고 들어온 곳
        #2 arr[i] -> 앞으로 들어갈 가지
        #3 그전 들어온 가지 < 앞으로 들어갈 가지  (True)
        if level > 0 and path[level-1] >= arr[i]: continue
        path[level]=arr[i]
        abc(level+1)

abc(0)

# 2. 매개변수 2개 사용 
arr=['a','b','c','d']
path=['']*3

def abc(level,start):
    if level==3:
        print(*path)
        return

    for i in range(start,4):
        path[level]=arr[i]
        abc(level+1,i+1)

abc(0,0)  #level start

출력
a b c
a b d
a c d
b c d

1. 중복 조합

# 4개의 원소 중에 3개를 순서 없이 뽑는 경우의 수 (중복 가능)
arr=['a','b','c','d']
path=['']*3

def abc(level,start):
    if level==3:
        print(*path)
        return

    for i in range(start,4):
        path[level]=arr[i]
        abc(level+1,i) # aad -> abb로 넘어가는 로직 이해를 확실히 하자!(조합)

abc(0,0)  #level start

• 조합을 활용한 문제💡
  • 백준 N과 M (3)
  • 백준 암호 만들기

순열이란 서로 다른 n개 중 r개를 골라 순서를 고려해 나열하는 가짓수를 말한다. nPr로 표시한다. 사실 순열은 itertools를 이용하면 쉽게 구현할 수 있다. 하지만 재귀로 직접 구현하는 방법을 알아보고자 한다. (itertools를 사용하여 구현하는 방법은 포스팅 마지막에 남기겠다.)

1. 중복 순열

# 중복 순열
# 주사위를 N번 던졌을 때 모든 경로 출력

dice = [1,2,3,4,5,6] # br
N = int(input())
path = [0]*N

def abc(level):
    if level == N: # N까지 뽑았으면 스탑
        print(*path, end = '\n')
        return
    for i in range(6): # 주사위 숫자 종류
        path[level] = dice[i]
        abc(level+1)
abc(0)

1. 일반 순열(중복 제외)

# A,B,C,D중에서 금,은,동메달 받을 사람 뽑는 경우의수

arr = ['A','B','C','D'] # br
path = [0]*3
used = [0]*4 # br의 개수 만큼 만들기, 중복 방지위해 만듦

def abc(level):
    if level == 3:
        print(*path)
        return 
    for i in range(4):
        if used[i] == 0: # 중복 방지
            path[level]=arr[i]
            used[i] = 1
            abc(level+1)
            used[i] = 0 # 재귀 탈출하면 돌려줌
abc(0)

# 배열 하나로 순열 만드는 법
p = list('ABCDE')

def perm(n, k): # n: 선택된 원소의 개수, k: 총 원소의 개수
    if n == k: # 배치가 다 되었을  때 print
        print(p)
        return
    for i in range(n, k): # index n앞의 숫자들을 이미 배치된 숫자, 그러므로 index n뒤의 숫자들과 자리를 바꿔가며 배치해야 함
        p[n], p[i] = p[i], p[n]
        perm(n+1, k)
        p[n], p[i] = p[i], p[n] # 원상복구

perm(0, 5)

💡 백트래킹(Backtracking)

완전 탐색 알고리즘에서 불필요한 분기(Branch) 를 가지치기(Pruning) 하는 것이다. 정답을 도출하기 전 탐색 과정 중에 정답이 될 수 없는 조건에 해당된다면 제외하여 효율을 높일 수 있다.

순열을 구하는 과정에서도 정답에 특정 조건이 붙어 모든 경우의 수를 구하는 경우가 아닐 때 백트래킹(Backtracking)을 이용해 효율을 높일 수 있다.

1. ABCD 중에 C로 시작하는 경우 제외, 3개를 중복 가능하게 뽑기

candidates=['A','B','C','D']
path=['']*3

def abc(level):
    if level==1 and path[level-1]=='C': return # 진입 후에 제외

    if level==3:
        print(*path)
        return

    for i in range(4):
        #if level==0 and candidates[i]=='C': continue # 진입 전에 제외
        path[level]=candidates[i]
        abc(level+1)

abc(0)

1. ABCD 중에 B는 모든 경우에서 제외, 3개를 중복 가능하게 뽑기

candidates=['A','B','C','D']
path=['']*3

def abc(level):
    #if level > 0 and path[level-1]=='B': return # B 진입 후에 제외
    if level == 3:
        print(*path)
        return
    for i in range(4):
        if i==1: continue # B 진입 전에 제외
        path[level]=candidates[i]
        abc(level+1)

abc(0)

1. ABCD 중에 연속해서 2장의 카드가 나오면 제외, 3개를 중복 가능하게 뽑기

candidates=['A','B','C','D']
path=['']*3

def abc(level):
    # if level > 1 and path[level-1] == path[level-2]: return # 진입 후에 제외
    if level==3:
        print(*path)
        return
    for i in range(4):
        if level > 0 and (path[level-1] == candidates[i]):continue # 진입 전에 제외
        path[level]=candidates[i]
        abc(level+1)

abc(0)

🎈 itertools를 이용하여 순열, 조합 구현하기

itertools를 이용하여 순열과 조합을 구현하면, 직접 구현한 것보다 시간이 10배 정도 덜 걸린다.

1. 순열

    import itertools

    arr = ['A', 'B', 'C']
    result = itertools.permutations(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
    print(list(result))

    # [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

2. 중복 순열

    from itertools import product

    arr = ['A', 'B', 'C']
    result = product(arr, arr, [1, 2]) # 반복 가능한 객체, 반복 가능한 객체, ..
    print(list(result))

    # [('A', 'A', 1), ('A', 'A', 2), ('A', 'B', 1), ('A', 'B', 2), ('A', 'C', 1), ('A', 'C', 2), ('B', 'A', 1), ('B', 'A', 2), ('B', 'B', 1), ('B', 'B', 2), ('B', 'C', 1), ('B', 'C', 2), ('C', 'A', 1), ('C', 'A', 2), ('C', 'B', 1), ('C', 'B', 2), ('C', 'C', 1), ('C', 'C', 2)]

    from itertools import product

    result = product([1,2,3], repeat=2) # 반복 가능한 객체, repeat=n (n번 반복)
    print(list(result))

    # [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

3. 조합

    import itertools

    arr = ['A', 'B', 'C']
    result = itertools.combinations(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
    print(list(result))

    # [('A', 'B'), ('A', 'C'), ('B', 'C')]

4. 중복 조합

    from itertools import combinations_with_replacement

    arr = ['A', 'B', 'C', 'D']
    result = combinations_with_replacement(arr, 2) # 반복 가능한 객체, r = 뽑는 개수
    print(list(result))

    # [('A', 'A'), ('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'C'), ('C', 'D'), ('D', 'D')]

재귀함수는 정의 단계에서 자신을 재참조하는 함수를 뜻한다. 재귀함수는 재귀가 모두 실행되어 끝나거나, 특정 브레이크 포인트를 만날 때까지 계속해서 실행되는데, 만약 브레이크 포인트를 제대로 설정하지 않으면 무한루프의 늪에 빠질 수도 있다. 함수가 무한대로 실행되면 스택 오버 플로우 문제가 발생하게 된다.

재귀함수 구현 시 고려사항

1. branch와 level을 고려한다.

   branch는 하나의 재귀 함수에서 뻗어나가는 가지의 개수를 의미하고, level은 들어가고 싶은 마지막 깊이를 의미한다. return을 어느 단계에서 할지 같이 고민하면 좋다.

2. 매개 변수를 고려한다.

   sum, level, now등 어떤 변수를 매개변수로 가져갈지 고려해야 한다. 전역으로 뒀을 때 편한 것과 매개변수로 뒀을 때 편한 것을 구분하여 사용한다.

3. visited 배열의 사용 유무와 원상 복구를 고려한다. 중복을 제거해야할 경우 visited 배열으로 방문 처리를 해줘야 한다. 그리고 재귀 함수 들어가기 전에 변경했던 값을 재귀가 끝나고 다시 돌아오는 경우에 원래의 상태로 되돌려 놔야 하는지 아닌지는 문제에 따라 다르므로 이를 고려하여 설계해야 한다.

# 재귀 함수로 리스트의 누적합 구하기
# 출력: 3 7 12 13 19 28

arr=[3,4,5,1,6,9]

# 1. 전역 변수 사용
sum = arr[0]
def abc(level):
    global sum
    if level == len(arr)-1: # 마지막 인덱스가 되면 sum 출력
        print(sum)
        return
    print(sum)
    sum+=arr[level+1]
    abc(level+1)

abc(0)

# 2. 지역 변수 사용
def abc(level,sum):
    if level == len(arr)-1: # 마지막 인덱스가 되면 sum 출력
        print(sum)
        return
    print(sum)
    abc(level+1,sum+arr[level+1])

abc(0,arr[0]) # level sum

# 거꾸로 누적합 구하기
# 출력: 28 19 13 12 7 3

# 전역
arr=[3,4,5,1,6,9]

def abc(level,sum):
    if level==len(arr)-1:
        print(sum)
        return
    abc(level+1,sum+arr[level+1])
    print(sum)

abc(0,arr[0])

# 지역
sum=arr[0]
def abc(level):
    global sum
    if level==len(arr)-1:
        print(sum)
        return
    sum+=arr[level+1]
    abc(level+1)
    sum-=arr[level+1]
    print(sum)

abc(0)

# 3개의 카드 묶음에서 1장씩 뽑았을때
# 나올 수 있는 모든 합들을 출력해 주세요

arr=[3,7,1,5] # 카드의 종류, 카드의 개수는 많음
# lv=3 (3장)
# br=4 (카드의 종류)

# 1. 전역
sum=0
def abc(level):
    global sum
    if level==3:
        print(sum, end=' ')
        return
    for i in range(4):
        sum+=arr[i]
        abc(level+1)
        sum-=arr[i] # 재귀 탈출하면 그 다음 가지를 위해 다시 빼줌

abc(0) # level

# 2. 매개

def abc(level,sum):
    if level==3:
        print(sum,end=' ')
        return
    for i in range(4):
        abc(level+1,sum+arr[i])

abc(0,0) # level sum

🎈 동전의 최소 개수

# 거스름돈 돌려둘 때 동전 개수의 최소
coin = [100,70,10] # 동전 종류

N = int(input()) # 거슬러야 할 돈
min_cnt = int(21e8)

def abc(N, cnt):
    global min_cnt
    if N < 0: # 가격이 안 맞으면 그냥 리턴
        return
    if N == 0: # 가격이 맞을 때 최소 갱신
        if min_cnt > cnt:
            min_cnt = cnt
        return
    for i in range(3):
        abc(N - coin[i], cnt+1)

abc(N, 0)

print(min_cnt)

슬라이딩 윈도우는 일정한 길이의 범위를 이동하여 조건에 맞는 값을 찾는 알고리즘이다. 한 칸씩 이동 하기 때문에 공통된 부분은 유지하고 처음과 끝 원소만 갱신하여 유용하게 사용할 수 있다.

• 일정 길이 최댓값을 구하는 함수

n,m=map(int,input().split())   # n: 입력받을 정수의 개수, m: 연속된 구간의 크기 (10, 5)
arr=list(map(int,input().split()))

Max,sum=0,0

for i in range(m): # 처음 m개의 구간 (0번 인덱스부터 4번인덱스)의 합 구하기
    sum+=arr[i]

for i in range(n-m+1): 
    if sum>Max:
        Max=sum
    if i==n-m: break
    sum+=arr[i+m] # i+m: 5~10
    sum-=arr[i]   # i: 0~5

print(Max)

• 일정 길이 최솟값을 구하는 함수

# 비효율적인 방법
def minArray(nums, k):
    result = sum(nums[0:k])
    for i in range(1, len(nums)-(k-1)):
        r = sum(nums[i:i+k])
        if r < result:
            result = r
    return result

# 슬라이딩 윈도우
def minSlidingWindow(nums, k):
    min_sum = 9999
    window_sum = 0
    start = 0

    for end in range(len(nums)):
        window_sum += nums[end]

        if end >= k - 1:
            # 0~k-1 까지 더한 값이 최소값보다 작다면, 최소값을 갱신
            if window_sum <= min_sum:
                min_sum = window_sum

            # 윈도우에 포함된 맨 앞자리 수를 제거
            window_sum -= nums[start]
            # 윈도우 시작 인덱스를 하나 증가
            start += 1
    return min_sum

💡투 포인터(Two pointer)란?

투 포인터는 데이터에 순차적으로 접근해야 할 때 두 개의 점 위치를 조절하여 조건에 부합하는지 판단하는 알고리즘이다. 공통 부분을 제외하고 포인터로 이동하는 원소의 처리만 하면 되므로 유용하게 쓰일 수 있다.

• 특정한 합을 가지는 부분 연속 수열의 개수를 구하는 알고리즘

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

cnt, sum = 0, 0
high, low = 0, 0
while(1):
    if sum > target:        # 합이 타겟보다 크면
        sum -= arr[low]     # sum에서 뺴고
        low += 1            # low 의 index를 1증가
    elif high == n: break
    else:
        sum+=arr[high]      # 합이 타겟보다 작거나 같다면
        high+=1             # sum에 더하고 high의 인덱스를 1증가
    if sum==target:
        cnt+=1
print(cnt)

• 백준 2003번, 수들의 합 2

범위가 매우 크기 때문에 2중 포문으로 풀면 런타임 에러가 난다. 그러므로 투 포인터를 활용하여 풀이해야 한다.

# 시간 초과가 나는 코드
def not_tow_pointer(nums):
    count = 0
    for i in range(N):
        for j in range(i, N):
            r = sum(nums[i:j+1])

            if r == M:
                count += 1

    print(count)

# 투포인터
def two_pointer(nums):
    count = 0
    start, end = 0, 0

    window_sum = nums[start]
    while start < N:
        if window_sum == M:
            count += 1
            window_sum -= nums[start]
            start += 1
        elif window_sum < M:
            end += 1
            if end >= N:
                break
            window_sum += nums[end]
        else:
            window_sum -= nums[start]
            start += 1
        print(f'start = {start} / end = {end}')

Parametric search는 이분(이진) 탐색과 매우 유사하다. Parametric search란 쉽게 말해서, 최적화 문제를 결정 문제로 변형하여 이분(이진) 탐색을 통해 해결하는 것을 말한다.

• Parametric search 적용 조건
  • 최적화된 값을 요구하는 문제
  • 특정 조건을 만족하는 최댓값/최솟값을 구하는 형식의 문제
  • 조건을 만족하는 최댓값을 구했을 경우 그 값보다 작은 값은 모두 조건을 민족해야 한다.

Parametric search 문제

• 커서의 위치 찾기

# 워드작업 중 정전으로 인하여 컴퓨터가 강제로 종료가 되었습니다.
# 다시 전기가 들어어 컴퓨터를 켰더니 다행이도 자동복구가 실행 되었습니다.
# 우리는 자동복구가 되었을때 커서의 위치가 어디인지를 알려줘야 합니다.
# 커서의 위치를 알려주는 프로그래밍을 완성해 주세요.
# 시간복잡도 (On^2)보다 빨라야 합니다.

curser = [ # '#'이 존재하는 최대 위치 찾기
    '##########',
    '##########',
    '##########',
    '##________',
    '__________'
]

def parametric_search(start, end, arr):
    max = 0 
    while (True): # 이진 탐색을 활용
        mid = (start + end) // 2
        if start > end:
            break
        if arr[mid] == '#':
            max = mid
            start = mid + 1

        elif arr[mid] == '_':
            end = mid - 1
    return max   

newls=[s[0] for s in curser]

x_idx=parametric_search(0,len(newls)-1, newls)

y_idx=parametric_search(0,len(curser[x_idx])-1,curser[x_idx])

print(x_idx,y_idx)

• 백준
  • 랜선 자르기
  • 기타 레슨
  • 반도체 설계

이진 탐색 알고리즘이란 정렬된 데이터 내에서 특정 값을 검색할 때 탐색 범위를 절반씩 좁혀가며 탐색하는 알고리즘이다. 탐색 범위가 반씩 줄어들기 때문에 O(logN)의 시간복잡도를 가진다. 단, 정렬된 데이터에서만 쓸 수 있다는 단점이 있다.

def binary_search(st,ed,value): # 시작, 끝, 찾을 값
    while (1):
        mid=(st+ed)//2          # mid
        if arr[mid]==value:     # mid가 target과 같을 경우
            return 1
        elif arr[mid] > value:  # mid가 클 경우
            ed=mid-1
        elif arr[mid]<value:    # mid가 작을 경우
            st=mid+1
        if st>ed:               # 종료 조건
            return 0

n=int(input())
arr=list(map(int,input().split())) #배열 입력
target=int(input()) # 찾을 값

arr.sort() # 정렬
flag = binary_search(0,n-1,target)
if flag:
    print("찾음")
else:
    print("없는숫자")

• 필요한 변수
  • start: 탐색 범위의 처음
  • end: 탐색 범위의 끝
  • mid: 탐색 범위의 중간
• 종료 조건
  • end < start: 검색에 실패할 경우
  • arr[mid] == target: 검색에 성공할 경우
• 시간 복잡도(Time complexity)
  • Best: O(1) / Average: O(logN) / Worst: O(logN)

Python bisect 라이브러리

Python에는 이진 탐색을 쉽게 사용할 수 있는 라이브러리가 존재한다.

• bisect_left(a, x)
  • 정렬을 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 반환한다.
• bisect_right(a, x)
  • 정렬을 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 반환한다.

from bisect import bisect_left, bisect_right

a = [0,1,2,3,4,5,6,7,8,9]
x = 5

print(bisect_left(a, x)) # 5
print(bisect_right(a, x)) # 6