📖저자님의 책 소개 영상: https://www.youtube.com/watch?v=Q13Uj_5bH9M

🗓️TIL (this week I learned)
월 읽기, 정리
화 정리 - 더 해야 함
토 몸풀기 문제 + ⭐별 한 개 문제
일 여행준비 ㅠㅠㅠㅠ

13-1 정렬 개념 ⭐⭐

정렬이 필요한 이유:

알고리즘의 효율을 크게 높여줌

1. 삽입 정렬(insertion sort)

출처: 삽입정렬 wiki(en)

• 데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고,
  정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬함.
• key: 정렬되지 않은 영역의 맨 앞에 있는 값
• 시간복잡도: 최악의 경우 $O(N^2)$, 이미 정렬이 되어 있는 최선의 경우 $O(N)$

2. 병합정렬(merge sort, divide and conquer)

출처: 병합정렬 wiki(en)

• 정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬
• 포인터: 특정 배열의 원소를 가리키기 위한 화살표와 같은 것
• 시간 복잡도: $O(NlogN)$ = 나누는 횟수 $logN$ + 합치는 횟수 $NlogN$($N$개 병합을 $NlogN$번) ➡️ $(N+1)logN$ ➡️ $NlogN$
  - $N$개의 인자를 가진 배열을 2로 h번 나누면 1개의 인자를 가진 배열이 된다.
  • 1(칸) = $N$ * $(1/2)^h$
  • $N$ = $2^h$
  • h = $log_2N$

3. 힙 정렬(heap sort)

출처: wiki(ko)

• 힙: 특정 규칙이 있는 이진 트리.
• 최대힙: 부모 노드가 자식 노드보다 크다.
• 최소힙: 부모 노드가 자식 노드보다 작다.
• 시간복잡도: $O(NlogN)$

4. 우선순위 큐(priority queue)

• 우선순위 큐는 힙으로 구현하는 것이 가장 좋다.

• 그 이유: 최소힙이나 최대힙이 특정 값을 루트 노드에 유지하는 특징이 있고, 우선 순위 큐의 핵심 동작(우선 순위가 높은 데이터부터 먼저 처리하는)과 맞아 떨어져서

• 파이썬 모듈: heapq

• c언어로 구현

5. 위상정렬(tropological sort)

• 일의 순서가 있는 작업을 순서에 맞게 정렬하는 알고리즘
• 바로 진행할 수 있는 일(진입차수가 0인 일)을 먼저 해결하고 관련 작업의 진입차수를 1씩 낮추면서 새롭게 진입차수가 0이 된 작업들을 해결하는 방식
• 큐를 활용해 구현
• wiki

6. 계수 정렬(counting sort)

• 데이터에 의존하는 정렬 방식
• 데이터의 빈도수로 정렬
• 한계: 빈도수 배열에 저장할 값의 범위가 듬성 듬성 있거나, 음수가 있으면 계수 정렬하기가 매우 곤란해진다.
• 함께 읽어볼 자료

13-2 문제

1. 문자열 내 마음대로 정렬하기

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

from operator import itemgetter

def solution(strings, n):
    alphabet_sorted = sorted(strings)
    return sorted(alphabet_sorted, key = itemgetter(n))

lambda가 편하긴 하다...

2. 정수 내림차순으로 배치하기

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

def solution(n: int) -> int:
    s = str(n)
    sorted_digits = sorted(s, reverse = True)
    return int("".join(sorted_digits))

3. K번째 수

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

from typing import List, Tuple

def solution(array: List[int], commands: List[Tuple[int, int, int]]) -> List[int]:
    
    answer: List[int] = []
    
    for i, j, k in commands:
        answer.append(sorted(array[i-1:j])[k-1])
    
    return answer

4. 가장 큰 수

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

from functools import cmp_to_key
from typing import List

def solution(numbers:List[int]) -> str:
    strs: List[str] = list(map(str, numbers))
    
    def compare(a: str, b: str) -> int:
        if a + b > b + a:
            return -1
        if a + b < b + a:
            return 1
        return 0
    sorted_strs = sorted(strs, key=cmp_to_key(compare))
    result = "".join(sorted_strs)
    if result[0] != "0":
        return result
    else:
        return "0"

5. 튜플

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

from typing import List

def solution(s: str) -> List[int]:
    inner = s[2:-2]
    subset_strings = inner.split("},{")
    
    subsets: List[List[int]] = []  
    for subset_str in subset_strings:
        number_strings = subset_str.split(",")
        numbers = [int(num) for num in number_strings]
        subsets.append(numbers)
    subsets.sort(key=len)
    
    result: List[int] = []
    seen = set()
    for subset in subsets:
        for num in subset:
            if num not in seen:
                seen.add(num)
                result.append(num)
    return result

6. 지형 이동(어려움)

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

from heapq import heappush, heappop
from typing import List, Tuple

def solution(land: List[List[int]], height: int) -> int:
    n = len(land)
    visited: List[List[bool]] = [[False] * n for _ in range(n)]
    total_cost = 0
    
    # 상, 우, 하, 좌
    directions: List[Tuple[int, int]] = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    
    # 우선순위 큐: 현재 칸까지 누적비용, 행, 열
    pq : List[Tuple[int, int, int]] = []
    heappush(pq, (0, 0, 0))
    
    # 주변 노드 탐색
    di = [-1, 0, 1, 0]
    dj = [0, 1, 0, -1]
    visited = [[False] * n for _ in range(n)]
    # 시작 노드 추가
    q = []
    
    heappush(q, [0,0,0])
    
    while pq:
        cost, r, c = heappop(pq)
        if visited[r][c]:
            # 이미 처리한 칸이면 건너뛰기
            continue
        visited[r][c] = True
        total_cost += cost
    
        for dr, dc, in directions:
            nr, nc = r + dr, c + dc
            if not(0 <= nr < n and 0 <= nc < n):
                continue
            if visited[nr][nc]:
                continue
            
            diff = abs(land[r][c] - land[nr][nc])
            # 높이차가 height보다 크면 diff, 아니면 0
            move_cost = diff if diff > height else 0
            heappush(pq, (move_cost, nr, nc))
            
    return total_cost

14-1 시뮬레이션 ⭐⭐

노하우

1. 푸는 방법
   • 하나의 문제를 최대한 여러 개로 분리
   • 예외 처리가 필요하다면 독립 함수로 구현(구현할 게 너무 많다)
2. 행렬 연산
   • 굉장히 많이 사용함
3. 좌표 연산
   • 2차원 좌표 사용
4. 대칭, 회전 연산(길이가 N인 정사각행렬)
   • 좌우 대칭: 일반화 A[i,j] = A[i, (N-1)-j]
     
   • 상하 대칭: 일반화 A[i,j] = A[(N-1)-j, i]
   • 회전 일반화(반시계 90도): 일반화 A[i,j] = A[(N-1)-j, i]
     
   • 회전 일반화(반시계 90도): 일반화 A[i,j] = A[(N-1)-j, N-1-j]

14-2 문제

1. 이진 변환

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

from typing import List

def decimal_to_binary(n: int) -> str:
    if n == 0:
        return '0'
    result: str = ""
    while (n > 0):
        result = str(n % 2) + result
        n //= 2
    return result

def solution(s: str) -> List[int]:
    count_transform: int = 0
    count_removed_zeros: int = 0
    
    while (s != "1"):
        zeros: int = s.count('0')
        count_removed_zeros += zeros
        s = s.replace('0', '')
        
        length: int = len(s)
        s = decimal_to_binary(length)
        count_transform += 1
    return [count_transform, count_removed_zeros]

2. 롤케이크 자르기

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

from collections import Counter
from typing import List

# 풀이가 이해되지 않아서 우선 답을 차근차근 따라가봄
def solution(topping: List[int]) -> int:
    # 결과값을 저장할 변수 초기화
    split_count: int = 0
    
    # 토핑의 개수를 세어서 딕셔너리에 저장
    topping_counter: Counter = Counter(topping)
    
    # 절반에 속한 토핑의 종류를 저장할 집합
    half_topping_set: set = set()
    
    # 롤케이크를 하나씩 절반에 넣으면서 확인
    for t in topping:
        # 절반에 토핑을 추가하고, 해당 토핑의 전체 개수를 줄임
        half_topping_set.add(t)
        topping_counter[t] -= 1
        
        # 토핑의 전체 개수가 0이면 딕셔너리에서 제거
        if topping_counter[t] == 0:
            topping_counter.pop(t)
            
        if len(half_topping_set) == len(topping_counter):
            split_count += 1
        
    # 공평하게 나눌 수 있는 방법의 수 반환
    return split_count

3. 카펫

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

from typing import List, Optional, Tuple

def solution(brown: int, yellow: int) -> List[int]:

    total : int = brown + yellow
    for width in range(3, int(total **0.5) + 1):
        if total % width == 0:
            height = total // width
            
            yellow_area = (width - 2) * (height - 2)
            if yellow_area == yellow:
                return [max(width, height), min(width, height)]
    return None

4. 점프와 순간 이동

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

def solution(n: int) -> int:
    bettery_usage = 0
    
    while (n > 0):
        if n % 2 == 1:
            n -= 1
            bettery_usage += 1
        else:
            n //= 2
    return bettery_usage

5. 캐릭터 좌표

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