넌 과감해질 필요가 있어

1. 더 맵게 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42626

# 이해
# 최소 힙
# 값이 작은 2개를 pop()해서, 특정 공식으로 계산된 결과를 push()
# 최소 값이 K를 넘을 때까지 반복

# 풀이
# scoville = heapq.heapify(scoville)
# cnt = 0
# while True:
    # scoville을 정렬하여, [0]번째 원소가 K보다 작으면 (heap은 subscription이 가능한가?)
        # first = heapq.heappop(scoville)
        # second = heapq.heappop(scoville)
        # new = first + (second * 2)
        # heapq.heappush(scoville, new)
        # cnt += 1
    # 작지 않으면 return cnt
    

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while len(scoville) >= 2:
        if scoville[0] < K:
            first = heapq.heappop(scoville)
            second = heapq.heappop(scoville)
            new = first + (second * 2)
            heapq.heappush(scoville, new)
            answer += 1
        else:
            return answer
    
    return answer if scoville[0] >= K else -1

힙의 크기가 1 이하가 되면, 더 이상 계산을 진행할 수 없으므로 while의 범위를 설정한다.

while을 벗어난 뒤에도 마지막으로 조건을 만족하는지 확인한 뒤에 결과를 return한다.

2. 디스크 컨트롤러 (Lv. 3)

https://school.programmers.co.kr/learn/courses/30/lessons/42627

# 이해 1
# 전체 작업 소요 시간의 평균이 최소가 되도록
# 매번 가능한 작업 중 소요 시간이 작은 것을 먼저 수행한다.
    # 반례가 있다.
    # [[0, 3], [4, 10], [5, 1], [6, 1]]
    # 3, 14, 15, 16 == 11.25
        # 3 + 10 + 10 + 10
    # 3, 6, 7, 17 == 8.25
        # 3, 1, 1, 10
# 끝나는 시간을 기준으로 해야 할 듯하다.
# 배열을 탐색하여, 원소 별로 끝나는 시간(시작 시간 + 소요 시간)을 구한다.
# 끝나는 시간이 빠른 것 순서대로 처리한다.

# 이해2
# 이해 1은 틀렸다 !! 정확히는 문제의 조건에 부합하지 않는다.
# <제한사항>의 마지막 항목: "하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다."
# 따라서 수행 가능한 작업이 있다면 즉시 실행한다.
# 수행 가능한 작업이 여러 개가 있다면 소요 시간이 짧은 것을 실행한다.

# 풀이
# 현재 시간을 표시할 변수 now = 0
# 총 대기 시간 변수 total_waiting_time = 0
# 현재 가능한 작업 큐 ready_queue = []
# 현재 index = 0

import heapq

def solution(jobs):
    jobs.sort()
    now = 0
    total_waiting_time = 0
    index = 0
    ready_queue = []

    while index < len(jobs) or ready_queue:
        while index < len(jobs) and jobs[index][0] <= now: # 현재 시간 now보다 작은(실행 가능한) 작업 모두 추가
            heapq.heappush(ready_queue, (jobs[index][1], jobs[index][0]))
            index += 1

        if ready_queue:
            duration, start = heapq.heappop(ready_queue)
            now += duration
            total_waiting_time += now - start
        else:
            now = jobs[index][0]

    return total_waiting_time // len(jobs)

3시간 이상 풀이한 듯하다 ..

적어도 1시간은 문제의 조건을 놓쳐서 헤맸다.

각 작업의 요청부터 종료 시간의 평균을 최소로 하려면, 작업이 종료되는 시간을 기준을 해야 한다고 판단했다.

가령 다음과 같은 테스트 케이스가 있다고 가정하자. `[[0, 3], [4, 10], [5, 1], [6, 1]]`

매 순간 가능한 작업 중 소요 시간이 가장 짧은 것을 선택하면 다음과 같다. `[0, 3] -> [4, 10] -> [5, 1] -> [6, 1]`

이 경우 요청부터 종료까지 3 + 10 + 10 + 10 -> 평균 8.25초가 소요된다.

끝나는 시간을 기준으로 가장 먼저 끝나는 작업을 선택하면 다음과 같다. `[0, 3] -> [5, 1] -> [6, 1] -> [4, 10]`

이 경우는 3 + 1 + 1 + 13 -> 평균 4.5초가 소요된다.

그러나 문제의 조건 중 다음을 놓쳤다. `하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다.`

조건을 만족하려면, 반드시 `현재 가능한 작업 중 소요 시간이 가장 짧은 것을 선택`해서 수행하면 된다.

현재 작업의 시작 시간이 now 보다 작다면 ready_queue에 추가한다. `while index < len(jobs) and jobs[index][0] <= now:`

현재 작업의 시작 시간이 now 보다 크다면  now를 현재 작업의 시작 시간에 맞춘다. `else:`

3. 이중우선순위큐 (Lv. 3)

https://school.programmers.co.kr/learn/courses/30/lessons/42628

# 이해
# 명령어를 받아서 힙을 구성
# 명령어에 따라 최솟값 혹은 최댓값을 pop()
# 모든 명령어를 수행하고 남은 힙의 최솟값과 최댓값을 return

# 풀이
# 명령어의 순서를 미리 기록한다.
# 가령 최솟값 삭제면 False, 최댓값 삭제면 True
# 힙에 추가하는 명령어를 실행할 때마다, 순서 배열을 보면서 최댓값 삭제(True)인 경우 -값을 추가한다.
# 모든 명령어는 최솟값 삭제로 실행한다.

import heapq

def solution(operations):
    answer = []
    heap = []
    
    for operation in operations:
        op, num = operation.split()
        
        if op == "I":
            heapq.heappush(heap, int(num))
        elif heap:
            if num == "-1":
                heapq.heappop(heap)
            else: # num == "1"
                heap.remove(max(heap))
    
    return [0, 0] if len(heap) == 0 else [max(heap), min(heap)]

O(NlogN) 풀이가 떠오르지 않아서 구글링을 했다.
다들 그냥 remove 함수를 사용한다.

O(N^2) 아닌가...? N == 10 ** 6이니까 10 ** 12로, 시간 초과 기준(10 ** 9)을 아득히 넘는다.
완성된 힙을 탐색하는 것이 아니라, 완성해가면서 탐색하는 것이기 때문에 가능한가보다.

다시 한번 느꼈다. 프로그래머스에서 문제 풀 때는 시간 복잡도는 신경 쓰는 것이 아니다.
N이 1억이나 10억이면 이분 탐색 문제이고, 아니라면 일단 O(N ** 2)으로 풀이하자.

1. 같은 숫자는 싫어 (Lv. 1)

https://school.programmers.co.kr/learn/courses/30/lessons/12906

# 이해
# 스택에 연속된 숫자가 저장되면 안 됨.

# 풀이
# arr을 탐색하며 stack에 추가
# 추가하기 전, stack의 top과 같은 경우 pass, 다른 경우 push

def solution(arr):
    stack = []
    
    for elem in arr:
        if stack:
            if elem != stack[-1]:
                stack.append(elem)
        else:
            stack.append(elem)
    
    return stack

기능개발 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42586

# 이해
# progresses의 원소는 100%를 달성하면 배포된다.
# 매일 speeds의 원소만큼 progress가 진행된다.
# 가장 앞에 있는 원소가 100%를 달성한 순간에, 100%를 달성한 모든 원소를 배포한다.

# 풀이
# progresses의 각 원소를 100에서 빼고, 그 값을 speeds로 나누어 남은 일자를 계산한다. remain_days: [Int]
# remain_days를 탐색하며, 내림차순으로 정렬된 경우 tmp에 더하고, 
    # 내림차순이 깨진 순간 tmp를 answer에 append하고, tmp를 초기화 한다.
# answer를 return한다.

import math

def solution(progresses, speeds):
    answer = []
    remain_days = [math.ceil((100 - progress) / speed) for progress, speed in zip(progresses, speeds)]
    
    current_max_day = remain_days[0]
    count = 0
    
    for day in remain_days:
        if day <= current_max_day:
            count += 1
        else:
            answer.append(count)
            current_max_day = day
            count = 1
    
    answer.append(count)
    
    return answer

`zip()` 함수는 여러 개의 iterators를 인자로 받아, 인덱스를 기준으로 짝 지은 튜플을 반환하는 함수이다.

위 코드에서 math.ceil()는 필수적이지 않다. `-((progress - 100) // speed)`의 형태로 작성해도 같은 결과이다.

3. 올바른 괄호 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/12909

나의 풀이

# 이해
# 괄호가 올바르게 짝지어지면 True
# 하나라도 틀리면 False

# 풀이
# "("인 경우
    # stack이 비었으면 추가한다.
    # stack에 원소가 있다면, stack의 top이 "("이라면 추가. ")"이라면 return False
# ")"인 경우
    # stack이 비었으면 return False
    # stack에 원소가 있다면, stack의 top이 "("이라면 stack.pop(), ")"이라면 return False

def solution(brackets):
    stack = []
    
    for bracket in brackets:
        if bracket == "(":
            if not stack:
                stack.append(bracket)
            else:
                if stack[-1] == "(":
                    stack.append(bracket)
                else:
                    return False
        
        else: # bracket == ")"
            if not stack:
                return False
            else:
                if stack[-1] == "(":
                    stack.pop()
                else:
                    return False
                
    return True if not stack else False

더 쉬운 풀이

def is_pair(s):
    wt = 0
    
    for c in s :
        if c == '(' :
            wt += 1
        elif c == ')':
            wt -= 1
        
        if wt < 0: 
            return False
        
    return wt == 0

스택에 성질을 활용하면 `나의 풀이`처럼 모든 케이스를 대응할 필요가 없다.

4. 프로세스 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42587

나의 풀이

# 이해
# priorities 배열을 우선순위에 따라 pop() 할 때, 
# location 위치에 있는 원소가 몇 번째로 pop() 되는지 return

# 풀이
# max_value = max(priorities)
# priorities_with_hash = [[i, hash(i)] for i in priorities]
# max_value_hash = priorities_with_hash[location][1]
# order = 0
# while len(priorities_with_hash) >= 0:
    # current = popleft()
    # current[0] >= max_value, 
        # if current[1] == max_value_hash:
            # return order
        # order += 1
    # current[0] < max_value:
        # priorities_with_hash.append(current)

from collections import deque
import random

def solution(priorities, location):
    order = 1
    priorities_with_hash = deque([[priorities[i], i] for i in range(len(priorities))])
    max_value = max(priorities)
    target_hash = priorities_with_hash[location][1]
    
    while len(priorities_with_hash) >= 0:
        current = priorities_with_hash.popleft()
        
        if current[0] >= max_value: 
            if current[1] == target_hash:
                return order
            max_value = max([elem[0] for elem in priorities_with_hash])
            order += 1
            
        else: # current[0] < max_value
            priorities_with_hash.append(current)
            
    return order

더 나은 풀이

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

`any()`: 인자로 받은 iterators 중에 하나라도 True이면, 전체를 True로 반환한다.

5. 다리를 지나는 트럭 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42583

# 이해
# bridge_length는 다리에 올라갈 수 있는 트럭 수. 동시에 트럭이 이동해야 하는 길이.
# weight는 다리가 버틸 수 있는 무게. 트럭의 개수가 bridge_length보다 적어도, 무게 기준을 만족해야 한다.
# 모든 트럭이 다리를 건너는 데까지 걸리는 시간을 return

# 풀이
# 정석적인 원형 큐로 풀이해보자
# bridge = deque([])
# bridge.append(truck_weights[0])
# bridge_sum += truck_weights[0]
# time = 0

# while True:
    # time += 1
    # out_truck = bridge.popleft()
    # bridge_sum -= out_truck
    # if out_truckt > 0 and len(truck_weights) == 0:
        # return time
    
    # if bridge_sum + truck_weights[0] < weight:
        # in_truck = truck_weights.popleft()
        # bridge.append(in_truck)
        # bridge_sum += in_truck
        
    # else:
        # bridge.append(out_truck)

from collections import deque
        
def solution(bridge_length, weight, truck_weights):
    
    bridge = deque([0] * bridge_length)
    truck_weights = deque(truck_weights)
    bridge_sum = 0
    time = 0

    while truck_weights or bridge_sum > 0:
        time += 1
        out_truck = bridge.popleft()
        bridge_sum -= out_truck

        if truck_weights and bridge_sum + truck_weights[0] <= weight:
            in_truck = truck_weights.popleft()
            bridge.append(in_truck)
            bridge_sum += in_truck
        else:
            bridge.append(0)
    
    return time

`if truck_weights and bridge_sum + truck_weights[0] <= weight:` 이러한 방식이 좋다.

반복할 때마다 판단해야 하는 조건이 있다면, if이든 while이든 조건문에 포함시키자.

6. 주식가격(Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42584

나의 풀이 (큐)

from collections import deque

def solution(prices):
    queue = deque(prices)
    answer = []
    
    while queue:
        price = queue.popleft()
        sec = 0
        for q in queue:
            sec += 1
            if price > q:
                break 
        answer.append(sec)        
    return answer

복잡할 것이 없는 풀이이다.

그러나 30분 동안 고민했다.

주어진 배열의 길이가 10 ** 5이어서, O(N ** 2)은 시간 초과가 발생할 수 있다고 판단했기 때문이다.

실제로는 시간 초과가 발생하지 않았다.

계속해서 queue의 크기를 줄여나가기  때문인 듯하다.

실제로 코테에서도 웬만한 크기(10 ** 4 ~ 10 ** 5)라면 일단 완전탐색으로 풀이하자.

그렇게 부분 점수 먼저 확보해 놓고, 시간복잡도를 개선하는 것이 훨씬 현실적인 코테 접근법이다.

더 나은 풀이 (스택)

# 이해
# 배열의 각 원소가 오름차순이 지속되는 길이를 각각 return
# 다음 원소와 비교하여, 값이 작아지지 않을 때마다 += 1
# 일단 지속 시간을 1초 증가시키고, 그 뒤에 오름차순 여부를 판단한다.
# 마지막 원소는 0초이다.

# 풀이
# 일단 이중 반복문으로 풀자

from collections import deque

def solution(prices):
    length = len(prices)
    answer = [i for i in range(length - 1, -1, -1)]
    
    stack = [0]
    for i in range(1, length):
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)
    
    return answer

https://velog.io/@soo5717/프로그래머스-주식가격-Python

위 블로그 글을 참고한 풀이이다.

1. 폰켓몬 (Lv. 1)

https://school.programmers.co.kr/learn/courses/30/lessons/1845

# 이해
# N마리 중에서 N/2마리를 선택.
# 이때 가장 많은 종류를 선택하고, 그때의 가짓수를 return
# nums의 길이는 10,000이므로 O(n^2)까지는 괜찮겠다. 프로그래머스는 10억에서 시간 초과가 발생하므로.

# 풀이
# nums+1(0부터 200,000) 크기의 visited 배열을 만든다.
# nums를 탐색하며, 방문하지 않은 포켓몬일 경우 result, cnt에 += 1 하고, 방문 처리한다.
# 매 탐색마다 cnt가 len(nums) // 2 이하인지 확인한다. 초과하면 result를 return 한다.

def solution(nums):
    return min(len(nums) // 2, len(set(nums)))

최초에는 방문 처리를 통해 최소 횟수로 최대 개수를 확보하려고 했다.

그러나 모든 포켓몬이 다른 종류인 경우 최대 방문 가능 횟수(`len(nums) // 2`) == 정답이다.

포켓몬의 종류가 `len(nums) // 2`보다 작은 경우 그것이 정답이다.

2. 완주하지 못한 선수 (Lv. 1)

https://school.programmers.co.kr/learn/courses/30/lessons/42576

최초 풀이 (정렬)

# 이해
# completion에 있지만, participant에 없는 사람 return
# 동명이인이 있을 수 있다.

# 풀이
# 정렬한다.
# 순서대로 나오지 않으면 즉시 return 한다.

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[len(participant)-1]

더 나은 풀이 (hash 함수)

def solution(participant, completion):
    
    dic = {}
    tmp = 0
    
    for part in participant:
        dic[hash(part)] = part
        tmp += hash(part)
    
    for comp in completion:
        tmp -= hash(comp)
        
    return dic[tmp]

hash 함수의 성질을 이용한 풀이이다.

배열의 각 원소를 탐색하며, hash()로 생성된 고유 숫자를 더하고 빼면, 하나의 고유 숫자만이 남는다는 것을 응용했다.

3. 전화번호 목록 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42577

# 이해
# 어떤 번호가 다른 번호의 접두어인 경우 false
# 아니라면 true
# str.startswith() / str.endswith() -> Bool

# 풀이
# phone_book을 탐색하며, 딕셔너리에서 현재 단어가 없다면,
# 현재 단어를 1글자씩 tmp에 더해가며 딕셔너리가 True가 반환되는 것이 있는지 확인.
# 있으면 return 없으면 완성된 단어를 True로 갱신


def solution(phone_book):
    dic = {}
    
    for pb in phone_book:
        dic[pb] = 1
    
    for pb in phone_book:
        tmp = ""
        for pb_chr in pb:
            tmp += pb_chr
            if tmp in dic and tmp != pb:  # 여기서도 동일하게 'if' 사용
                return False
    
    return True

단어 배열을 탐색하며, 완성된 단어는 모두 방문 처리한다.

단어 배열을 다시 탐색하며, 각 단어를 이중 탐색한다.

한 글자씩 더해가며 딕셔너리에 있는 단어인지 판단한다.

이때, 한 글자씩 더해가다가 단어가 완성된 경우는 제외한다. 문제의 조건에 중복된 단어는 없기 때문이다

4. 의상 (Lv. 2)

https://school.programmers.co.kr/learn/courses/30/lessons/42578

# 이해
# 패션 조합의 가짓수
# 하루에 최소 한 개의 의상
# 한 종류에서는 하나의 옷만 선택
# 모든 종류를 선택할 수도, 하나의 종류만 선택할 수도, 복수의 종류만 선택할 수도 있다.

# 풀이
# from itertools import combinations
# type별로 카운트 횟수를 딕셔너리에 기록함
# type에 대한 조합을 구함.
# 모든 조합에 대하여, type에 대응하는 카운트 횟수를 곱해 answer에 더함.
# answer 반환.

def solution(clothes):
    answer = 1  # 곱셈을 위해 1부터 시작
    dic = {}
    
    # 각 옷의 종류별로 개수를 계산
    for _, type in clothes:
        dic[type] = dic.get(type, 0) + 1
    
    # 각 종류별로 옷을 선택하는 경우의 수 계산 (해당 종류의 옷을 안 입는 경우 포함)
    for count in dic.values():
        answer *= (count + 1)  # 해당 종류의 옷을 선택하지 않는 경우도 포함하여 +1
    
    return answer - 1  # 아무것도 입지 않는 경우의 수 1을 뺌

최초에는 combinations를 사용하여 복잡하게 풀이했다.

더 나은 풀이를 참고하니 깨달음을 얻었다.

선택하지 않는 것을 포함한 모든 조합의 수를 구하는 것 == 케이스마다 선택 가능한 `경우의 수 + 1` 모두 곱하기

5. 베스트앨범 (Lv. 3)

https://school.programmers.co.kr/learn/courses/30/lessons/42579

# 이해
# 1. 해당 장르의 재생 수
# 2. 동일 장르 내 곡의 재생수
# 3. 고유번호가 낮은 것

# 풀이
# genre_count = { 장르: 총 재생 횟수 }
# genre_dic = { 장르: [고유번호, 재생 횟수] }
# genre_count -> 재생 횟수 -> 고유 번호 순서대로 정렬
# 각 장르마다 2개씩 끊어서 고유 번호 저장

def solution(genres, plays):
    answer = []
    
    genre_count = {}
    genre_dic = {}
    
    for i in range(len(genres)):
        if genres[i] in genre_count:
            genre_count[genres[i]] += plays[i]
        else:
            genre_count[genres[i]] = plays[i]
        
        genre_dic.setdefault(genres[i], []).append([i, plays[i]])
    
    # genre_count의 values의 내림차순으로 정렬
    genre_count_sorted = sorted(genre_count.items(), key=lambda x: x[1], reverse=True)
    
    for genre, _ in genre_count_sorted:
        sorted_songs = sorted(genre_dic[genre], key=lambda x: (-x[1], x[0]))
        answer.extend([song[0] for song in sorted_songs[:2]])
    
    
    return answer

최초에는 정말 복잡하게 풀었다.

`dictionary.setdefault(val, default_val)` 함수를 기억하자.

lambda로 정렬 함수를 작성할 때 `-, +` 부호를 활용하여 `내림차순, 오름차순`을 쉽게 표현할 수 있다는 것을 기억하자.

구현 문제가 아닌 이상 코딩테스트의 코드는 과도하게 복잡해지지 않는다는 것을 기억하자.

실전에서는 어찌 됐든 풀이하는 게 맞다. 그러나 코드의 엔트로피가 올라가고 있다면 뭔가 잘못 됐다는 것을 의식하자.

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/acqm9mM1P6o?si=paoazc7Qx2lqr39R

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘.

다양한 문제 상황이 있다.

1. 한 지점에서 다른 한 지점까지의 최단 경로
2. 한 지점에서 다른 모든 지점까지의 최단 경로
3. 모든 지점에서 다른 모든 지점까지의 최단 경로

각 지점은 그래프에서 노드로 표현한다.

지점 간 연결 도로는 그래프에서 간선으로 표현한다.

다익스트라 Dijkstra

요약

특정 노드에서 다른 모든 노드로 가는 최단 경로를 계산.

음의 간선이 없는, 현실 세계의 도로에서 정상적으로 동작.

그리디 알고리즘으로 분류.

매 상황에서 가장 비용이 적은 노드를 선택하여 과정을 반복하기 때문.

동작 과정

1. 출발 노드를 설정
2. 최단 거리 테이블을 최댓값(예컨대 INF)으로 초기화 (각 노드에 대한 현재까지의 최단 거리 정보를 갖고 있음)
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택
4. 3번에서 선택한 노드를 거쳐, 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 모든 노드를 방문할 때까지 3번과 4번을 반복

구현1. 기본적인 다익스트라

INF = int(1e9) # 무한의 거리를 나타내기 위해 10억을 설정

n, m = map(int, input().split())
start = int(input()) # 시작 노드
graph = [[] for _ in range(n+1)] # 연결 정보 담는 리스트
visited = [False] * (n+1) # 방문 체크 리스트
distance = [INF] * (n+1) # 시작 노드부터 특정 노드까지의 최단 거리 테이블. INF로 초기화.

for _ in range(m): # 모든 간선 정보 입력
    a, b, c = map(int, input().split()) # a번 노드 -> b번 노드 (비용 c)
    graph[a].append((b, c))
    
def get_smallest_node(): # 방문하지 않은 노드 중, 최단 거리가 최소인 노드 반환
    min_value = INF
    index = 0 # 최단 거리가 최소인 노드의 인덱스
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]: # 현재 노드의 최단 거리보다 짧고 && 방문하지 않음
            min_value = distance[i]
            index = i
    
    return index
    
def dijkstra(start):
    distance[start] = 0 # 시작 노드부터 시작 노드까지의 최단 거리는 0으로 갱신
    visited[start] = True # 방문 처리
    
    for adjacent_node_of_start in graph[start]: # 시작 노드와 인접한 노드의 최단 거리 갱신
        distance[adjacent_node_of_start[0]] = adjacent_node_of_start[1]
        
    for i in range(n-1): # n-1인 이유. 시작 노드X. 마지막 노드X
        now = get_smallest_node() # 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드
        visited[now] = True # 방문 처리
        
        for adjacent_node in graph[now]: # 선택한 노드와 인접한 노드 확인
            cost = distance[now] + adjacent_node[1] # 시작~선택 + 선택~인접
            if cost < distance[adjacent_node[0]]: # cost가 시작~인접보다 작을 경우 갱신
                distance[adjacent_node[0]] = cost
                
dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("도달할 수 없는 신기루")
    else:
        print(distance[i])

1번 방법의 특징

O(V)번에 걸쳐서 get_smallest_node()를 호출하여, 매번 선형 탐색을 해야 한다.

따라서 전체 시간 복잡도는 O(V^2)이다.

python은 대략 1초에 20,000,000 연산이 가능하므로 노드 개수가 5,000 개면 간당간당하다.

우선순위 큐를 이용하여 개선이 필요하다.

잠시 자료 구조의 바다에 빠져보자.

풍덩 ~

우선순위 큐 Priority Queue

우선 순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료 구조.

python은 표준 라이브러리 형태로 지원한다.

나의 이데아 swift는 지원하지 않는다. 함부로 다가갈 수 없는 매력이 있다.

힙 Heap

우선순위 큐를 구현하기 위해 필요한 자료 구조이다.

최소 힙(Min Heap)과 최대 힙(Max Heap)이 있다.

완전 이진 트리(complete binary tree)의 일종.

힙은 느슨한 정렬 상태를 유지한다.

부모 노드의 key(노드가 저장하는 값)가 자식 노드의 key보다 항상 작은-최소 힙(큰-최대 힙) 상태의 이진 트리.

이진 트리 binary tree

모든 노드가 둘 이하(0, 1, 2)의 자식을 가진 트리이다.

위 그림과 같이 다양한 종류가 있다.

많은 자료 구조를 만나고 왔다.

이진 트리 -> 완전 이진 트리 -> 힙 -> 우선 순위 큐 -> 개선된 다익스트라 알고리즘.

이렇듯 여러 단계를 거쳐 다익스트라를 개선시킬 수 있다.

핵심은 단계마다 방문하지 않은 노드 중에서, 시작 노드로부터 최단 거리가 가장 짧은 노드를 선택하기 위해 힙을 사용하는 것이다.

구현2. 개선된 다익스트라

import heapq

INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)
# 방문 처리 배열을 만들지 않는다. 단계마다 순차 탐색하는 것이 아니라 우선순위 큐에서 pop()하므로.

for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start)) # 시작 노드 -> 시작 노드의 최단 거리는 0으로 갱신. 큐에 삽입.
    distance[start] = 0
    
    while q: # 큐가 텅텅 빌 때까지 반복
        dist, now = heapq.heappop() # 최단 거리(dist)를 기준으로 우선순위 큐에서 bubble pop

        if distance[now] < dist: # distance[now] == 현재까지 확정된 최소 거리, dist == 현재 탐색에서 최소 거리
            continue # 확정된 최소 거리가 더 짧으면, 이미 방문한 셈 치고 continue
        
        for adjacent_node in graph[now]:
            cost = dist + adjacent_node[1] # 현재 탐색에서, 탐색 중인 노드의 최소 거리 + 인접 노드의 최소 거리
            if cost < distance[adjacent_node[0]]: # cost가 인접 노드의 확정된 최소 거리보다 짧다면 갱신
                distance[adjacent_node[0]] = cost
                heapq.heappush(q, (cost, adjacent_node[0]])

dijkstra(start)

for i in ragne(1, n+1):
    if distance[i] == INF:
        print("영영 닿을 수 없음")
    else:
        print(distance[i])

개선된 방법의 특징

시간 복잡도는 O(ElogV)이다.

E는 Edge(간선), V는 Vertex(정점, 노드).

모든 노드를 검사하는 while문은 간선의 개수 E에 따라 실행 횟수가 결정된다.

왜 why? 간선의 개수만큼 큐에 넣으니까.

전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산(O(logN))과 유사하다.

E개의 원소에 대하여 O(logE)의 연산을 수행한다.

즉, 시간 복잡도는 O(ElogE)이다.

동시에 이것은 O(ElogV)와 같다.

왜 why? 실제 그래프에서 모든 노드가 서로 연결되어 있다면, 최대 간선 수는 V*(V-1)/2이다.

따라서 다음의 식이 성립한다.

O(ElogE) -> O(ElogV^2) -> O(2ElogV) -> O(ElogV)

플로이드-워셜 Floyd-Warshall

요약

모든 노드에서 다른 모든 노드로 가는 최단 경로를 모두 계산.

다익스트라와 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행.

단, 단계마다 방문하지 않는 노드 중 최단 거리 노드를 찾는 과정은 필요X (다익스트라에서 get_smallest_noe()로 수행했던 그것)

2차원 테이블에 최단 거리 정보를 저장.

다이나믹 프로그래밍 유형에 속함.

동작 과정

1. 2차원 최단 거리 테이블을 최댓값(예컨대 INF)으로 초기화
2. 각 단계마다 특정한 노드 k를 거쳐가는 경우를 확인
   1.  a -> b 최단 거리보다, a -> k  + k -> b가 더 짧은지 검사
   2. 점화식(D는 거리): Dab = min(Dab, Dak + Dkb)
3. 모든 노드를 방문할 때까지 2번을 반복

구현: 플로이드 워셜

INF = int(1e9)

n, m = map(int, input().split()) # n은 노드의 개수, m은 간선의 개수
graph = [[INF] * (n + 1) for _ in range(n + 1)] # 최단 거리 정보를 저장할 2차원 리스트 INF로 초기화

for a in range(1, n+1): # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
    for b in range(1, n+1):
        if a == b:
            graph[a][b] = 0
            
for _ in range(m): # 각 간선에 대한 정보를 입력 받아, 최단 거리 테이블 갱신
    a, b, c = map(int, input().split())
    graph[a][b] = c # a에서 b로 가는 비용을 c라고 설정
    
for k in range(1, n+1): # 점화식에 따라 플-워 수행
    for a in range(1, n+1):
        for b in range(1, n+1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for a in range(1, n+1):
    for b in range(1, n+1):
        if graph[a][b] == INF:
            print("INFINITY", end = " ")
        else:
            print(graph[a][b], end = " ")
    print()

플로이드 워셜의 특징

노드의 개수가 N개일 때 알고리즘을 N번 수행한다.

각 단계마다 O(N^2)의 연산을 통해, 현재 선택된 노드를 거쳐 가는 모든 경로를 고려한다.

따라서 플로이드 워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다.

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/5Lu34WIx2Us?si=OJpwTfcdclJ1HMaq

다이나믹 프로그래밍 Dynamic Programming

요약

다이나믹 프로그래밍(DP)은 동적 계획법이라고도 부른다.

메모리를 사용하여, 처리 시간을 단축하는 방법이다. 이를 메모이제이션(Memoization)이라고 한다.

조건

1. 최적 부분 구조 (Optimal Substructure)
   - 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다.
2. 중복되는 부분 문제 (Overlapping Subproblem)
   - 동일한 작은 문제를 반복적으로 사용하여 해결해야 한다.

접근 방식

• 하향식(Top-Down): 큰 문제로 시작하여, 풀리지 않는 작은 문제를 만나면 재귀적으로 해결.
• 상향식(Bottom-Up ): 작은 문제를 모아서 큰 문제를 해결하는 방식.

Top-Down 접근 방식을 메모이제이션(Memoization)이라고도 부른다.

계산 결과를 메모리에 저장하여 중복 계산을 방지한다.

주로 재귀 함수를 반복적으로 호출하여 문제를 해결한다.

Bottom-Up 접근 방식은 타뷸레이션(Tabulation)이라고 한다.

테이블에 기록한다는 느낌.

주로 반복문으로 구현한다.

따라서 재귀 호출에 따른 오버헤드 혹은 스택 오버플로우 위험이 없다.

기본적으로 Bottom-Up으로 접근하는 것이 더 직관적이다.

일단 그렇게 하고, 막히면 Top-Down으로 풀이하자.

DP인지 어떻게 판단?

가장 중요한 문제이다.

1. 주어진 입력값의 범위가 너무 크면 의심해본다.
2. 완탐, 그리디로 풀리지 않으면 의심해본다.
3. 상술된 조건을 이용한다. (quick sort가 왜 DP가 아닌지 떠올리면 더 좋다. 최적 부분 구조는 맞지만, 중복되는 부분 문제는 없다.)

피보나치 수열을 DP로 구현

피보나치 수열이 뭔지는 생략하지 않지 않지 않겠다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

An = An-1 + An-2의 규칙을 반복하는 수열이다.

그림과 같은 방식으로 풀이하면, 중복 계산이 발생하여 지수 시간복잡도를 갖는다.

그래서 DP로 풀이하기 딱 좋은 유형이다.

f(6)을 구하기 위해, 작은 문제로 나눌 수 있다. 작은 문제를 합치면 f(6)을 구할 수 있다. (최적 부분 구조)

f(2)와 같이 작은 문제가 중복 계산되고 있다. (중복되는 부분 문제)

햐향식 Top-Down 접근

dp = [0] * 100 # 계산된 결과를 메모이제이션 하기 위한 리스트

def fibo(x):
    if x == 1 or x == 2:
        return 1
        
    if dp[x] != 0: # 이미 계산된 결과는 즉시 return. 중복 계산 방지. 상수 시간 소요.
        return dp[x]

    dp[x] = fibo(x - 1) + fibo(x - 2) # 새로운 문제는 재귀적으로 구함.
    return dp[x]

print(fibo(10)) # 55

상향식 Bottom-Up 접근

# 엥 이것도 메모이제이션 아니에요? 
# 동의하는 부분.. 다만 탑다운에서 이미 계산된 결과는 즉시 반환하는 등 명시적으로 다루고 있어서 구분 짓나 보다.
dp = [0] * 100

d[1] = 1
d[2] = 1

for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[10]) # 55

예제 1. 개미 전사

# DP인지 판단
# 최적 부분 구조가 가능한가?
    # 특정 구간의 최대 조합이 있을 것이다. 그것은 구간을 확장해도 조합이 바뀌지 않을 것이다.
# 중복되는 부분 문제가 있는가?
    # 특정 구간의 조합이 다음 구간에 영향을 주므로 (1칸 이상 떨어져야 함) 중복되는 문제가 있다고 보아야 한다.

# 메모이제이션 - 탑 다운으로 풀이해보자
# 배열의 크기가 1일 때는? a1
# 2일 때는? max(S1, a2)
# 3일 때는? max(S2, S1 + a3)
# 4일 때는? max(S3, S2 + a4)
# 5일 때는? max(S4, S3 + a5)
# 6일 때는? max(S5, S4 + a6)
# n일 때는? max(Sn-1, Sn-2 + an)
# S1 = arr[0]
# S2 = max(arr[1], arr[0])
# Sn = max(Sn-1, Sn-2 + an)

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * 10
dp[0] = arr[0]
dp[1] = max(arr[0], arr[1])

def get_food(n):

    if dp[n] != 0:
        return dp[n]
    
    dp[n] = max(dp[n - 1], dp[n - 2] + arr[n])

    return dp[n]

print(get_food(n - 1))
print(dp)

예제 2. 1로 만들기

# 최적 부분 구조
    # 맞다. 특정 수를 만드는 최소 연산 회수는 정해져 있다.
# 중복되는 부분 문제
    # 맞다. 특정 수까지의 최소 연산 회수가 정해져 있으므로, 계산 과정에서 반복적으로 사용한다.

# 조건
# 5로 나눈다.
# 3으로 나눈다.
# 2로 나눈다.
# 1로 뺸다.

# 풀이
# 항상 큰 수로 나누는 것이 유리한가?
# 그렇지만, 순서의 차이는 있다. 16의 경우 16 -> 15 -> 3 -> 1 (3번) / 16 -> 8 -> 4 -> 2 -> 1 (4번)). 그리디처럼 풀이하는 것은 아니다.
# 반대로 1부터 dp 테이블 해당 인덱스를 구하기 위한 최소 연산 회수로 채워가는 것은 어떤가?
# [0, 1, 2, 3, 4, 5, 6, 7, ...]
# [0, 0, 1, 1, 2, 1, 2, 3, ...]

# 7을 살펴보자. 다음과 같은 방법으로 만들 수 있다.
# 6 + 1
# 6을 살펴보자.
# 5 + 1, 3 * 2, 2 * 3
# 10을 살펴보자.
# 9 + 1, 5 * 2, 2 * 5
# Sn = min(Sn-1 + 1, Sn//5 + 1, Sn//3 + 1, Sn//2 + 1)이다.
# if n이 어떤 수로 나누어 떨어지느냐에 따라 if 조건문으로 나누면 풀이할 수 있을 것이다.

# n = 1 return 1
# n = 2 return 1
# n = 3 return 1
# n = 5 return 1

# if n % 5 == 0
    # min(Sn-1 + 1, Sn//5 + 1)
# elif n % 3 == 0
    # min(Sn-1 + 1, Sn//3 + 1)
# elif n % 2 == 0
    # min(Sn-1 + 1, Sn//2 + 1)
# else
    # Sn-1 + 1

n = int(input())

dp = [0] * 30001
dp[0] = 0
dp[1] = 0
dp[2] = 1
dp[3] = 1
dp[5] = 1

for i in range(4, n + 1):
    dp[i] = dp[i-1] + 1
    if i % 5 == 0:
        dp[i] = min(dp[i], dp[i//5] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)

print(dp[n])

예제 3. 효율적인 화폐 구성

# 최적 부분 구조
    # 맞다. 특정 값을 구성하기 위한 최소 화폐 개수는 정해져 있다.
# 중복되는 부분 문제
    # 해당 구조가 여러 번 반복된다.


# 풀이
# 무조건 고액 화폐를 많이 사용하는 것이 옳은가?
# 그렇지 않다. 700을 고려해보자. 300 + 300 + ...? / 300 + 200 + 200
# 1로 만들기 문제처럼, 100부터 목표 값까지 최소 화폐 개수를 채워나가보자.
# coins = [200, 300]
# [100, 200, 300, 400, 500, 600, 700, 800, 900, 1000]
# [  0,   1,   1,   2,   2,   2,   3,   3,   3,    4]
# 쉬운 듯?
# min(Sn-300 + 1, Sn-200 + 1)

# if 조건문으로 모든 케이스를 검증하며 풀이해보자. 아니다. 조건문조차 필요가 없다.
# dp = [0] * 10001

# for coin in coins:
# dp[coin] = 1

# for i in range(min(coins), m + 1)
    # for coin in coins:
        # if i > coin:
            # dp[i] = min(dp[i], dp[i - coin] + 1)

# -1 if dp[m] == 1 else dp[m]


n, m = map(int, input().split())
coins = [int(input()) for _ in range(n)]

dp = [10001] * (m + 1)
dp[0] = 0

for i in range(n): # 화폐 단위
    for j in range(coins[i], m+1): # 목표 금액
        if dp[j - coins[i]] != 10001:
            dp[j] = min(dp[j], dp[j-coins[i]] + 1)

if dp[m] == 10001:
    print(-1)
else:
    print(dp[m])

예제 4. 금광

# 최적 부분 구조
    # 맞다. 전체의 문제를 한 열씩 나눠서 판단할 수 있다. 
    # 특정 구간 최적 경로는 전체 구간에서 봐도 그렇다.
# 중복되는 부분 문제
    # 하나의 최적 경로를 구하는 문제이므로, 같은 구간이 중복되어 계산된다.

# 풀이
# 무작정 3방향 중 최대값을 선택하면 되는가?
# 안 된다. 그건 그리디이다. 이동 범위 밖에 있는 최적 경로가 존재할 수 있다.

# 전체 행에서 최대값을 선택하는 것도 불가능하다. 이동이 불가능할 수도 있으므로.

# 2차원 배열을 탐색하며 이전 3방향의 최대값을 더해주는 방식으로 배열을 갱신해야겠다.
# 현재 인덱스의 값은, 이전 3방향 값 중 최대값을 더한 값이다.
# 즉, 다음과 같다.
# dp[i][j] = dp[i - 1][j] +  matrix[i][j-1]
# if i > 0:
# dp[i][j] = max(dp[i][j], dp[i-1][j-1] + matrix[i][j])
# if i + 1 < n 
# dp[i][j] = max(dp[i][j], dp[i+1][j-1] + matrix[i][j])


tc = int(input())

for k in range(tc):
    n, m = map(int, input().split())
    arr = list(map(int, input().split()))

    matrix = []
    for i in range(0, len(arr), m):
        matrix.append(arr[i : i + m])

    dp = [[0] * m for _ in range(n)]
    for i in range(n):
        dp[i][0] = matrix[i][0]

    for j in range(1, m):
        for i in range(n):
            if i == 0:
                left_up = 0
            else:
                left_up = dp[i - 1][j - 1]
            
            if i == n - 1:
                left_down = 0
            else:
                left_down = dp[i + 1][j - 1]
            
            left = dp[i][j - 1]
            dp[i][j] = matrix[i][j] + max(left_up, left, left_down) # 2차원 탐색 문제는 이렇게

    result = 0
    for i in range(n):
        result = max(result, dp[i][m-1])
    
    print(result)

예제 5. 병사 배치하기

# 최적 부분 구조
    # 나눠서 풀 수 있는가?
    # 연속되는 구간 별로 나눠서 특정 병사를 제외했을 때, 그것이 최선이 되는가?
    # 직관적으로 생각나지는 않지만, 딱히 반례가 떠오르는 것도 아니다.

# 중복되는 부분 문제
    # 하나의 최적 배열을 구하는 것이므로, 부분 문제가 중복된다고 할 수 있다.

# 풀이
# 최장 연속 부분 수열? 그런 유형인 듯하다.
# 내림차순이 성립하지 않는 모든 수만 제거하면 되는가? 그럼 문제가 발생한다.
# [15 11 2 10 9] 이런 배열이 있다면 내림차순이 성립함에도 불구하고, 2를 제거하는 것이 옳다.
# [9 8 7 6 5 4 3 2 10 5 9 8 7] 이런 경우에는 4 3 2 5를 제거해야 한다.


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

dp = [1] * n

for i in range(1, n):
    for j in range(0, i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)

print(n - max(dp))

위 문제는 가장 긴 연속하는 부분 수열(Longest Increasing Subsequence, LIS) 유형이다.

LIS의 점화식은 다음과 같다.

# D[i] = array[i]를 마지막 원소로 포함하는, 부분 수열의 최대 길이
모든 0 ≤ j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

모든 i에 대하여 0 ~ i 범위를 탐색하면서 비교하므로 시간복잡도는 O(N^2)이다.

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/KGyK-pNvWos?si=w2ozPGhJxDhH5aNy

레퍼런스: https://gyoogle.dev/blog/

정렬

데이터를 특정한 기준에 따라 순서대로 나열하는 것.

선택 정렬 selection sort

요약

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 정렬 알고리즘.

각 탐색마다 결정될 자리를 먼저 선택하고, 자리에 올 값을 찾는 과정이라고 생각하면 좋다.

구현

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

for i in range(len(array)):
    min_index = i # 최솟값의 인덱스, 최초에는 이번 탐색에서 결정될 인덱스로 초기화
    
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]: # 현재 인덱스보다 작은 값을 발견하면
            min_index = j # 최솟값의 인덱스를 갱신
    
    array[i], array[min_index] = array[min_index], array[i] # 탐색이 끝나면 스왑

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도

N + (N - 1) + (N - 2) + ... + 2 # 마지막 원소는 이미 확정되었으므로 정렬을 하지 않아도 괜찮다.

데이터의 개수가 N개라고 했을 때,

• 첫 번째 탐색에서 비교횟수: 1 ... N-1 => N-1
• 두 번째 탐색에서 비교횟수: 2 ... N-1 => N-2
• ...
• (N-1) + (N-2) + .... + 2 => N(N-1) / 2 - 1

시간복잡도는 O(N^2)이다.

최선, 평균, 최악의 경우 모두 같다.

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행되므로, O(N)이다.

특징

• 제자리 정렬 (in-place sorting)
• 불안정 정렬 (unstable sorting)

삽입 정렬 insertion sort

요약

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입하는 정렬 알고리즘.

선택 정렬에 비해 구현 난도는 높지만, 일반적으로 더 효율적.

구현

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

for i in range(1, len(array)): # 1번째 원소는 결정된 것으로 간주하고, 2번째 원소부터 정렬
    for j in range(i, 0, -1): # 삽입할 원소를, 역순으로 기존 원소와 비교하며 삽입 위치를 결정
        if array[j] < array[j-1]: # 현재 원소가 이전 원소보다 작은 경우
            array[j], array[j-1] = array[j-1], array[j] # 위치를 바꿈 # 이전 원소의 왼쪽으로
        else:
            break # 작지 않을 경우 해당 자리에서 멈춤

print(array) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

시간 복잡도

N + (N - 1) + (N - 2) + ... + 1 # 마지막 원소까지 정렬해야 함

최악, 평균의 경우: 선택 정렬과 마찬가지로 O(N^2)

최선의 경우: O(N)

이미 정렬이 되어 있을 경우, 한 번씩만 비교한다.

즉, 상수 시간이 소요된다.

전체 배열 탐색 + 탐색마다 한 번씩 비교만 하면 되므로 O(N)

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행되므로, O(1)이다.

추가적인 메모리가 필요하지 않다.

특징

• 대부분의 원소가 정렬되어 있는 경우, 매우 효율적이다.
• 제자리 정렬 (in-place sorting)
• 안정 정렬 (stable sorting)

퀵 정렬 quick sort

요약

기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.

분할 정복(divide and conquer) 방법을 사용한다.

병합 정렬과 더불어 대부분 언어의 기본 정렬 라이브러리의 근간이다.

구현1: 일반적인 방식

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return

    pivot = start # 첫 번째 원소를 피봇으로
    left = start + 1 # 왼쪽 포인터의 인덱스
    right = end # 오른쪽 포인터의 인덱스

    while left <= right:
        while left <= end and array[left] <= array[pivot]: # 왼쪽 출발. pivot보다 큰 값을 찾을 때까지.
            left += 1
        
        while right > start and array[right] >= array[pivot]: # 오른쪽 출발. pivot보다 작은 값을 찾을 때까지.
            right -= 1
        
        if left > right: # 포인터가 엇갈렸다면, 작은 값과 피봇 값을 교체
            array[right], array[pivot] = array[pivot], array[right]
        
        else: # 엇갈리지 않았다면, 각 포인터의 값을 교체
            array[left], array[right] = array[right], array[left]
    
    quick_sort(array, start, right - 1) # 분할divide 이후 각각 재귀적으로 정렬
    quick_sort(array, right + 1, end)

quick_sort(array, 0, len(array) - 1)
print(array)

구현2: pythonic한 방식

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

def quick_sort(array):
    if len(array) <= 1: # 리스트 원소가 1개라면 재귀 끝 !
        return array
    
    pivot = array[0] # 첫 번째 원소를 피봇
    tail = array[1:] # 피봇을 제외하고 나머지 배열

    left_side = [x for x in tail if x <= pivot] # filter를 사용하듯, pivot 보다 작은 원소만
    right_side = [x for x in tail if x > pivot] # pivot 보다 큰 원소만

    # 재귀적으로 반복하면, left_side에는 min이, right_side에는 max만 남고 return을 시작한다.
    # 차곡차곡 min + 1, max - 1 -> min + 2, max - 2 ... 쌓이고, 정렬이 완성된다.
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array)

시간 복잡도

데이터의 크기가 N이라면,

각 순환 호출 단계의 비교 연산: O(N)

총 호출의 횟수: O(logN)

따라서 평균, 최선의 시간복잡도는 O(NlogN)이다.

최악의 경우는 O(N^2)이다.

정렬하고자 하는 배열이 이미 오름차순 혹은 내림차순으로 정렬이 되어있는 경우,

각 호출 단계 비교 횟수 O(N), 총 호출 횟수 O(N)이 되어 O(N^2)이다.

공간 복잡도

주어진 배열 안에서 교환(swap)을 통해 수행된다.

재귀 호출 깊이 만큼 추가적인 공간이 필요하므로 O(logN)이다.

최악의 경우 O(N)이다.

특징

• 불안정 정렬
• 불균형 분할 (분할이 항상 절반으로 뚝 나뉘는 것이 아니다. 최악의 경우 시간 복잡도의 비효율을 초래한다.)

계수 정렬 Counting sort

요약

비교하지 않는 정렬이다.

데이터의 값 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.

위 조건에서는 매우 빠르게 동작한다.

구현1: 카운트한 값만큼 반복하는 방식

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
result = []

count = [0] * (max(array) + 1) # 값의 모든 범위를 포함하는 카운터 배열. 0으로 초기화

for i in range(len(array)):
    count[array[i]] += 1 # array 원소의 개수를 센다.

for i in range(len(count)):
    for j in range(count[i]): # 현재 원소가 count된 수만큼 반복해서 추가한다.
        result.append(i)

print(result) # [0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9]

구현2: 누적합을 사용하는 방식 (다소 직관적이지 않다)

def counting_sort(arr):
    # 1단계: 입력 배열에서 최대값 찾기
    max_val = max(arr)
    count = [0] * (max_val + 1)  # 각 숫자의 등장 횟수를 저장할 배열 초기화
    
    # 각 숫자의 등장 횟수 세기
    for num in arr:
        count[num] += 1
    
    # 2단계: 누적합 계산
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 3단계: 정렬된 배열을 생성하기 위한 임시 배열
    output = [0] * len(arr)
    
    # 원본 배열을 거꾸로 순회하며 정렬된 위치에 숫자 배치
    for num in reversed(arr):
        idx = count[num] - 1  # 정렬된 배열에서의 위치 계산. 누적합에서 1을 빼야 0부터 시작하는 인덱스 반영.
        output[idx] = num
        count[num] -= 1  # 다음 같은 숫자가 올 위치를 위해 누적합 감소
    
    return output

# 예제 배열
arr = [1, 4, 1, 2, 7, 5, 2]
sorted_arr = counting_sort(arr)
print(sorted_arr) # [1, 1, 2, 2, 4, 5, 7]

시간 복잡도

데이터의 개수가 N / 정수의 최대값이 K라면,

카운터 배열의 초기화: O(N)

카운터 배열의 누적합을 만드는 과정: O(K)

O(N + K)의 시간 복잡도를 갖는다.

O(N)이 아닌 이유는 [1, 999999] 배열을 정렬할 경우, N = 2임에도 K의 크기만큼 누적합을 계산해야 하기 때문에.

공간 복잡도

누적합 배열: O(K)

정렬된 배열: O(N)
따라서 추가적으로 필요한 공간은 O(N + K)이다.

비교 기반 알고리즘과 다르게 동작하기 때문에, 정렬된 배열을 위한 공간 O(N)이 필요하다는 것을 기억하자.

특징

• 안정 정렬 (stable sorting)
• 제자리 정렬이 아니다 !!! 비교 기반 알고리즘과는 다르다.

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/7C9RgOcvkvo?si=p-_dsBcTLy0K_6WN

스택 Stack

Last-In First-Out

먼저 들어온 데이터가 나중에 나가는 선입후출 자료구조.

stack = []

stack.append(5) # push
stack.append(3)
stack.append(2)
stack.pop() # pop

print(stack) # [5, 3]

python에서 stack은 리스트로 구현할 수 있다.

• 삽입: append(요소) # O(1)
• 삭제: pop() # O(1)

큐 queue

First-In First-Out

먼저 들어온 데이터가 먼저 나가는 선입선출 자료구조.

from collections import deque

queue = deque()

queue.append(5) # push
queue.append(3)
queue.popleft() # pop
queue.append(2)

print(queue) # [3, 2]

python에서 queue는 deque을 사용해서 구현한다.

삽입: append(요소) # O(1)

삭제: popleft() # O(1)

deque은 내부적으로 연결 리스트로 구현이 되어 있다.

따라서 삽입, 삭제가 O(1)으로 가능하다.

단 random access가 불가능하기에, 요소 접근에는 O(N)이 소요된다.

재귀 함수 Recursive Fuction

재귀 함수란? 자기 자신을 다시 호출하는 함수.

재귀 함수는 반복문으로 동일하게 구현이 가능하다. 역도 그렇다.

코드의 길이는 짧아지지만, 인간에게 직관적이지 않으므로 신중하게 사용해야 한다.

문제 풀이에 활용하려면 종료 조건을 반드시 명시해야 한다.

종료 조건 없이 함수가 무한히 호출되면, stack overflow가 발생하기 때문.

import sys
sys.setrecursionlimit(10 ** 5)

python3는 기본적으로 재귀 깊이를 1,000으로 제한해 놓았다.

그러나 문제를 풀다보면 이 제한을 해제해야 하는 경우가 있다.

sys.setrecursionlimit()으로 이 제한을 늘려주자

직접 해본 결과 재귀 깊이가 29945를 넘어가면, segmentation fault 에러가 발생한다.

프로그램이 메모리를 잘못 액세스 했을 때 발생하는 오류로, stack overflow를 원인으로 발생하는 오류 중 하나이다.

정해진 메모리 공간을 넘어가면, 다른 데이터를 건드릴 수 있기에 이를 방지하기 위한 에러이다.

실전에서는 재귀 깊이 제한을 10 ** 5 정도로 설정한 뒤에, 종료 조건을 반드시 작성하자.

예시1. 팩토리얼

def factorial_recursive(n)
    if n <=1 :
        return 1
    return n * factorial_recursive(n - 1)
    
# 0! == 1
# 1! == 1

예시2. 유클리드 호제법

def gcd(a, b)
    if a % b == 0 :
        return b
    else :
        return gcd(b, a % b)
        
# 성질: a와 b의 나머지가 r이라면, a와 b의 최대 공약수 == b와 r의 최대 공약수
# a, b의 대소 관계와 상관없이 동작한다.

DFS (Depth First Search)

정의

깊이 우선 탐색.

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

뼈대

def dfs(graph, v, visited):
    
    visited[v] = True # 현재 노드 방문 처리
    print(v, end = " ") # 방문한 노드를 순서대로 출력
    
    for i in graph[v]: # 인접한 노드를 모두 확인
        if not visited[v]: # 방문하지 않은 노드가 있다면
            dfs(graph, i, visited) # 재귀적으로 탐색

스택 혹은 재귀 함수를 이용한다.

1. 탐색 시작 노드를 스택에 삽입 / 방문 처리
2. 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리.
   방문하지 않은 인접한 노드가 없으면 스택 최상단 노드 꺼냄.
3. 2번 과정을 수행할 수 없을 때 까지 반복

BFS (Breadth First Search)

정의

너비 우선 탐색.

가까운 노드부터 우선적으로 탐색하는 알고리즘.

뼈대

from collections import deque

def bfs(graph, start, visited):
    
    queue = deque([start]) # deque에 시작 노드를 추가해서 초기화
    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 # 방문 처리

큐를 이용한다.

1. 탐색 시작 노드를 큐에 삽입 / 방문 처리
2. 큐에서 노드 꺼내고 해당 노드의 인접 노드 중에서, 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 2번 과정을 수행할 수 없을 때까지 반복

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬, 나동빈, 2021

강의: https://youtu.be/2zjoKjt97vQ?si=VgYo4fBNuccHh7P5

그리디

정의

현재 상황에서 지금 당장 좋은 것만 선택하는 알고리즘.

정당성 분석이 선행되어야 한다.
--> 단순하게 가장 좋아보이는 것만 선택하면, 최적의 해를 구할 수 있는지?

실제로 유형을 모른 채로 문제를 만났을 때, 그리디 알고리즘을 사용해야 하는 근거는 다음과 같다.

1. 문제의 구조:

• 최적 부분 구조: 작은 문제의 최적 해결책이, 전체 문제에도 적용될 수 있어야 함.

2. 선택의 기준:

• 탐욕적: 현재 정보에 한해, 제일 좋은 것을 선택.
• 단기적: 각 선택은 현재 정보만을 기반으로 이루어짐. 이전 혹은 미래의 선택을 고려하지 않음.
• 불가역적: 선택이 이루어지고 나면, 이후의 과정에서 그 선택을 되돌릴 수 없음. 모든 선택은 최종 선택임.

1. 거스름 돈

큰 단위가 항상 작은 단위의 배수이므로 최적의 해를 보장한다.
예: [500, 400, 100]이라면, 큰 단위(500)가 작은 단위(400)의 배수가 아니므로, 그리디를 적용할 수 없다.

2. 1이 될 때까지

1빼기 보다, 나누기를 많이 하는 것이 대부분의 상황에서 유리하다.

현재 값이 2이상이면 나누는 것이 1 빼는 것보다 빠르게 조건을 달성할 수 있으니까.

n, k = map(int, input().split())

result = 0

while True:
    target = (n // k) % k # n과 가장 가까우면서 작은 k로 나누어 떨어지는 수
    result += (n - target) # 어차피 1씩 빼면서 target까지 가야한다. 그것을 한 번에.
    
    n = target # 1씩 빼서 target까지 도착했다고 치고
    
    if n < k: # 나누는 수보다 작아지면 탈출
        break
        
    result += 1
    n //= k # while을 한 번 반복할 때마다, k로 한 번씩 나누는 셈

result += (n - 1) # 더 이상 나눌 수 없는 상태이므로, 1씩 빼서 1에 도착할 때까지 횟수
print(result)

3. 곱하기 혹은 더하기

피연산자가 1 또는 0이 아니라면 항상 곱하기가 유리하다.

4. 모험가 길드

배열을 정렬하고, 작은 값부터 임시 그룹에 추가하며, 조건을 만족하는 즉시 마을을 떠나면 최적의 해를 구할 수 있다.

그리디 알고리즘을 적용해야 하는지 헷갈릴 수 있다.

그리디 알고리즘 선택 근거를 다시 생각해보자.

1. 문제의 구조: [1]인 경우와 [1, 2, 3]인 경우, 모두 같은 풀이를 적용할 수 있다.

2. 선택의 기준: [1]인 경우와 [1, 2, 3]인 경우, 탐욕적으로 선택해도 최적의 해가 나온다. 각 선택은 단기적이고 불가역적이다. 

구현

정의

풀이를 떠올리는 것은 쉽지만 소스 코드로 옮기기 어려운 문제

1. 알고리즘은 간단한데 코드가 지나칠 정도로 길어짐
2. 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 함
3. 문자열을 다룸
4. 적절한 라이브러리를 찾아서 사용해야 함

1. 상하좌우

방향 벡터를 사용한 문제.

행렬의 시작 부분인 (0, 0)이 좌상단 임을 기억할 것.

2. 시각

h = int(input())

count = 0

for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            if "3" in str(i) + str(j) + str(k): # 이렇게 하면 쉽다.
                count += 1

print(count)

완전 탐색.

하루는 86,400초이므로 완탐을 하기에 무리 없다.

파이썬은 1초에 2,000만 번 정도 연산을 수행할 수 있다고 생각하기.

3. 왕실의 나이트

8방향 벡터.

4. 문자열 재정렬

data = input()
result = []
value = 0

for x in data:
    if x.isalpha(): # 문자면 True 아니면 False # isNumeric()도 있음
        result.append(x)
    else:
        value += int(x)

result.sort()

if value != 0: # 숫자가 없을 경우 표시하면 안 되니까
    result.append(str(value))

print("".join(result)) # 리스트의 원소를 합쳐서 문자열로 만드는 방법