the-ze

Sliding Window(슬라이딩 윈도우) 알고리즘은 배열이나 리스트의 일정 범위의 요소를 '창'으로 생각하고, 이 창을 배열이나 리스트의 끝까지 이동시키면서 주어진 문제의 조건에 맞는 최적의 해를 찾는 방식이다. 이 알고리즘은 특히 연속된 데이터에 대해 최대합, 최소값, 평균 등을 효율적으로 계산할 때 유용하다.

슬라이딩 윈도우를 구현할 때에는 윈도우의 크기를 결정하고, 배열의 시작 부분에 윈도우를 위치시킨 뒤, 윈도우를 한 칸씩 오른쪽으로 이동시키면서, 윈도우에 포함된 요소들을 이용해 문제를 해결한다.

각 이동마다 최적의 해를 찾거나 조건을 만족하는지 검사하고, 필요한 경우 해를 갱신해야 한다.

윈도우를 한 번만 순회하므로, 알고리즘의 시간 복잡도는 대체로 O(n)이다. 데이터 스트림과 같이 동적으로 변하는 연속된 데이터에 대해서도 실시간으로 최적의 해를 찾는 데 적합하다.

def max_sum_subarray_of_size_k(arr, k):
    max_sum = 0
    window_sum = sum(arr[:k])  # 초기 윈도우의 합을 계산
    max_sum = window_sum

    for i in range(len(arr) - k):
        window_sum = window_sum - arr[i] + arr[i + k]  # 윈도우를 한 칸씩 오른쪽으로 이동
        max_sum = max(max_sum, window_sum)  # 최대 합 갱신

    return max_sum

arr = [1, 15, 1, 2, 6, 12, 5, 7]
k = 4
print(max_sum_subarray_of_size_k(arr, k))

#출력
#30

투 포인터(Two Pointers) 알고리즘은 배열이나 리스트에서 두 개의 포인터를 이용하여 문제를 해결하는 방법이다. 주로 정렬된 배열에서 두 요소의 합, 최대값 또는 최소값을 찾거나, 특정 조건을 만족하는 부분 배열을 탐색하는 데 유용하다. 대부분의 경우 선형 시간 안에 해를 찾는다.

배열의 시작점에 두 포인터를 위치시킨다. 보통 한 포인터는 배열의 시작점에, 다른 하나는 끝점에 위치시킨다. 주어진 조건에 따라 포인터들을 적절히 이동시키면서 문제의 해를 찾는다.

• 합이 특정 값보다 작을 때는 시작 포인터를 오른쪽으로 이동시켜 합을 증가시킨다.
• 합이 특정 값보다 클 때는 끝 포인터를 왼쪽으로 이동시켜 합을 감소시킨다.

중첩 반복문을 사용하지 않아 시간 복잡도가 O(n^2)에서 O(n)으로 줄어든다.

def two_sum(arr, target):
    left, right = 0, len(arr) - 1  # 초기화

    while left < right:
        current_sum = arr[left] + arr[right]

        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return None

arr = [1, 2, 3, 4, 5]
target = 9
print(two_sum(arr, target))

# 출력
# (3,4)

LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 시퀀스(예: 문자열, 리스트 등)에서 순서를 변경하지 않고 양쪽 시퀀스에서 모두 찾아낼 수 있는 가장 긴 부분 수열을 찾는 문제다. 이 문제는 다이나믹 프로그래밍(dynamic programming) 기법을 이용하여 효율적으로 해결할 수 있다.

LCS 문제를 해결하는 기본 아이디어는 두 시퀀스의 각 위치에 대해, 해당 위치까지의 최장 공통 부분 수열의 길이를 저장하는 2차원 배열(또는 테이블)을 만드는 것이다. 이 배열을 dp라 할 때, dp[i][j]는 첫 번째 시퀀스의 i번째 원소와 두 번째 시퀀스의 j번째 원소까지 고려했을 때의 최장 공통 부분 수열의 길이를 나타낸다.

dp 배열의 모든 값을 0으로 초기화한다. 여기서 dp[0][j]와 dp[i][0]은 첫 번째 시퀀스 또는 두 번째 시퀀스의 원소가 하나도 없을 때를 의미하므로, 공통 부분 수열의 길이는 0이다.

• 만약 현재 위치의 원소가 같다면, dp[i][j] = dp[i-1][j-1] + 1로 설정한다. 이는 현재 원소가 공통 부분 수열에 포함되므로, 이전 위치까지의 최장 길이에 1을 추가한 것이다.
• 만약 현재 위치의 원소가 다르다면, dp[i][j] = max(dp[i-1][j], dp[i][j-1])로 설정한다. 이는 현재 원소를 제외하고, 이전 위치에서의 최장 공통 부분 수열의 길이를 가져오는 것이다.

dp 배열의 마지막 원소인 dp[n][m]이 두 시퀀스의 최장 공통 부분 수열의 길이를 나타낸다. 여기서 n과 m은 각각 두 시퀀스의 길이다.

LCS 문제는 컴퓨터 과학뿐만 아니라, 생물 정보학에서 유전자 시퀀스 비교나 텍스트 편집 거리 계산 등 다양한 분야에서 응용된다.

def lcs(X, Y):
    # 두 문자열의 길이 계산
    m, n = len(X), len(Y)

    # dp 테이블 초기화 (m+1)x(n+1) 크기
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # dp 테이블 채우기
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i-1] == Y[j-1]:  # 현재 문자가 서로 같은 경우
                dp[i][j] = dp[i-1][j-1] + 1
            else:  # 현재 문자가 서로 다른 경우
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]  # 테이블의 마지막 값이 최장 공통 부분 수열의 길이

X = "GXTXAYB"
Y = "AGGTAB"
print(f"LCS length: {lcs(X, Y)}")

#출력
#LCS length: 4
#(GTAB로 4이기 때문)

Knapsack 문제는 조합 최적화(Combinatorial Optimization)의 대표적인 예로, 특정한 제약 조건 하에서 최적의 해를 찾는 문제다. 이 문제는 배낭에 넣을 수 있는 물건들이 주어졌을 때, 물건의 무게 제한을 초과하지 않으면서 가치의 합을 최대화하는 방법을 찾는 것이다. Knapsack 문제에는 여러 변형이 있지만, 가장 널리 알려진 형태는 0-1 Knapsack 문제와 Fractional Knapsack(분할 가능 배낭) 문제다.

0-1 배낭 문제에서는 각 물건을 통째로 넣거나 아예 넣지 않아야 한다.(분할 불가)

• n개의 아이템이 있으며, 각 아이템은 가치(value)와 무게(weight)를 가진다.
• 최대 무게가 W인 배낭이 있다.
• 배낭의 무게 한도를 초과하지 않으면서 가치의 합을 최대화하려면 어떤 아이템을 배낭에 넣어야 하는가?

분할 가능 배낭 문제에서는 물건을 부분적으로 나누어 넣을 수 있다. 이는 그리디 알고리즘을 사용해 해결할 수 있으며, 아이템의 가치 대비 무게(가치/무게 비율)를 기준으로 선택한다.

0-1 배낭 문제는 다이나믹 프로그래밍을 사용해 효율적으로 해결할 수 있다. 핵심 아이디어는 두 가지 선택지가 있을 때 최적의 선택을 결정하는 것이다: 아이템을 배낭에 추가하거나 추가하지 않는다. 다이나믹 프로그래밍 접근 방식에서는 이러한 결정을 기반으로 값을 메모하여, 반복 계산을 줄인다.

1. (n+1)x(W+1) 크기의 테이블을 0으로 초기화한다. 여기서 n은 아이템 수, W는 배낭의 최대 무게다.
2. 각 아이템에 대해, 가능한 모든 무게에 대해 최대 가치를 계산하여 dp 테이블을 채운다.
3. dp 테이블의 마지막 값(dp[n][W])은 주어진 무게 한도에서 얻을 수 있는 최대 가치다.

예를 들어, 배낭의 최대 무게가 50이고, 다음 3개의 아이템이 있을 때의 최적의 해를 찾는다고 가정하자.

• 아이템 1: 무게 10, 가치 60
• 아이템 2: 무게 20, 가치 100
• 아이템 3: 무게 30, 가치 120

0-1 배낭 문제의 해결책은 이 아이템들 중에서 선택하여 최대 가치를 얻는 조합을 찾는 것이다.

Knapsack 문제는 그 해결 방법이 명확하고, 다양한 실생활 문제에 응용될 수 있는 대표적인 최적화 문제 중 하나다.

def knapsack(W, wt, val, n):
    """
    :param W: int 배낭의 최대 무게
    :param wt: list 아이템의 무게 리스트
    :param val: list 아이템의 가치 리스트
    :param n: int 아이템의 총 개수
    :return: int 최대 가치
    """
    # 기본적으로 0으로 초기화된 DP 테이블 생성
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]
    
    # DP 테이블을 채워나감
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i-1] <= w:
                # i번째 아이템을 포함시킬 경우와 포함시키지 않을 경우 중 최대 가치 선택
                K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w])
            else:
                # i번째 아이템을 포함시킬 수 없는 경우
                K[i][w] = K[i-1][w]

    return K[n][W]  # 최대 가치 반환

# 예시 데이터
val = [60, 100, 120]  # 아이템의 가치
wt = [10, 20, 30]  # 아이템의 무게
W = 50  # 배낭의 최대 무게
n = len(val)  # 아이템 개수

# 최대 가치 계산
print(knapsack(W, wt, val, n))

# 출력
# 220

다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프 내에서 두 노드 사이의 최단 경로를 찾는 알고리즘이다. 주로 네트워크 라우팅 프로토콜, 지도의 경로 탐색 등에 활용된다. 이 알고리즘은 음의 가중치를 갖지 않는 그래프에 적용된다.

다익스트라 알고리즘은 시작 노드 설정 후, 시작 노드로부터 각 노드까지의 거리(가중치)를 저장하는 배열을 무한대로 초기화한다. 시작 노드의 거리는 0으로 설정하고, 방문하지 않은 노드 중 시작 노드로부터 가장 가까운 노드를 선택한다. 그리고 선택한 노드를 경유지로 하여 갈 수 있는 다른 노드들까지의 거리를 계싼하고, 기존에 저장된 거리보다 짧을 경우 갱신한다. 모든 노드를 방문할 때 까지 이 과정을 반복하면 시작 노드로부터 각 노드까지의 최단 거리가 계산된다.

다익스트라 알고리즘은 그리디 알고리즘을 적용하여 매 선택에서 지역적으로 최적인 해를 선택해 나가는 방식으로, 전체적으로 최적의 해를 찾는다.

음의 가중치가 있을 경우, 알고리즘은 정확한 결과를 보장할 수 없다.

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    queue = []
    heapq.heappush(queue, [distances[start], start])

    while queue:
        current_distance, current_node = heapq.heappop(queue)

        if distances[current_node] < current_distance:
            continue

        for adjacent, weight in graph[current_node].items():
            distance = current_distance + weight

            if distance < distances[adjacent]:
                distances[adjacent] = distance
                heapq.heappush(queue, [distance, adjacent])

    return distances

# 그래프 예시
graph = {
    'A': {'B': 8, 'C': 1, 'D': 2},
    'B': {},
    'C': {'B': 5, 'D': 2},
    'D': {'E': 3, 'F': 5},
    'E': {'F': 1},
    'F': {'A': 5}
}

start_node = 'A'
print(dijkstra(graph, start_node))

#출력 결과
{'A': 0, 'B': 6, 'C': 1, 'D': 2, 'E': 5, 'F': 6}

플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 모든 쌍 최단 경로 문제를 해결하는 알고리즘이다. 이 문제는 주어진 가중치 그래프에서 모든 정점 쌍 사이의 최단 경로를 찾는 것이 목표이다. 플로이드-워셜 알고리즘은 동적 프로그래밍을 기반으로 한다.

알고리즘의 기본 아이디어는 각 단계마다 '경유점'을 하나씩 추가하며, 이 경유점을 통해 갈 수 있는 모든 정점 쌍의 최단 거리를 업데이트하는 것이다. 여기서 '경유점'이란 특정 정점을 거쳐 가는 경로를 말한다.

최단 거리 정보를 저장할 2차원 배열 D를 준비한다. D[i][j]는 정점 i에서 j로 가는 직접 경로의 가중치를 나타낸다. 직접 경로가 존재하지 않는 경우, 해당 값은 무한대로 설정한다. 자기 자신으로 가는 경로의 가중치는 0으로 설정한다.

각 정점을 경유점으로 고려: 모든 정점 쌍 (i, j)에 대해서, 가능한 모든 경유점 k에 대하여 D[i][k] + D[k][j]의 값을 계산하고, 이 값이 D[i][j]보다 작은 경우 D[i][j]를 D[i][k] + D[k][j]로 업데이트한다. 그리고 모든 정점을 경유점으로 고려한 후, 배열 D에는 모든 정점 쌍 사이의 최단 경로의 가중치가 저장된다.

시간 복잡도는 O(N^3)이며, 여기서 N은 그래프의 정점 수이다. 음의 가중치가 있는 그래프에서도 사용할 수 있다. 단, 그래프에 음의 사이클이 있으면 안 된다. 동적 프로그래밍 방식을 사용하여 문제를 해결한다.

# 무한대를 의미하는 값으로 초기화한다. 실제 사용에서는 충분히 큰 수를 사용한다.
INF = float('inf')

# 그래프의 가중치를 나타내는 2차원 리스트. graph[i][j]는 정점 i에서 j로 가는 가중치를 의미한다.
# 직접 연결이 없는 경우 INF로 설정한다.
graph = [
    [0, 3, INF, 5],
    [2, 0, INF, 4],
    [INF, 1, 0, INF],
    [INF, INF, 2, 0]
]

# 플로이드-워셜 알고리즘 실행
def floyd_warshall(graph):
    n = len(graph)
    
    # 최단 거리를 저장할 2차원 리스트를 그래프의 가중치로 초기화한다.
    dist = [row[:] for row in graph]
    
    # 모든 정점을 경유점으로 하여 최단 거리를 업데이트한다.
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

# 최단 거리 계산
shortest_distances = floyd_warshall(graph)

for row in shortest_distances:
    print(row)

#출력 결과
#[0, 3, 7, 5]
#[2, 0, 6, 4]
#[3, 1, 0, 5]
#[5, 3, 2, 0]

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하는 방법이다. 각 하위 문제는 한 번만 계산되며, 그 결과는 테이블에 저장되어 필요할 때마다 재사용된다. 이 접근법은 중복 계산을 피하고, 효율성을 크게 향상시킨다.

DP 추천 알고리즘 : https://www.acmicpc.net/problem/10870

DP는 큰 문제를 해결할 수 있는 작은 문제로 나누고, 각 하위 문제를 해결하고, 결과를 저장한 뒤, 저장된 하위 문제의 해결책을 조합하여 원래 문제의 해결책을 구하는 방식이다.

Top-Down(Memoization)방식은 큰 문제를 작은 문제로 나누어 재귀적으로 해결한다. 이미 계산된 결과는 저장(메모)하여 중복 계산을 방지한다.

Bottom-Up(Tabulation)방식은 가장 작은 하위 문제부터 시작하여 순차적으로 큰 문제를 해결해 나가는 방식이다. 각 단계의 결과를 테이블에 저장하며, 최종적으로 원하는 문제의 해를 얻을 수 있다.

피보나치 수열에서 F(n) = F(n-1) + F(n-2)라는 관계가 있다. 이를 동적 계획법으로 해결할 수 있다.

# Top-Down
def fib_memo(n, memo):
    if n <= 1:
        return n
    if memo[n] == 0:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

n = 10
memo = [0]*(n+1)
print(fib_memo(n, memo))

#Bottom-Up
def fib_tab(n):
    if n <= 1:
        return n
    fib_table = [0]*(n+1)
    fib_table[1] = 1
    for i in range(2, n+1):
        fib_table[i] = fib_table[i-1] + fib_table[i-2]
    return fib_table[n]

n = 10
print(fib_tab(n))

탐욕 알고리즘(Greedy Algorithm)은 매 순간 최적이라고 생각되는 선택을 하여 최종적인 해답에 도달하는 방법이다. 이 알고리즘은 전체를 고려하는 것이 아니라, 각 단계에서 최선의 결정을 내려서 전역 최적화(global optimum)를 추구한다. 탐욕 알고리즘은 구현이 간단하고, 계산 효율이 높다는 장점이 있지만, 모든 문제에 대해 항상 최적의 해를 보장하지는 않는다.

그리디 알고리즘은 각 단계에서 지역적으로 최적이라고 판단되는 선택을 함으로써 전체 문제의 최적해를 찾아가고, 한 번 선택된 결정은 취소할 수 없다. 최적의 선택을 통해 탐색 공간을 신속하게 축소한다.

그리디 알고리즘을 적용하기 위해서는 두 가지 규칙이 있는데 첫 번째는 앞의 선택이 이후의 선택에 영향을 주지 않으며, 부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있는 것이고, 두 번째 규칙은 문제의 최적 해결책이 그 부분 문제의 최적 해결책으로부터 구성될 수 있다는 것이다.

#동전의 종류가 500원, 100원, 50원, 10원이 있을 때, 
#거스름돈을 가장 적은 수의 동전으로 나누어 주는 방법을 찾는 것이 목표

def min_coins(change, coins):
    count = 0
    for coin in sorted(coins, reverse=True):
        count += change // coin
        change %= coin
    return count

coins = [500, 100, 50, 10]
change = 1260
print(min_coins(change, coins))

각 단계에서 가장 큰 동전부터 최대한 많이 사용하는 탐욕적 선택을 한다. 이러한 선택이 전체 문제에 대한 최적의 해답(최적 해)을 제공한다.

BFS(너비 우선 탐색)는시작 정점에서 가까운 정점부터 차례대로 모든 정점을 방문하는 방식. 큐(Queue)를 사용하여 구현한다.

모든 노드를 레벨별로 탐색하고 최단 경로를 찾는 데 유용하다(가중치가 없는 경우). 고로최단 경로 찾기, 소셜 네트워크에서 '최단 연결 경로' 찾기 등에 유용하다.

from collections import deque

def bfs(graph, start_node):
    visited = set()  # 방문한 노드를 체크할 집합
    queue = deque([start_node])  # 탐색을 시작할 노드를 큐에 추가
    
    while queue:  # 큐가 비어있지 않는 동안
        node = queue.popleft()  # 큐에서 하나의 노드를 꺼냄
        if node not in visited:
            visited.add(node)
            queue.extend(graph[node] - visited)  # 해당 노드의 인접 노드를 큐에 추가
    return visited

DFS(깊이 우선 탐색)는 시작 정점에서 한 방향으로 가능한 멀리 있는 정점을 방문하고, 더 이상 방문할 정점이 없으면 마지막에 통과한 정점으로 되돌아와 다른 방향의 정점을 탐색하는 방식이다. 스택(Stack) 또는 재귀 함수를 사용하여 구현한다.

경로의 가능성을 탐색할 때 유용하다. 순환 구조를 갖는 그래프에서 사용될 수 있다. 미로 찾기, 퍼즐 게임, 사이클 찾기 등을 구현할 때 유용하다.

def dfs(graph, start_node, visited=None):
    if visited is None:
        visited = set()  # 방문한 노드를 체크할 집합
    visited.add(start_node)
    
    for node in graph[start_node] - visited:  # 현재 노드의 인접 노드 중 방문하지 않은 노드에 대해 탐색
        dfs(graph, node, visited)
    return visited

Topological Sort(위상 정렬)은 방향 그래프에서 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 이 알고리즘은 주로 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에 적용된다. 위상 정렬의 결과는 유일하지 않을 수 있으며, 하나의 그래프에 여러 위상 정렬 결과가 존재할 수 있다.

DAG에서는 적어도 하나의 노드가 들어오는 간선이 없는(진입 차수가 0인) 노드가 존재한다. 위상 정렬은 진입 차수가 0인 노드를 찾아 순서대로 나열하고, 해당 노드와 연결된 간선을 제거한다. 간선 제거 후 새롭게 진입 차수가 0이 된 노드를 찾아 위 과정을 반복한다.

모든 노드의 진입 차수를 계산한다. 진입 차수가 0인 노드를 큐에 삽입한다. 큐에서 노드를 꺼내 해당 노드를 위상 정렬의 결과에 추가하고, 해당 노드에서 나가는 간선을 그래프에서 제거한다. 이 때, 간선 제거로 인해 새롭게 진입 차수가 0이 된

노드를 큐에 삽입한다. 큐가 빌 때까지 3번 과정을 반복한다. 그래프에 사이클이 없다면 모든 노드가 위상 정렬 결과에 포함된다.

from collections import deque

def topological_sort(graph):
    indegree = {u: 0 for u in graph}  # 모든 노드의 진입 차수를 0으로 초기화
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1  # 진입 차수 계산
    
    queue = deque([u for u in graph if indegree[u] == 0])  # 진입 차수가 0인 노드를 큐에 삽입
    
    top_order = []
    while queue:
        u = queue.popleft()
        top_order.append(u)
        for v in graph[u]:
            indegree[v] -= 1  # u에서 나가는 간선 제거
            if indegree[v] == 0:
                queue.append(v)
                
    if len(top_order) == len(graph):
        return top_order  # 모든 노드를 방문했다면 위상 정렬 성공
    else:
        return []  # 사이클이 존재한다면 위상 정렬 실패

위상 정렬은 의존성이 있는 여러 작업을 수행할 때 순서를 결정하는 데 유용하다. 예를 들어, 프로젝트에서 수행해야 할 작업들 사이에 선행 관계가 정의되어 있을 때, 각 작업을 시작하기 전에 반드시 완료되어야 하는 작업들의 순서를 결정할 수 있다. 또한, 컴파일러가 소스 코드 내의 의존성을 해결하기 위해 사용하기도 한다.

++백트래킹

백트래킹(Backtracking)은 해를 찾는 도중에 현재의 경로가 해가 될 가능성이 없다고 판단되면, 즉시 뒤로 돌아가(Backtrack) 다른 경로로 해를 탐색하는 기법이다. 이 방법은 주로 결정 문제(예/아니오로 답하는 문제)나 최적화 문제를 해결할 때 사용된다. 백트래킹은 브루트 포스(완전 탐색)를 기반으로 하되, 불필요한 경로를 조기에 차단함으로써 탐색의 효율을 높인다.

탐색 중에 해가 될 수 없는 경우를 빠르게 판단하여 탐색 범위를 줄인다. 이는 탐색 과정에서 불필요한 부분을 제거함으로써 탐색 시간을 단축시킨다.

가능한 모든 해를 나무 모양으로 구성한 것으로, 해를 찾기 위해 탐색한다. 노드마다 선택지를 고르면서 내려가되, 어떤 노드가 문제의 조건에 맞지 않는다면 그 노드의 부모로 돌아와 다른 선택지를 탐색한다.

백트래킹은 재귀적인 성질을 띤다. 해를 찾아가는 과정에서 각 단계에서 모든 가능성을 시도하다가 가능성이 없다고 판단되면, 바로 이전 상태로 돌아간다.

def backtrack(path):
    if 조건에 부합하는 해가 완성된 경우:
        해를 출력하거나 기록
        return
    
    for 선택 in 모든 가능한 선택지:
        if 선택이 유효한 경우:
            path에 선택을 추가
            backtrack(path)  # 재귀 호출
            path에서 선택을 제거  # 백트래킹

완전 탐색 알고리즘(Brute-Force Search)은 문제를 해결하기 위해 가능한 모든 경우의 수를 시험해보는 방법이다. 가장 기본적이면서 직관적인 알고리즘 접근 방식 중 하나로, 복잡한 문제 해결 방법이 바로 떠오르지 않을 때 유용하게 사용될 수 있다.

Brute-Force Search 는 문제의 가능한 모든 해를 체계적으로 나열하고 검사하여, 조건에 맞는 해를 찾아낸다. 이 방법은 문제의 크기가 작을 때 효과적이고 . 특정 문제에 국한되지 않고, 어떤 종류의 문제에도 적용 가능하다.

가능한 해의 수가 많아지면 계산 시간이 기하급수적으로 증가하는 단점이 있다 가능한 모든 경우의 수를 탐색하기 때문에, 문제의 규모가 커질수록 비효율적이고 시간이 많이 소요되기 때문이다.

Brute-Force Search는 비밀번호 크래킹(가능한 모든 문자열 조합을 시도하여 비밀번호를 찾아내는 과정)과 여러 도시를 순회하는 여행자 문제(TSP, Traveling Salesman Problem)에서 가능한 모든 경로를 탐색하여 최단 경로를 찾는 경우와 스도쿠, 큐브 퍼즐 등에서 가능한 모든 숫자나 위치의 조합을 시도하여 문제를 해결할 때 사용할 수 있다.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 원하는 값을 찾으면 그 위치를 반환
    return -1  # 값을 찾지 못하면 -1 반환

Brute-Force Search 방식은 문제를 해결하는 가장 확실한 방법 중 하나이지만, 대부분의 경우 더 효율적인 알고리즘을 고려하는 것이 좋다.

이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾기 위한 효율적인 알고리즘이다. 이진 탐색은 분할 정복(Divide and Conquer) 전략을 사용하여, 탐색 과정에서 검사해야 할 요소의 수를 매 단계마다 절반으로 줄여 나간다. 이로 인해 탐색 시간을 대폭 줄일 수 있으며, 시간 복잡도는 O(log n)이다.

작동 원리

1. 분할(Divide): 배열의 중간에 위치한 원소를 선택하고, 이 원소를 피벗(pivot)으로 한다.
2. 정복(Conquer): 피벗과 탐색하고자 하는 값(target)을 비교한다.
   • 타겟 값이 피벗보다 작다면, 피벗의 왼쪽 부분에 대해서만 탐색을 계속한다.
   • 타겟 값이 피벗보다 크다면, 피벗의 오른쪽 부분에 대해서만 탐색을 계속한다.
3. 재귀(Recursive): 선택된 부분 배열에 대해 위의 과정을 반복한다.
4. 종료 조건:
   • 타겟 값이 피벗과 일치하는 경우, 해당 인덱스를 반환한다.
   • 탐색 범위가 더 이상 없는 경우(타겟 값을 찾지 못한 경우), -1 또는 탐색 실패를 나타내는 값이 반환된다.

이진 탐색을 사용하기 위해서는 배열이 미리 정렬되어 있어야 한다. 정렬된 데이터셋에서 특정 값의 존재 여부 확인, 값의 인덱스 찾기 등에 사용된다.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # 타겟을 찾은 경우, 인덱스 반환
        elif arr[mid] < target:
            left = mid + 1  # 타겟이 더 큰 경우, 왼쪽 범위 조정
        else:
            right = mid - 1  # 타겟이 더 작은 경우, 오른쪽 범위 조정

    return -1  # 타겟을 찾지 못한 경우, -1 반환

최소 힙(Min Heap)과 최대 힙(Max Heap)은 완전 이진 트리(complete binary tree)를 기반으로 하는 힙(Heap) 자료구조의 두 가지 주요 형태다. 힙은 각 노드가 하위 노드보다 우선순위가 높은 반정렬 상태(semi-ordered state)를 유지하는 트리 기반의 자료구조이다. 최소 힙과 최대 힙은 우선순위의 정의에 따라 분류되며, 우선순위 큐(priority queue) 구현에 자주 사용된다.

최소 힙(Min Heap)에서는 부모 노드의 키(key) 값이 자식 노드의 키 값보다 항상 작거나 같다. 즉, 트리의 루트에는 힙 내의 최소값이 위치한다. 따라서, 최소 힙을 사용하면 원소들이 항상 오름차순으로 정렬된 상태를 유지할 수 있다.

• insert: 새로운 요소를 추가할 때는, 트리의 가장 마지막에 요소를 추가한 후, 부모 노드와 비교하여 힙 속성을 만족시키도록 위치를 조정한다.
• extract-min: 힙에서 최소값(루트 노드)을 제거하고, 트리의 가장 마지막 요소를 루트로 이동시킨 후, 힙 속성을 만족시키도록 다시 조정한다.

최대 힙 (Max Heap)에서는 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같다. 즉, 트리의 루트에는 힙 내의 최대값이 위치한다. 최대 힙을 사용하면 원소들이 항상 내림차순으로 정렬된 상태를 유지할 수 있다.

• insert: 새로운 요소를 추가할 때는, 트리의 가장 마지막에 요소를 추가한 후, 부모 노드와 비교하여 힙 속성을 만족시키도록 위치를 조정한다.
• extract-max: 힙에서 최대값(루트 노드)을 제거하고, 트리의 가장 마지막 요소를 루트로 이동시킨 후, 힙 속성을 만족시키도록 다시 조정한다.

힙은 배열로 효율적으로 구현될 수 있다.

• 부모 노드의 인덱스: ⌊ i−1 / 2 ​⌋
• 왼쪽 자식 노드의 인덱스: 2i + 1
• 오른쪽 자식 노드의 인덱스: 2i + 2

Priority Queue, 즉 우선순위 큐는 우선순위를 기준으로 요소들이 정렬되는 추상 자료형(abstract data type)이다. 이 자료구조에서는 각 요소가 우선순위와 연관되어 있으며, 우선순위가 가장 높은 요소가 가장 먼저 제거된다. 우선순위 큐는 다양한 방법으로 구현될 수 있지만, 힙(heap)을 사용하는 것이 가장 일반적이다.

우선순위 큐에서 요소의 추가나 제거는 요소의 우선순위에 따라 결정된다. 가장 높은 우선순위를 가진 요소가 가장 먼저 제거된다. 배열, 연결 리스트, 이진 힙(최소 힙 또는 최대 힙) 등 여러 가지 방법으로 구현할 수 있다. 이 중 이진 힙을 사용하는 것이 추가 및 제거 작업에 대해 O(log n)의 시간 복잡도를 제공하여 가장 효율적이다.

Priority Queue는 다익스트라 알고리즘, 프림 알고리즘과 같은 그래프 알고리즘, 스케줄링, 네트워크 트래픽 제어, 이벤트 관리 시스템 등 다양한 분야에서 활용된다.

• insert(item, priority): 주어진 우선순위와 함께 요소를 큐에 추가한다.
• pop(): 가장 높은 우선순위를 가진 요소를 큐에서 제거하고, 그 요소를 반환한다.
• peek(): 가장 높은 우선순위를 가진 요소를 큐에서 제거하지 않고 반환한다.
• isEmpty(): 큐가 비어 있는지 여부를 확인한다.

Python의 표준 라이브러리인 heapq 모듈은 최소 힙 기능을 제공하며, 최소 힙을 우선순위 큐로 사용할 수 있다. 최대 힙을 구현하려면 우선순위에 음수를 적용하거나 사용자 정의 객체를 사용할 수 있다.

import heapq

# 최소 힙을 사용한 우선순위 큐 예시
priority_queue = []
heapq.heappush(priority_queue, (1, 'Task 1'))  # 우선순위 1
heapq.heappush(priority_queue, (3, 'Task 3'))  # 우선순위 3
heapq.heappush(priority_queue, (2, 'Task 2'))  # 우선순위 2

# 가장 우선순위가 높은 요소를 제거하고 반환
print(heapq.heappop(priority_queue))  # 출력: (1, 'Task 1')

QuickSort는 분할 정복(divide and conquer) 전략을 사용하는 효율적인 정렬 알고리즘 중 하나다. 평균적인 시간 복잡도는 O(n log n)이며, 최악의 경우 시간 복잡도는 O(n^2)이다.

작동 원리

1. 분할(Divide): 배열에서 '피벗'이라고 하는 하나의 원소를 선택한다. 피벗의 위치는 다양한 방법으로 선택할 수 있으며, 피벗 선택 방식에 따라 알고리즘의 성능이 달라질 수 있다. 이 피벗을 기준으로 배열을 두 부분으로 나눈다. 피벗보다 작은 모든 요소는 피벗의 왼쪽에, 피벗보다 큰 모든 요소는 피벗의 오른쪽에 오도록 한다.
2. 정복(Conquer): 피벗을 제외한 왼쪽 부분 배열과 오른쪽 부분 배열을 재귀적으로 정렬한다.
3. 결합(Combine): QuickSort는 정복 단계에서 배열을 실제로 정렬하므로, 별도의 결합 단계가 필요하지 않다.

특징

• In-place 정렬: 추가적인 배열을 필요로 하지 않으며, 주어진 배열 내에서 정렬을 수행한다.
• 불안정 정렬(Unstable sort): 동일한 값의 원소가 있을 경우, 원래의 순서가 유지되지 않을 수 있다.
• 피벗 선택 중요: 피벗 선택 방법에 따라 성능이 크게 달라질 수 있다. 예를 들어, 항상 첫 번째 원소를 피벗으로 선택하면 이미 정렬된 배열에 대해 최악의 성능(O(n^2))을 보일 수 있다.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)

정렬 과정

1. 초기 배열: [3, 6, 8, 10, 1, 2, 1]
2. 피벗 선택: 8 (배열의 중간 요소)
3. 분할:
   • 왼쪽(left): [3, 6, 1, 2, 1] (피벗보다 작은 요소)
   • 중간(middle): [8] (피벗과 같은 요소)
   • 오른쪽(right): [10] (피벗보다 큰 요소)
4. 왼쪽(left) 부분 배열에 대한 재귀적 정렬:
   • 피벗 선택: 1
   • 분할:
     • 왼쪽: [1] (피벗보다 작거나 같은 요소)
     • 중간: [1] (피벗과 같은 요소)
     • 오른쪽: [3, 6, 2] (피벗보다 큰 요소)
   • 오른쪽 부분 배열에 대한 재귀적 정렬:
     • 피벗 선택: 6
     • 분할:
       • 왼쪽: [3, 2] (피벗보다 작은 요소)
       • 중간: [6] (피벗과 같은 요소)
       • 오른쪽: [] (피벗보다 큰 요소가 없음)
     • 왼쪽 부분 배열에 대한 재귀적 정렬:
       • 피벗 선택: 2
       • 분할:
         • 왼쪽: [2] (피벗보다 작은 요소)
         • 중간: [] (피벗과 같은 요소가 없음)
         • 오른쪽: [3] (피벗보다 큰 요소)
     • 재조합: [2, 3, 6]
   • 재조합: [1, 1, 2, 3, 6]
5. 전체 배열에 대한 재조합: [1, 1, 2, 3, 6, 8, 10]

정렬된 배열

• 최종 결과: [1, 1, 2, 3, 6, 8, 10]

MergeSort는 분할 정복(divide and conquer) 방법론을 기반으로 하는 효율적인 정렬 알고리즘이다. 평균적으로 O(n log n)의 시간 복잡도를 가지며, 최악의 경우에도 O(n log n)을 유지한다. 이 알고리즘은 배열을 더 이상 나눌 수 없을 때까지 반으로 나눈 다음, 나누어진 배열을 다시 정렬하면서 병합하는 방식으로 작동한다.

작동 원리

1. 분할(Divide): 입력 배열을 가장 작은 단위가 될 때까지 계속 반으로 나눈다. 이 과정은 재귀적으로 수행되며, 각 부분 배열이 하나의 요소만을 갖게 될 때까지 계속된다.
2. 정복(Conquer): 나누어진 부분 배열을 다시 병합하면서 정렬한다. 이때, 인접한 두 부분 배열을 정렬하면서 병합하는 방식으로 진행한다.
3. 결합(Combine): 모든 부분 배열이 병합되어 하나의 정렬된 배열이 될 때까지 2단계를 반복한다.

특징

• 안정 정렬(Stable sort): 동일한 값의 요소 사이의 상대적인 순서가 변경되지 않는다.
• 비교적 메모리 사용량이 많음: 병합 과정에서 추가적인 배열이 필요하기 때문에, QuickSort와 같은 일부 다른 정렬 알고리즘에 비해 메모리 사용량이 많다.
• 분할 정복 알고리즘: 데이터를 분할하고, 각각을 정복한 다음, 결과를 결합하는 전형적인 분할 정복 접근 방식을 따른다.

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr)//2
        L = arr[:mid]
        R = arr[mid:]

        mergeSort(L)
        mergeSort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

HeapSort는 힙(heap) 자료구조를 기반으로 하는 효율적인 정렬 알고리즘 중 하나다. 이 알고리즘은 최악, 평균, 최선의 경우 모두 O(n log n)의 시간 복잡도를 가진다. HeapSort의 기본 아이디어는 주어진 데이터를 이진 힙(binary heap) 구조로 만든 후, 큰 값들(또는 작은 값들)을 배열의 끝으로 이동시키면서 정렬하는 것이다.

힙(Heap) 이란?

힙은 각 노드의 값이 자식 노드의 값보다 크거나 같은(또는 작거나 같은) 완전 이진 트리(complete binary tree)이다. 힙은 크게 두 종류가 있다: 최대 힙(max heap)과 최소 힙(min heap). 최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같으며, 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같다.

HeapSort의 작동 방식

1. 힙 구성(Heapify): 주어진 배열을 최대 힙 형태로 구성한다. 이 과정은 배열의 중간부터 시작하여 루트 노드까지 거슬러 올라가면서, 각 노드를 올바른 위치로 이동시키는 "heapify" 과정을 반복하여 수행한다.
2. 정렬(Sort): 최대 힙의 루트(가장 큰 값)는 항상 힙의 첫 번째 위치에 있으므로, 이를 배열의 마지막 요소와 교환한다. 배열에서 힙으로 고려되는 부분의 크기를 하나 줄이고(실제로 배열에서 요소를 제거하는 것은 아니다), 변경된 힙에 대해 다시 heapify 과정을 수행한다. 이 과정을 배열이 정렬될 때까지 반복한다.

특징

• In-place 정렬: 추가적인 배열을 필요로 하지 않으며, 주어진 배열 내에서 정렬을 수행한다.
• 불안정 정렬(Unstable sort): 동일한 값의 원소가 있을 경우, 원래의 순서가 유지되지 않을 수 있다.
• 효율적인 시간 복잡도: 모든 경우에 O(n log n)의 시간 복잡도를 제공한다.

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[largest] < arr[left]:
        largest = left

    if right < n and arr[largest] < arr[right]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    for i in range(n//2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

힙 구성(Heapify) 단계

정렬(Sort) 단계