16. 그리디(Greedy)

1) 그리디 개념

문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선을 선택, 그 선택 번복 X ⇒ 그리디 알고리즘은 지역 최적해를 추구한다

* 부분적으로 최적해를 구한다고 할 수 있어도 전체적으로 최선의 해를 구했는지는 불확실

그리디 알고리즘으로 거스름돈 내어주기

상황) 손님에게 8원을 거슬러 줘야 하는데 동전 종류가 5, 4, 1원만 있음, 이때 동전 개수를 가장 적게 만들기 위해 그리디 알고리즘 활용

1. 가장 값이 큰 동전부터 주기. 그리디 알고리즘은 현재 상황에서 최선의 선택을 하니 값이 가장 큰 동전부터 준다고 생각. → 5원부터 생각 * 5원부터 거슬러 주는 선택은 이후 거스름돈을 주는 선택에 영향을 줌
2. 나머지 3원은 1원 3개를 주는 방법 → 총 4개의 동전으로 거스름돈을 줌
3. 이 방법은 최선은 아님. 4원 2개를 주는 것이 더 좋음 → 그리디 알고리즘은 가장 큰 값을 먼저 선택할 수 밖에 없음. 그래서 항상 최적의 해를 보장 X
   

그리디 알고리즘이 최적해를 보장하려면?

그리디 알고리즘은 특정한 상황에서 최적해를 보장, 이를 잘 활용하면 문제를 해결 가능

• 최적 부분 구조(Optimal Substructure) : 부분해를 푸는 과정이 최적해를 구하는 과정과 일치
• 그리디 선택 속성(Greedy Selection Property) : 선택 과정이 다른 과정에 영향 없음
  

2) 최소 신장 트리

그리디 알고리즘을 사용하는 대표적인 트리 형태의 자료구조

신장 트리(Spanning Tree)란?

모든 정점이 간선으로 연결되어 있고 간선 개수가 정점 개수보다 하나 적은 그래프

최소 신장 트리(Minimum Spanning Tree, MST)란?

신장 트리 중 간선의 가중치 합이 최소인 트리

경우에 따라 최소 신장 트리는 하나가 아닐 수도 있음

eg. 항공기의 운항 경로 최적화할 때 활용, 네트워크 분야에서 많이 활용

최소 신장 트리를 구하는 그리디 알고리즘

프림 알고리즘(Prim’s Algorithm)으로 최소 신장 트리 구하기

로버트 프림이 만든 알고리즘

1. 임의의 정점을 하나 선택해서 최소 신장 트리에 추가
2. 최소 신장 트리와 연결되어 있는 정점 중 가장 가중치가 적은 정점을 최소 신장 트리에 추가(그리디적 선택), 순환을 형성하지 않은 정점을 추가
3. 과정 2를 신장 트리 조건에 만족할 때까지 반복
   

크루스칼 알고리즘으로 최소 신장 트리 구하기

모든 간선을 가중치 기준으로 오름차순 정렬한다는 점 이외의 나머지 규칙은 프림 알고리즘과 동일

1. 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬
2. 가중치가 낮은 간선부터 최소 신장 트리에 하나씩 추가(그리디적 선택), 순환 형성 X
3. 과정 2를 신장 트리 조건에 만족할 때까지 반복
   

3) 배낭 문제(Knapsack Problem)

배낭에 담을 수 있는 최대 무게가 존재, 무게와 가치가 다른 짐들이 있을 때, 잘 조합해서 배낭의 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제

배낭 문제의 목표 - 최대한 배낭에 높은 가치의 짐을 넣는다

짐을 쪼갤 수 있는 부분 배낭 문제(Fractional Knapsack Problem)

부분 배낭 문제를 해결하려면 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 알고리즘 사용

1. 짐 별로 무게당 가치를 구하기
2. 무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣기 2-1. 배낭 용량이 짐 무게보다 크면 짐을 쪼개서 넣기
3. 과정 2를 배낭이 허용하는 용량이 0이 될 때까지 수행
   

짐을 쪼갤 수 없는 0/1 배낭 문제(0/1 Knapsack Problem)

이 문제는 짐을 쪼갤 수 없어서 지금 선택한 짐이 다음 짐 선택에 영향을 줌

그리디 알고리즘 적용 시 최적의 해 구할 수 없음(동적 계획법으로 접근 필요)

0/1 배낭 문제는 그리디 알고리즘으로 근사해를 구할 수 있다고 함

4) 몸 풀기 문제

문제 80) 거스름돈 주기

거스름돈 amount가 있을 때 화폐 단위 [1, 10, 50, 100]을 최소한으로 사용한 화폐 리스트를 반환

def solution(amount):
    lists = [100, 50, 10, 1]
    changes = []

    for c in lists:
        while amount >= c:
            changes.append(c)
            amount -= c

    return changes

assert solution(123) == [100, 10, 10, 1, 1, 1]
assert solution(350) == [100, 100, 100, 50]

5) 합격자가 되는 모의 테스트

문제 84) 귤 고르기

from collections import Counter

def solution(k, tangerine):
    cnt = Counter(tangerine)
    res, tot = 0, 0

    lists = sorted(cnt.values(), reverse=True)

    for count in lists:
        tot += count
        res += 1

        if tot >= k:
            break

    return res

assert solution( 6, [1, 3, 2, 5, 4, 5, 2, 3]) == 3
assert solution( 4, [1, 3, 2, 5, 4, 5, 2, 3]) == 2
assert solution( 2, [1, 1, 1, 1, 2, 2, 2, 3]) == 1

15. 동적 계획법(Dynamic Programming)

1) 동적 계획법 개념

동적 계획법 : 전체 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들을 해결하고, 이것들을 활용하여 전체 문제를 해결하는 방법
활용 조건

• 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 함
• 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 함
  

* 동적 계획법은 작은 문제들이 같아야 하고 반복되어야 함   → 최적 부분 구조(Optimal Substructure) : 작은 문제의 해결책의 합으로 큰 문제를 해결할 수 있는 구조   → 중복 부분 문제(Overlapping Subproblems) : 큰 문제를 나누었을 때 작은 문제가 여러 개 반복되는 문제

점화식 세우기와 동적 계획법

동적 계획법으로 문제 해결 절차

1. 문제를 해결하는 해가 이미 있다고 가정
2. 종료 조건을 설정
3. 과정 1, 2를 활용해 점화식 세우기
   

점화식 구현 : 재귀 활용

재귀 - 재귀 함수의 반환값을 활용한다는 특징이 있음

Fact(N):
    if (N이 1이면) 1 반환 # 종료 조건
    else Fact(N-1) * N 반환 # 일반

호출한 함수가 많으면 많을수록 스택 메모리에 함수 호출 정보가 많이 쌓임 → 입력값이 크다면 메모리 한계로 런타임 오류 발생 가능 ⇒ 재귀 호출 사용 전에 항상 메모리 한계에 대한 생각을 하고 이 문제가 발생하지 않도록 주의

재귀 호출해서 문제 발생 시 해결 방안

1. 재귀 호출 자체를 쓰지 않는 법 → 반복문
2. 재귀 호출의 횟수를 줄이는 법 → 메모이제이션
   

재귀 호출의 횟수를 줄여주는 메모이제이션

메모이제이션 : 이미 계산한 값을 저장해두었다가 이후 쓸 일이 있을 때 활용하는 개념 ⇒ 함수의 결과를 메모이제이션해서 재귀 호출을 다시 하는 것이 아니라 메모이제이션을 활용해서 바로 계산

점화식 구현 : 재귀 + 메모이제이션 활용

메모이제이션 조합

1. 메모이제이션을 위한 저장소 생성 : 이미 구한 해를 저장할 공간을 생성
2. 재귀 함수 정의 : 점화식을 재귀로 표현할 함수를 정의, 이때 함수의 세부 구현은 고려 X
3. 재귀 함수의 종료 조건을 정의 : eg) 피보나치 수의 첫 번째, 두 번째 수는 1로 정해져 있으므로 메모이제이션 저장소에 해를 미리 넣어두고 종료 조건으로 생각
4. 재귀 함수의 일반 연산 처리 : 보통 동적 계획법에서는 점화식으로 나머지 문제 처리, 그 과정에서 구한 결과값은 메모이제이션 저장소에 저장

fibodata[1...N] # 메모이제이션을 위한 배열 선언, 0으로 초기화
fibo(N) : (함수 정의)
    if(fibodata[N] != 0) fibodata[N] 반환 # 메모이제이션 활용
    if(N이 2 이하이면) fibodata[N]에 1 삽입 # 메모이제이션, 종료 조건
    else fibodata[N]에 fibo(N-1) + fibo(N-2) 삽입 # 메모이제이션, 일반항

fibodata[N] 반환

문제 해결 과정

• 점화식 작성(가정한다)
• 재귀 방식으로 풀어보기(반복한다)
• 동적 계획법으로 재귀 + 메모이제이션으로 구현(기억한다)

점화식으로 문제를 작은 문제로 나눠서 접근하는 과정 공부(최적 부분 구조)

메모이제이션으로 반복되는 작은 문제에 연산 횟수를 효율적으로 줄일 수 있음(중복 부분 문제)

최장 증가 부분 수열(Long Increasing Subsequence, LIS)

부분 수열이란?

주어진 수열 중 일부를 뽑아 새로 만은 수열을 의미, 이때 각각의 원소는 전후 관계 유지

최장 증가 부분 수열이란?

부분 수열의 원소가 오름차순을 유지하면서도 길이가 가장 긴 수열을 의미 eg) [1, 4, 2, 3, 1, 5, 7, 3] ⇒ [1, 2, 3, 5, 7]

최장 증가 부분 수열은 엄격하게 증가하는 오름차순이어야 함. eg) [1, 1, 3, 5]는 같은 값이 존재하므로 LIS가 아님

LIS 특징

• 숫자가 점점 증가함
• 원소 간의 전후 관계는 유지함
  

LIS의 길이 동적 계획법으로 구하기

전체 수열의 LIS 길이를 구하는 문제는 각 숫자로 끝나는 LIS 길이 중 최댓값을 구하는 문제로 바꾼 것임을 알 수 있음(최적 부분 구조), 각 숫자로 끝나는 LIS를 구할 때 이전 LIS 길이를 참조함

• dp[N] = arr[N]을 마지막 원소로 하는 LIS 길이

dp로 점화식을 세우면

• dp[N] = max(dp[K]) + 1(단, K는 1 ≤ K < N, arr[K] < arr[N]
• dp[1] = 1(종료 조건)
  

최장 공통 부분 수열(Longest Common Subsequence, LCS)

컴퓨터 과학에서는 수열의 의미를 좀 더 폭넓게 해석 → 특정 순서로 나열한 객체를 의미, 즉 객체는 문자, 숫자 등의 자료형이므로 컴퓨터 과학에서 부분 수열은 특정 순서로 객체를 나열한 것

$\therefore$ 최장 공통 부분 수열이란 두 수열이 어떤 기준에 따라 양쪽에서 공통으로 발견할 수 있는 가장 긴 부분 수열을 의미

부분 수열은 원소 사이의 순서만 유지하면 되고 반드시 연속할 필요 X

LCS 길이 찾는 방법?

입력값을 작게 하여 반복하여 풀 수 있는 작은 문제가 나오는지에 집중

LCS의 길이 점화식 생각하기

• 두 문자열의 특정 문자가 같은지
• 같다면 찾은 두 문자의 위치가 이전에 찾은 문자의 다음에 있는지
  

LCS 길이 알고리즘 분석

총 연산 횟수는 dp를 채우는 것과 같으므로 O(N*M)

2) 몸 풀기 문제

문제 70) LCS 길이 계산하기

주어진 두 개의 문자열 str1과 str2에 대해 최장 공통 부분 수열의 길이를 계산하는 함수 구현

def solution(str1, str2):
  x = len(str1)
  y = len(str2)

  dp = [[0 for _ in range(y + 1)] for _ in range(x + 1)]

  for i in range(1, x + 1):
    for j in range(1, y + 1):
      if str1[i - 1] == str2[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[x][y]

assert solution("ABCBDAB", "BDCAB") == 4
assert solution("AGGTAB", "GXTXAYB") == 4

3) 합격자가 되는 모의 테스트

문제 73) 피보나치 수

2 이상의 n이 입력되었을 때 n 번째 피보나치 수를 1234567로 나눈 나머지를 반환하는 함수 구현

def solution(n):
    dp = [0, 1]

    for i in range(2, n + 1):
        dp.append((dp[i - 1] + dp[i - 2]) % 1234567)

    return dp[n]

14. 시뮬레이션(Simulation)

1) 시뮬레이션 문제 풀이 노하우

시뮬레이션 : 문제에 주어진 상황을 완벽하게 이해하고 이를 코드로 구현하는 과정

시뮬레이션 문제를 푸는 방법

다른 알고리즘처럼 일반화한 방법으로 설명하거나 풀 수 없음 → 주어진 상황에 따라 해결 방식 결정

- 하나의 문제를 최대한 여러 개로 분리 - 예외 처리가 필요하다면 독립 함수로 구현

행렬 연산

시뮬레이션 문제에 행렬 연산은 굉장히 많이 활용하는 기법

행렬 덧셈과 뺄셈, 그리고 곱셈

각 행렬에서 같은 위치에 있는 값끼리 더하거나 빼는 연산

이 연산을 하려면 사용하는 두 행렬의 크기가 같아야 함, 다르면 덧셈, 뺄셈 불가능

행렬 곱셈은 곱셈 순서가 중요하며 A → B 순서로 곱했다면 행렬 A의 행, 행렬 B의 열 크기가 일치해야 하고 곱셈의 결과는 행렬 A의 열, 행렬 B의 행 크기가 됨

전치 행렬

전치 행렬은 arr[i][j]를 arr[j][i]로 바꾸는 연산을 의미, 쉽게 말해 행과 열의 위치를 바꾸는 것

좌표 연산

시뮬레이션 문제에서는 조건에 따라 이동을 구현하는 경우가 많음 → 2차원 좌표를 사용하면 유용

좌표 배열로 표현하기

좌표를 배열로 표현하는 방법은 좌푯값에 해당하는 배열의 위치를 활용하는 것

 eg. (3, 4) → arr[4][3] = 1

좌표 이동 오프셋값으로 쉽게 표현하기

좌표를 활용하는 대부분의 문제는 현재 위치를 이동하는 문제가 많음 But, 좌표의 이동을 if문의 연속으로 표현하면 구현해야 하는 양이 너무 많아 좋지 않음    → 좌표의 이동을 오프셋값을 이용해 표현하면 훨씬 깔끔하게 코드 구현 가능    eg. 오프셋 배열이 있으면 8번의 if문 대신 for문 한번만 돌리면 되므로 편리함

for i in range(1, 9):
    arr[curr_y + dy[i]][curr_x + dx[i]] 

대칭, 회전 연산

01) 대칭과 회전은 조금만 침착하게 생각하면 쉽게 구현 가능

 eg. arr[[4, 3, 2], [5, 6, 5], [1, 2, 4]]

02) 길이가 N인 정사각형 배열에서 좌우 대칭을 일반화하면 A[i, j] = A[i, (N - 1) - j]와 같이 표현 가능

 eg. arr[0][0] → arr[0][2], arr[0][2] → arr[0][0]

03) 길이가 N인 정사각형 배열에서 90도, 반 시계 방향으로 회전하는 것을 일반화하면 A[i, j] = A[i, (N - 1) - i]와 같이 표현 가능

 eg. arr[0][0] → arr[2][0], arr[0][1] → arr[1][0]

2) 몸 풀기 문제

문제 62) 배열 회전하기

2차원 배열 arr을 시계 방향으로 90도 * n 번 회전하는 함수 작성

def solution(arr, n):
  k = len(arr)
  n = n % 4

  for _ in range(n):
    res = [[0 for _ in range(k)] for _ in range(k)]
    for i in range(k):
      for j in range(k):
        res[j][k - 1 - i] = arr[i][j]

    arr = res

  return arr

assert solution(
    [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
        [13, 14, 15, 16]
    ], 1
) == [
    [13, 9, 5, 1],
    [14, 10, 6, 2],
    [15, 11, 7, 3],
    [16, 12, 8, 4]
]

assert solution(
    [
        [1, 2, 3, 4],
        [5, 6, 7, 8],
        [9, 10, 11, 12],
        [13, 14, 15, 16]
    ], 2
) == [
    [16, 15, 14, 13],
    [12, 11, 10, 9],
    [8, 7, 6, 5],
    [4, 3, 2, 1]
]

3) 합격을 위한 모의 테스트

문제 65) 이진 변환

0과 1로 이루어진 문자열 s가 주어지고 s가 "1"이 될 때까지 계속해서 이진 변환을 할 때 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 배열에 담아 반환하는 함수 완성

def solution(s):

    transform = 0
    zero = 0

    while s != "1":
        transform += 1
        zero += s.count("0")
        s = bin(s.count("1"))[2:]

    return [transform, zero]

13. 정렬(Sort)

1) 정렬 개념

정렬(sort) : 사용자가 정의한 순서로 데이터를 나열하는 것

정렬이 필요한 이유

데이터를 정렬하면 원하는 데이터를 쉽게 찾기가 가능(eg. 이진 탐색 트리)

삽입 정렬(Insertion Sort)

데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬

삽입 정렬의 시간 복잡도는 최악의 경우 O(N^2), 최선의 경우 O(N)

병합 정렬(Merge Sort)

정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬

* 이런 방식을 분할 정복(Divide and Conquer)이라고 함

* 병합 정렬의 핵심 : ‘병합할 때 부분 정렬하는 부분을 어떻게 구현해야 하는가?’

병합 정렬의 시간 복잡도

병합 정렬의 성능은 결국 병합 횟수가 결정

나누는 횟수 : logN 합치는 횟수 : NlogN(N개를 병합하는 과정을 logN번 진행)     $\therefore$ O(NlogN)

힙 정렬(Heap Sort)

힙이라는 자료구조를 사용해 정렬 힙 정렬을 하기 위해서 먼저 주어진 데이터로 힙을 구축해야 함

힙이란?

힙은 특정 규칙이 있는 이진 트리, 규칙에 따라 최대 힙, 최소 힙으로 나눔

최대 힙 : 부모 노드가 자식 노드보다 큼 최소 힙 : 부모 노드가 자식 노드보다 작음

* max_heapify() : 특정 노드가 최대 힙의 규칙을 만족하지 못하면 힙을 구축하는 과정을 아래로 내려가면서 반복하는 동작

힙 정렬 과정 : 최대 힙

최대 힙에서 힙 정렬은 루트 노드가 가장 큰 값이므로 루트 노드의 값을 빼서 저장하기만 하면 됨

But, 루트 노드의 값을 뺀 이후 최대 힙을 유지하는 것이 중요

힙 정렬의 시간 복잡도

데이터는 N개이고 각 데이터에 대해 힙 정렬을 수행하면 O(N*logN)

우선순위 큐

우선순위가 높은 데이터부터 먼저 처리하는 큐 즉, 우선순위에 따라 pop을 하는 큐

우선순위 큐의 내부 동작은 힙과 매우 유사하므로 우선순위를 구현할 때 힙을 활용하는 것이 효율적

우선순위 큐의 핵심 동작 : 우선순위가 높은 데이터를 먼저 pop하는 것

최소 힙, 최대 힙은 특정 값을 루트 노드에 유지하는 특징이 있고, 이는 우선순위 큐의 핵심 동작과 맞아 떨어지므로 힙을 활용하면 우선순위 큐를 효율적으로 구현할 수 있다는 것을 알 수 있음

힙으로 우선순위 큐 구현하기

데이터 자체에 우선순위를 직접 정하고 싶다면 튜플 형태로 (우선순위, 데이터)를 heappush()에 전달

heapq의 시간 복잡도

힙 정렬의 삽입, 삭제 연산의 효율과 완전히 동일

원소의 개수가 N이라고 할 때, 시간 복잡도는 heapify()는 O(N)이고, heappush() / heappop() 둘 다 O(logN)

위상 정렬(Topological Sort)

일의 순서가 있는 작업을 순서에 맞춰 정렬하는 알고리즘

위상 정렬은 일의 순서가 중요하므로 반드시 간선의 방향이 있어야 함

위상 정렬과 진입차수

위상 정렬은 자신을 향한 화살표 개수를 진입차수로 정의하여 진행

위상 정렬의 시간 복잡도

모든 정점의 간선을 딱 한 번씩만 지나므로 시간 복잡도는 O(|V|+|E|)

계수 정렬(Counting Sort)

계수 정렬은 데이터에 의존하는 정렬 방식, 데이터의 빈도수로 정렬 * 결과를 확인할 때 리스트의 첫 번째 데이터부터 하나씩 그 값만큼 반복하여 출력

계수 정렬의 한계

계수 정렬의 핵심 동작은 빈도수를 세어 빈도수 배열에 저장하는 것 → 빈도수 배열에 저장할 값의 범위가 듬성듬성 있거나, 음수가 있으면 계수 정렬을 하기 매우 곤란함

계수 정렬의 시간 복잡도

값의 최솟값~최댓값 범위 크기가 K라면 빈도수 배열에서 K + 1만큼 탐색해야 하므로 계수 정렬의 시간 복잡도는 O(N+K)

2) 몸 풀기 문제

문제 54) 계수 정렬 구현하기

인자로 받은 문자열 s를 계수 정렬로 정렬하여 반환하는 함수 구현

def solution(s):
  count = [0] * 26
  res = ""

  for i in s:
    count[ord(i) - ord('a')] += 1

  for i in range(len(count)):
    if count[i] > 0:
      for j in range(count[i]):
        alp = i + ord('a')
        res += chr(alp)

  return res

assert solution("hello") == "ehllo"
assert solution("algorithm") == "aghilmort"

문제 55) 정렬이 완료된 두 배열 합치기

이미 정렬이 완료되어 있는 두 배열 arr1, arr2를 받아 병합 정렬하는 함수 구현

def solution(arr1, arr2):
  res = []
  i, j = 0, 0

  while i < len(arr1) and j < len(arr2):
    if arr1[i] < arr2[j]:
      res.append(arr1[i])
      i += 1
    else:
      res.append(arr2[j])
      j += 1

  res.extend(arr1[i:])
  res.extend(arr2[j:])

  return res

assert solution([1, 3, 5], [2, 4, 6]) == [1, 2, 3, 4, 5, 6]
assert solution([1, 2, 3], [4, 5, 6]) == [1, 2, 3, 4, 5, 6]

3) 합격자가 되는 모의 테스트

문제 56) 문자열 내 마음대로 정렬하기

문자열로 구성된 리스트 strings와 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하기

def solution(strings, n):

  return sorted(strings, key=lambda s: (s[n], s))

assert solution(["sun", "bed", "car"], 1) == ["car", "bed", "sun"]
assert solution(["abce", "abcd", "cdx"], 2) == ["abcd", "abce", "cdx"]

문제 57) 정수 내림차순으로 배치하기

정수 n을 받아 n의 각 자릿수를 내림차순으로 정렬한 새로운 정수 반환

def solution(n):
  lists = list(map(int, str(n)))

  lists.sort(reverse=True)

  res = int(''.join(map(str, lists)))

  return res

assert solution(118372) == 873211

문제 58) K번째 수

배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때 k번째에 있는 수를 구하려고 함. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 주어질 때 commands의 모든 원소에 대하여 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 반환하는 함수 작성

def solution(ary, commands):
  res = []

  for c in commands:
    i, j, k = c

    sort_ary = sorted(ary[i-1:j])

    res.append(sort_ary[k-1])

  return res

assert solution(
  [1, 5 ,2, 6, 3, 7, 4], 
  [[2, 5, 3], [4, 4, 1], [1, 7, 3]]) == [5, 6, 3]

12. 백트래킹(Back Tracking)

1) 백트래킹과 백트래킹 알고리즘

백트래킹이란?

어떤 가능성이 없는 곳을 알아보고 되돌아가는 것

백트래킹 알고리즘이란?

가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘 → 문제마다 효율 다름

답을 찾는 과정에서 가능성이 없는 곳에서 백트래킹

백트래킹을 통해 가능성 없는 탐색 대상 배제 가능하여 탐색 효율이 완전 탐색보다는 좋음

유망 함수란?

백트래킹 알고리즘의 핵심, ‘해가 될 가능성을 판단하는 것’ → 그 가능성은 유망 함수라는 것을 정의하여 판단

* 백트래킹 알고리즘 과정

1. 유효한 해의 집합 정의
2. 위 단계에서 정의한 집합을 그래프로 표현
3. 유망 함수 정의 → 특정 조건을 정의하는 것 eg) 처음에 뽑은 숫자가 3 미만이면 백트래킹
4. 백트래킹 알고리즘을 활용하여 해를 찾음
   

2) 몸 풀기 문제

문제 47) 1부터 N까지 숫자 중 합이 10이 되는 조합 구하기

정수 N을 입력받아 1부터 N까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환
제약 조건 - 숫자 조합은 오름차순, 같은 숫자는 한 번만 선택 가능

def solution(n):
  res = []

  def bt(n, start, tot, cur_sum, cur, res):
    if cur_sum == tot:
      res.append(cur.copy())
      return res

    for i in range(start, n+1):
      if cur_sum + i <= tot:
        cur.append(i)
        cur_sum += i

        bt(n, i+1, tot, cur_sum, cur, res)

        cur.pop()
        cur_sum -= i

  bt(n, 1, 10, 0, [], res)

  return res

assert solution(5) == [[1, 2, 3, 4], [1, 4, 5], [2, 3, 5]]
assert solution(2) == []
assert solution(7) == [[1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5],[2, 3, 5], [3, 7], [4, 6]]

문제 48) 스도쿠 퍼즐

9 x 9 스도쿠 보드를 다 채워 완성된 스도쿠 보드를 반환하는 함수 작성
해는 유일하지 않을 수 있음
규칙 1) 가로줄, 세로줄에는 1부터 9까지의 숫자가 한 번씩 나타나야 함
규칙 2) 9 x 9 보드를 채울 9개의 작은 박스에도 1부터 9까지 숫자가 한 번씩 나타나야 함

def solution(board):

  def is_valid(row_val, col_val, num):
    return not (in_row(num, row_val) or in_col(num, col_val) or in_box(num, row_val, col_val))

  def in_row(num, row_val):
    return num in board[row_val]

  def in_col(num, col_val):
    for i in range(len(board)):
      if board[i][col_val] == num:
        return True

    return False

  def in_box(num, row_val, col_val):
    start_row = row_val - row_val % 3
    start_col = col_val - col_val % 3

    for i in range(3):
      for j in range(3):
        if board[start_row + i][start_col + j] == num:
          return True

    return False

  def find_empty():
    for i in range(len(board)):
      for j in range(len(board[i])):
        if board[i][j] == 0:
          return (i, j)

    return None

  empty_loc = find_empty()
  if not empty_loc:
    return board
  row, col = empty_loc

  for num in range(1, 10):
    if is_valid(row, col, num):
      board[row][col] = num
      if solution(board):
        return board
      board[row][col] = 0

  return False

assert solution([
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9],
]) == [
    [5, 3, 4, 6, 7, 8, 9, 1, 2],
    [6, 7, 2, 1, 9, 5, 3, 4, 8],
    [1, 9, 8, 3, 4, 2, 5, 6, 7],
    [8, 5, 9, 7, 6, 1, 4, 2, 3],
    [4, 2, 6, 8, 5, 3, 7, 9, 1],
    [7, 1, 3, 9, 2, 4, 8, 5, 6],
    [9, 6, 1, 5, 3, 7, 2, 8, 4],
    [2, 8, 7, 4, 1, 9, 6, 3, 5],
    [3, 4, 5, 2, 8, 6, 1, 7, 9],
]

3) 합격자가 되는 모의 테스트

문제 49) 피로도

유저의 현재 피로도 k와 각 던전 별 최소 필요 피로도, 소모 피로도가 담긴 2차원 배열 dungeons가 매개변수로 주어질 때 유저가 탐험할 수 있는 최대 던전 수를 반환하는 함수 작성

def solution(k, dungeons):
  visited = [False] * len(dungeons)

  def explore(k, visited):
    dun_count = 0

    for i in range(len(dungeons)):
      if not visited[i] and dungeons[i][0] <= k:
        visited[i] = True
        dun_count = max(dun_count, 1 + explore(k - dungeons[i][1], visited))
        visited[i] = False

    return dun_count

  return explore(k, visited)

assert solution(80, [[80, 20], [50, 40], [30, 10]]) == 3

11. 그래프(Graph)

1) 그래프의 개념

그래프 : 노드(Vertex)와 간선(Edge)을 이용한 비선형 데이터 구조      데이터 간의 관계를 표현하는 데 사용

데이터 = 노드(vertex) 노드 간 관계/흐름 = 간선(edge) → 유방향/무방향 가중치 : 관계/흐름의 정도

그래프 용어 정리

그래프의 특징과 종류

그래프는 방향성, 가중치, 순환 특성에 따라 종류 구분 가능

흐름을 표현하는 방향성

방향 그래프(Directed Graph) : 방향이 있는 간선을 포함하는 그래프

무방향 그래프(Undirected Graph) : 방향이 없는 간선을 포함하는 그래프

흐름의 정도를 표현하는 가중치

어떤 데이터는 흐름의 방향 뿐 아니라 양도 중요할 수 있어서 그런 정도를 간선에 표현할 때 가중치를 사용

시작과 끝의 연결 여부를 보는 순환 순환은 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 것을 의미

순환 그래프(Cycle Graph) : 순환이 존재하는 그래프

비순환 그래프(Acycle Graph) : 순환이 존재하지 않는 그래프

그래프 구현

인접 행렬 그래프 표현

인접 행렬은 배열을 활용하여 구현하는 경우 多

배열의 인덱스 = 노드, 배열의 값 = 노드의 가중치

인덱스의 세로 방향 = 출발 노드, 인덱스의 가로 방향 = 도착 노드

인접 행렬의 세로 방향 인덱스 = 출발, 가로 방향 인덱스 = 도착

‘-’로 표현한 가중치는 실제 코드에서는 굉장히 큰 값을 넣거나 -1로 정함

인접 리스트 그래프 표현

적절한 노드 정의

값=정점(v), 가중치(w), 다음 노드(next)를 묶어 관리

동작 과정

1. 우선은 노드 개수만큼 배열 준비

2. 배열의 인덱스는 각 시작 노드를 의미하여 배열의 값에는 다음 노드 연결

   
   

2) 그래프 탐색

깊이 우선 탐색(Depth-First Search, DFS) ⭐깊이 우선 탐색 : 깊게 탐색 후 되돌아오는 특성

시작 노드부터 탐색을 시작하여 간선을 따라 최대 깊이 노드까지 이동하며 차례대로 방문

최대 깊이 노드까지 방문 후 이전 방문한 노드를 거슬러 올라가며 해당 노드와 연결된 노드 중 방문하지 않은 노드로 다시 최대 깊이까지 차례대로 방문

탐색 시작 시 시작 노드 정하고, 스택에 시작 노드 push.

깊이 우선 탐색의 핵심 : 가장 깊은 노드까지 방문한 후에 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있는지 확인

스택을 활용한 깊이 우선 탐색

선입후출의 특성을 가진 스택으로 가장 최근에 방문한 노드 확인 가능

재귀 함수를 활용한 깊이 우선 탐색

스택을 직접 사용하지 않고도 깊이 우선 탐색 구현 가능 → 재귀 함수 활용

재귀 함수를 호출 시 호출한 함수는 시스템 스택이라는 곳에 쌓이므로 깊이 우선 탐색에 활용 가능

dfs(N) : N번 노드를 방문 처리하고 N번 노드와 인접한 노드 중 아직 방문하지 않은 노드를 탐색

너비 우선 탐색(Breadth First Search, BFS) ⭐너비 우선 탐색 : 가중치가 없는 그래프에서 최단 경로 보장

시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘   → 여기서 말하는 거리 : 시작 노드와 목표 노드까지의 차수

너비 우선 탐색 방식을 보면 시작 노드부터 인접한 노드를 모두 방문 후 그 다음 단계의 인접 노드 방문 즉, 먼저 발견한 노드 방문.   → 이런 특성 때문에 너비 우선 탐색 시 큐를 활용

방문 처리 시점이 다른 이유

깊이 우선 탐색은 스택에서 pop하며 방문 처리를 했고, 너비 우선 탐색은 큐에서 push하며 방문 처리 → 탐색 방식이 다르기 때문

깊이 우선 탐색 과정에서는 스택에 다음에 방문할 인접한 노드를 push. 즉, 스택에 push할 노드는 방문 예정인 노드이므로 pop하며 방문 처리해야 함

너비 우선 탐색 과정에서는 지금 방문할 노드를 push. 그래야 인접한 노드부터 탐색 가능

3) 그래프 최단 경로(Shortest Path) 구하기

• 가중치가 없는 그래프에서는 간선 개수가 가장 적은 경로가 최단 경로
• 가중치가 있는 그래프에서는 일반적으로 시작 노드에서 끝 노드까지 이동할 때 거치는 간선의 가중치의 총합이 최소가 되는 것이 최단 경로
  

다익스트라(Dijkstra) 알고리즘 = 데이크스트라 알고리즘 가중치가 있는 그래프의 최단 경로를 구하는 문제는 대부분 다익스트라 알고리즘을 사용

음의 가중치가 있는 그래프일 때

다익스트라 알고리즘은 양의 가중치만 있는 그래프에서만 동작하므로 음의 가중치가 있는 그래프에서 제대로 동작 X

다익스트라 알고리즘은 시작 노드에서 각 노드까지 최소 비용을 갱신하는 과정 반복, 현재까지 구한 각 노드의 최소 비용 중 가장 작은 노드를 선택하여 움직임 = 그리디 알고리즘

** 그리디 알고리즘 : 각 단계에서 가장 좋은 것을 선택하는 전략을 가짐

벨만-포드(Bellman-Ford) 알고리즘 노드에서 노드까지 최소 비용을 구한다는 점에선 다익스트라 알고리즘과 같음

But, 벨만-포드 알고리즘은 매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하므로 음의 가중치를 가지는 그래프에서도 최단 경로를 구할 수 있음

한 번 더 연산을 반복하는 이유? 음의 순환을 찾기 위해!

노드 N의 최단 경로를 구성하는 간선 개수가 N개 이상이면 최단 경로의 간선 개수는 최대 N-1이어야 함 → 음의 순환이 있다는 의미

음의 순환인 N → (N -1) 구간을 반복하면 계속해서 최소 비용(가중치의 합)은 점점 줄어듦

4) 몸 풀기 문제

문제 38) 깊이 우선 탐색 순회

깊이 우선 탐색으로 모든 그래프의 노드를 순회하는 함수 solution() 작성.
start = 시작 노드, graph = [출발 노드, 도착 노드] 쌍들이 들어 있는 리스트
반환 값 = 그래프의 시작 노드부터 모든 노드를 깊이 우선 탐색으로 진행한 순서대로 노드가 저장된 리스트

def solution(graph, start):
  res = []
  nodes_list = {}
  visited = []

  for node in graph:
    if node[0] not in nodes_list:
      nodes_list[node[0]] = [node[1]]
    else:
      nodes_list[node[0]].append(node[1])

  def dfs(node):
    if node not in visited:
      visited.append(node)
      res.append(node)

      if node in nodes_list:
        for neighbor in nodes_list[node]:
          dfs(neighbor)

  dfs(start)

  return res

assert solution([['A', 'B'], ['B', 'C'], ['C', 'D'], ['D', 'E']], 'A') == ['A', 'B', 'C', 'D', 'E']
assert solution([['A', 'B'], ['A', 'C'], ['B', 'D'], ['B', 'E'], ['C', 'F'], ['E', 'F']], 'A') == ['A', 'B', 'D', 'E', 'F', 'C']

문제 39) 너비 우선 탐색 순회

너비 우선 탐색으로 모든 노드를 순회하는 함수 solution()을 작성
시작 노드 = start, (출발 노드, 도착 노드) 리스트 = graph
반환값 = 시작 노드부터 모든 노드를 너비 우선 탐색으로 진행한 순서대로 노드가 저장된 리스트

from collections import defaultdict

def solution(graph, start):
  nodes_dict = defaultdict(list)

  for n, m in graph:
    nodes_dict[n].append(m)

  return bfs(nodes_dict, start)

def bfs(dicts, node):
  visited = []
  qu = []

  for nodes in dicts:
    if nodes == node and node not in visited:
        qu.append(node)
        visited.append(node)

        if node in visited: qu.pop()

    for n in dicts[nodes]:
      if n not in visited:
        qu.append(n)
        visited.append(n)

        if n in visited: qu.pop()

  return visited

assert solution([(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7), (4, 8), (5, 8), (6, 9), (7, 9)], 1) == [1, 2, 3, 4, 5, 6, 7, 8, 9]
assert solution([(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)], 1) == [1, 2, 3, 4, 5, 0]

문제 40) 다익스트라 알고리즘

주어진 그래프와 시작 노드를 이용하여 다익스트라 알고리즘을 구현하는 solution() 구현
인수 : graph - 딕셔너리, 노드의 연결 정보와 가중치 저장 / start - 문자열, 출발 노드
반환값 : 시작 노드부터 각 노드까지 최소 비용과 최단 경로를 포함한 리스트

import heapq

def solution(graph, start):
  dist = {node: float("INF") for node in graph}
  dist[start] = 0 
  priority_qu = []
  path = {node: [] for node in graph}

  # 시작 노드를 우선순위 큐에 삽입
  heapq.heappush(priority_qu, [dist[start], start])

  # 다익스트라 알고리즘 수행
  while priority_qu:
    distance, node = heapq.heappop(priority_qu)

    if dist[node] < distance:
        continue

    # 이웃 노드를 탐색하고 거리를 업데이트
    for v, w in graph[node].items():
      node_dist = distance + w

      # 더 짧은 경로가 발견되면 거리와 경로를 업데이트
      if node_dist < dist[v]:
        dist[v] = node_dist
        heapq.heappush(priority_qu, [node_dist, v])
        path[v] = path[node] + [node]

  result = {node: float("INF") for node in graph}
  for node, shortest_path in path.items(): 
    result[node] = shortest_path + [node]

  return [dist, result]

assert solution({
    'A': {'B':9, 'C':3},
  'B': {'A':5},
  'C': {'B':1}
}, 'A') == [
    {'A':0, 'B':4, 'C':3},
  {
        'A': ['A'],
    'B': ['A', 'C', 'B'],
    'C': ['A', 'C']
    }
]

assert solution({ \
    'A': {'B':1}, \
  'B': {'C':5}, \
  'C': {'D':1}, \
  'D': {}
}, 'A') == [
    {'A':0, 'B':1, 'C':6, 'D':7}, \
  {
        'A': ['A'], \
    'B': ['A', 'B'], \
    'C': ['A', 'B', 'C'], \
    'D': ['A', 'B', 'C', 'D']
    }
]

5) 합격자가 되는 모의 테스트

문제 42) 게임 맵 최단 거리

ROR 게임은 두 팀으로 나눠 진행하며 상대 팀 진영을 먼저 파과하면 이기는 게임. 각 팀은 상대 팀 진영에 최대한 빨리 도착해야 게임을 유리하게 이끌 수 있음
5 x 5 크기의 맵, 검은색 = 벽, 흰색 = 길, 캐릭터 이동은 동, 서, 남, 북 방향으로 한 칸씩 이동
게임 맵이 maps로 주어질 때 우리 팀 캐릭터가 상대 팀 진형에 도착하기 위해 지나가야 하는 길의 최소 개수를 반환하는 solution() 완성

from collections import deque

def solution(maps):
  n, m = len(maps), len(maps[0])
  deq = deque([((0, 0), 1)])
  visited = {(0, 0)}

  while deq:
    loc, dist = deq.popleft()

    for x, y in [[-1, 0], [0, -1], [1, 0], [0, 1]]:
      row = loc[0] + x
      col = loc[1] + y

      # 이동한 위치 범위 안에서 동작
      if row < 0 or row >= n or col < 0 or col >= m:
        continue

      # 이동한 위치에 벽(= 0)이 있는 경우
      if maps[row][col] == 0:
        continue

      next_loc = (row, col)
      if next_loc not in visited:
        deq.append((next_loc, dist + 1))
        visited.add(next_loc)

        # 종료지점
        if next_loc == (n - 1, m - 1):
          return dist + 1

  return -1

assert solution([[1, 0, 1, 1, 1], [1, 0, 1, 0, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 0, 1]]) == 11
assert solution([[1, 0, 1, 1, 1], [1, 0, 1, 0, 1], [1, 0, 1, 1, 1], [1, 1, 1, 0, 0], [0, 0, 0, 0, 1]]) == -1

문제 43) 네트워크

컴퓨터 A, B가 직접 연결되어 있고 컴퓨터 B, C가 직접 연결되어 있을 때 컴퓨터 A, C는 간접 연결되어 있어 정보 교환 가능해서 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있음. 컴퓨터 개수가 n, 연결 정보가 담긴 2차원 배열 computers가 주어질 때 네트워크 개수를 반환하는 solution() 작성

def solution(n, computers):
  visited = [False] * n
  net = 0 # 네트워크 개수

  for i in range(n):
    if not visited[i]:
      dfs(computers, visited, i)
      net += 1

  return net

def dfs(computers, visited, cur):
  visited[cur] = True

  for next_node, connected in enumerate(computers[cur]):
    if connected and not visited[next_node]:
      dfs(computers, visited, next_node)

assert solution(3, [[1, 1, 0], [1, 1, 0], [0, 0, 1]]) == 2
assert solution(3, [[1, 1, 0], [1, 1, 1], [0, 1, 1]]) == 1

10. 집합

1) 집합과 상호 배타적 집합의 개념

집합의 개념

집합 : 순서와 중복이 없는 원소들을 갖는 자료구조(순서X)

집합의 종류

• 특성에 따라 부르는 말이 다양함

유한 집합 : 원소 개수가 유한한 집합

무한 집합 : 원소 개수가 무한한 집합

상호 배타적 집합이란?

상호 배타적 집합 : 교집합이 없는 집합 관계를 의미

A = {1, 2, 3}이고 B = {4, 5, 6, 7}일 때 서로 겹치는 원소가 없으면 교집합이 없다고 할 수 있고, 이를 상호 배타적 집합이라고 함

상호 배타적이지 않은 집합 → 원소 5가 집합 A와 집합 B에 존재하기 때문

상호 배타적 집합의 특성을 활용하는 분야

• 이미지 분할 : 이미지를 서로 다른 부분으로 나누는 데 사용
• 도로 네트워크 구성 : 도로를 구축할 때 각 도로를 서로 교차하지 않도록 설계하는 데 사용
• 최소 신장 트리 알고리즘 구현 : 최소 신장 트리 알고리즘을 구현에서 간선을 추가할 때마다 사이클을 형성하는지 여부 체크
• 게임 개발 : 캐릭터의 동작을 자연스럽게 구현 가능
• 클러스터링 작업 : 각 작업이 서로 겹치지 않도록 구성 가능
  

2) 집합의 연산

배열을 활용한 트리로 집합 표현하기

집합은 배열을 활용한 트리로 구현, 각 집합에는 대표 원소가 필요

대표 원소란?

집합의 원소 중 집합을 대표하는 역할

배열로 집합을 표현한 것이란?

하나의 배열로 상호 배타적 관계를 가지는 집합을 모두 표현한다는 것을 의미

집합 → 트리 형태로 표현 시 배열의 인덱스는 자신을, 배열 값은 부모 노드를 의미

eg) disjoint_set[3] = 9일 때, 부모 노드 = 3

즉, 루트 노드는 값 자체가 배열의 인덱스와 동일

→ 그림에서 값이 가장 큰 원소가 9이므로 배열의 크기는 10으로 잡기

집합 표현 완벽 정리하기

집합을 배열로 구현하기

01 단계) 집합을 배열로 표현 시 초기 상태

초기 각 노드는 자신을 루트 노드로 하였고, 집합에 없는 인덱스는 -1로 처리

02 단계) 집합이 완성되었을 때, 집합 A는 {1, 2, 3, 5, 9}이고, 집합 B는 {4, 8}. 루트 노드는 음영 처리, 점선으로 노드 9의 루트 노드를 찾는 과정 표시(9 → 3 → 2 → 1)

유니온-파인드 알고리즘

집합 알고리즘에 주로 쓰이는 연산은 합치기(Union)와 탐색(Find)이다.

파인드 연산

특정 노드의 루트 노드가 무엇인지 탐색하는 방법

보통 특정 노드가 같은 집합에 있는지 확인 시 사용(찾기 연산)

1) 현재 노드의 부모 노드 확인. 부모 노드 확인 시 부모 노드 = 루트 노드이면 찾기 연산 종료

2) 1에서 찾기 연산이 종료되지 않으면 1을 반복(현재 노드 $\neq$ 부모 노드)

탐색 연산은 재귀 함수로 구현 - 루트 노드를 현재 노드와 부모 노드가 같을 때까지 재귀 실행

파인드 연산의 연산 비용 문제, 경로 압축으로 해결하자

좀 더 효율적으로 파인드 연산을 하기 위해 집합 형태를 유지하면서도 트리 높이를 줄이면 됨

트리의 높이를 줄이는 게 부모 노드를 거치는 과정을 줄일 수 있음

합치기(유니온) 연산

두 집합을 하나로 합치는 연산 = 두 집합의 루트 노드를 같게 하는 것

1) 두 집합에서 찾기 연산을 통해 루트 노드 찾기

2) 찾은 두 루트 노드의 값 비교

3) 두 집합 합침. 두 집합의 루트 노드를 같게 하는 것

합치기 연산의 연산 비용 문제, 랭크로 해결하자

트리의 깊이가 깊어지면 깊어질수록 연산 비용 ↑ ⇒ 개선하기 위해 랭크 필요

* 랭크 개념 도입 목적 : ‘트리의 균형을 유지하기 위함’

랭크란?

현재 노드를 기준으로 하였을 때 가장 깊은 노드까지의 경로 길이를 의미

랭크 기반으로 합치기 연산하기

1) 두 노드의 루트 노드 구하기

2) 1에서 구한 루트 노드의 랭크 비교

2-1) 랭크값이 다르면 랭크값이 큰 루트 노드를 기준으로 삼기

2-2) 랭크값이 같으면 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더함

3) 몸 풀기 문제

문제 33) 간단한 유니온-파인드 알고리즘 구현하기

초기의 노드는 부모 노드를 자신의 값으로 설정했다고 가정하며, 여기서는 각 집합의 루트 노드를 기준으로 루트 노드가 작은 노드를 더 큰 노드의 자식으로 연결하는 방법 사용. operations에 있는 연산을 모두 수행한 후 집합의 개수를 반환하는 solution() 함수 구현

def union(nodes, x, y):

  node1 = find(nodes, x)
  node2 = find(nodes, y)

  nodes[node2] = node1

def find(nodes, x):

  if nodes[x] == x:
    return x
  else:
    nodes[x] = find(nodes, nodes[x])
    return nodes[x]

def solution(k, operations):
  nodes = list(range(k))

  for op in operations:
    if op[0] == 'u':
      union(nodes, op[1], op[2])
    elif op[0] == 'f':
      find(nodes, op[1])

  n = len(set(find(nodes, i) for i in range(k)))
  print("n : ", n)

  return n

k = 3
operations = [['u', 0, 1], ['u', 1, 2], ['f', 2]] # result = 1
solution(k, operations)

k = 4
operations = [['u', 0, 1], ['u', 2, 3], ['f', 0]] # result = 2
solution(k, operations)

4) 합격자가 되는 모의 테스트

문제 36) 전화번호 목록

전화번호부에 적힌 전화번호 중 한 번호가 다른 번호의 접두어인 경우가 있는지 확인. 전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution() 함수의 매개변수로 주어질 때 어떤 번호가 다른 번호의 접두어이면 False, 그렇지 않으면 True를 반환하는 함수 작성

def solution(phone_book):
    phone_book.sort()

    for i in range(len(phone_book) - 1):
        if phone_book[i+1].startswith(phone_book[i]): 
            return False

    return True

09. 트리

1) 트리 개념

트리(Tree) : 데이터를 저장하고 탐색하기에 유용한 구조를 가짐

트리의 특성을 활용하는 분야

계층 구조를 표현하는 용도로 많이 사용(eg. 파일 시스템, 디렉터리 구조)

• 인공지능 : 판단 기준을 만들 때 의사 결정 트리 사용 → 외부에서 입력된 데이터 분류, 상황 예측하는 모델
• 자동 완성 기능 : 트리는 문자열 처리에도 많이 사용 → 검색 엔진에서 자동 검색어 추천 기능(트라이(trie) 트리 구조 활용)
• 데이터베이스 : 데이터를 쉽게 검색, 삽입, 삭제 할 수 있도록 트리 활용하여 데이터를 구조화하고 인덱싱 함(B-트리 or B+트리)
  

나무를 거꾸로 뒤집어 놓은 모양의 트리

트리를 구성하는 노드

루트 노드(Root Node) : 노드 중 가장 위에 있는 노드

노드를 연결하는 에지

간선 or 에지(Edge) : 노드와 노드 사이에 이어주는 선

• 트리는 노드와 노드가 단방향 간선으로 연결
• 루트 노드에서 각 노드까지 경로는 유일

레벨 : 루트 노드로부터 특정 노드까지 거쳐가는 최소한의 간선 수

부모-자식, 형제 관계를 가지는 노드

부모-자식 관계 : 간선으로 연결된 노드들

• 부모 노드(Parent Node) : 간선으로 직접 연결된 노드 중 상대적으로 위에 있는 노드
• 자식 노드(Child Node) : 그 아래에 있는 노드

형제 노드(Sibling Node) : 같은 부모를 갖는 노드

자식이 없는 말단 노드

리프 노드(Leaf Node) : 자식이 없는 노드

아래로 향하는 간선의 개수, 차수

차수(Degree) : 특정 노드에서 아래로 향하는 간선의 개수

2) 이진 트리 표현하기

이진 트리(Binary Tree) : 모든 노드의 최대 차수가 2를 넘지 않는 트리

• 이진 트리는 배열이나 포인터로 구현 가능
  

배열로 표현하기

• 이진 트리의 노드가 N개 일 때, 배열로 이진 트리 생성 시 O(N)이 걸림

배열 - 선형 자료구조 / 트리 - 계층 자료구조

3가지 규칙 필요

1) 루트 노드는 배열 인덱스 1번에 저장

2) 왼쪽 자식 노드의 배열 인덱스 : 부모 노드의 배열 인덱스 x 2

3) 오른쪽 자식 노드의 배열 인덱스 : 부모 노드의 배열 인덱스 x 2 + 1

* 메모리만 넉넉하다면 구현 시간을 단축하는 용도로 Good

이진 트리 순회하기

순회 : 어떤 데이터가 있을 때 그 데이터를 빠짐 없이 방문하는 것을 의미 → 트리에서 데이터를 검색하려면 트리를 순회할 수 있어야 함

트리 순회 방법

• 전위 순회(Preorder) 현재 노드를 부모 노드로 생각했을 때 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 방문
• 중위 순회(Inorder) 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순서로 방문
• 후위 순회(Postorder) 현재 노드를 부모 노드로 생각했을 때 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드 순서로 방문

* 방문 : 탐색에서 방문은 탐색을 마친 상태를 의미, 탐색 과정에서 지나치는 것과 그렇지 않은 것을 구분하기 위해 방문이라는 용어를 사용

전위 순회 과정 살펴보기

01단계) 루트 노드에서 시작

02단계) 현재 노드를 부모로 생각, 다음 왼쪽 자식 노드로 이동

03 단계) 오른쪽 자식 노드 방문

04 단계) 오른쪽 자식 노드가 없을 경우, 현재 노드의 부모 노드로 이동

* 전위 순회는 주로 트리를 복사할 때 많이 사용

중위 순회 과정 살펴보기

01단계) 루트 노드에서 시작 → 왼쪽 자식 노드 이동

02단계) 01단계의 노드를 부모로, 이 노드의 왼쪽 자식 노드 방문/이동

03단계) 부모 노드 방문

04단계) 오른쪽 자식 노드 방문 후 거슬러 올라감

* 중위 순회는 이진 탐색 트리에서 정렬된 순서대로 값을 가져올 때 사용

후위 순회 과정 살펴보기

01단계) 루트 노트에서 시작 → 왼쪽 자식 노드로 이동

02단계) 왼쪽 노드의 자식이 없을 때까지 이동 후 자신 방문

03단계) 오른쪽 노드 방문 후 거슬러 올라가서 부모 노드 방문

04단계) 왼쪽 트리 전체 완료 후 오른쪽 트리 시작할 때도 같은 방식

노드 삭제

• 부모 먼저 삭제 X
• 자식부터 삭제해야 트리가 유지되고, 재귀로 루트 노드까지 삭제 가능

* 자식 노드부터 방문한다는 특성이 있는 후위 순회는 트리 삭제에 자주 활용

포인터로 표현하기

포인터로 트리 표현 시 노드부터 정의 필요

노드는 노드의 값, 왼쪽 자식 노드와 오른쪽 자식 노드를 가짐

포인터로 표현한 트리는 배열과 달리 인덱스 연산을 하지 않으므로, 메모리 공간 낭비 X

3) 이진 트리 탐색하기

이진 트리에서 가장 중요한 부분 : 탐색을 효율적으로 할 수 있도록 트리 구축하는 것

이진 탐색 트리(Binary Search Tree) 구축하기

이진 탐색 트리 정렬 방식 : 데이터 크기를 따져 크기가 작으면 왼쪽 자식 위치에, 크거나 같으면 오른쪽 자식 위치에 배치

이진 탐색 트리 탐색하기

1) 찾으려는 값이 현재 노드의 값과 같으면 탐색을 종료하고 크면 오른쪽 노드 탐색

2) 본인이 찾으려는 값이 현재 노드의 값보다 작으면 왼쪽 노드 탐색

3) 값을 찾으면 종료. 노드가 없을 때까지 계속 탐색했는데 값이 없으면 현재 트리에 값이 없는 것

이진 탐색 트리는 크면 오른쪽, 작으면 왼쪽

모든 탐색 알고리즘에서 탐색 효율을 개선하는 방법은 같음 - 탐색 대상이 아닌 노드를 한 번에 많이 제외할 수 있으면 됨

$\therefore$ 데이터 크기에 따라 하위 데이터 중 한 방향을 검색 대상에서 제외 - 검색 빨라짐

이진 탐색 트리의 시간 복잡도

이진 탐색 트리의 시간 복잡도는 트리 균형에 의존. 즉, 각 노드의 차수가 비슷하게 유지되면서 각 노드의 자식 노드 수가 비슷하게 유지되는 것을 의미

⇒ 트리에 저장된 노드가 N개 일 때 시간 복잡도는 O(logN)

균형 이진 탐색 트리(Balanced Binary Search Tree)

한 쪽으로만 치우쳐지지 않도록 균형을 유지하는 이진 탐색 트리

세부적으로 AVL 트리, 레드-블랙 트리 등으로 구분

이진 트리의 탐색 연산 횟수가 트리 높이에 비례하고 트리의 높이는 logN이므로 탐색 시간 복잡도를 O(logN)으로 유지 가능, But 구현 난이도가 높음

4) 몸 풀기 문제

문제 26) 트리 순회

이진 트리를 표현한 리스트 nodes를 인자로 받아 트리를 표현한 것. 해당 이진 트리에 대해 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 함수 구현

def preorder(nodes, idx):
    res = []
    if idx < len(nodes):
      res.append(nodes[idx])
      res.extend(preorder(nodes, 2 * idx + 1 ))
      res.extend(preorder(nodes, 2 * idx + 2))
    return res

def inorder(nodes, idx):
  res = []
  if idx < len(nodes):
    res.extend(inorder(nodes, 2 * idx + 1))
    res.append(nodes[idx])
    res.extend(inorder(nodes, 2 * idx + 2))
  return res

def postorder(nodes, idx):
  res = []
  if idx < len(nodes):
    res.extend(postorder(nodes, 2 * idx + 1))
    res.extend(postorder(nodes, 2 * idx + 2))
    res.append(nodes[idx])
  return res

def solution(nodes):
  result = [
    preorder(nodes, 0),
    inorder(nodes, 0),
    postorder(nodes, 0)
  ]
  return result

문제 27) 이진 탐색 트리 구현

첫 번째 인수 lst를 이용하여 이진 탐색 트리 생성, 두 번째 인수 search_lst에 있는 각 노드를 이진 탐색 트리에서 찾을 수 있는지 확인하여 True or False를 담은 리스트 result를 반환하는 함수 작성

class Node:
    def __init__(self, item):
        self.left = None
        self.right = None
        self.item = item

class BinaryTree:
  def __init__(self):
    self.root = None

  def insert(self, key):
    self.root = self._insert(self.root, key)

  def _insert(self, root, key):
    if root is None:
      return Node(key)

    if key < root.item:
      root.left = self._insert(root.left, key)
    else:
      root.right = self._insert(root.right, key)

    return root

  def search(self, root, value):
    if root is None or root.item == value:
      return root is not None

    if value < root.item:
      return self.search(root.left, value)
    else:
      return self.search(root.right, value)

def solution(lst, search_lst):
  tree = BinaryTree()
  for value in lst:
    tree.insert(value)

  result = [tree.search(tree.root, value) for value in search_lst]
  return result

5) 합격자가 되는 모의 테스트

문제 28) 예상 대진표

게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution()의 인수로 주어질 때 첫 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는 지 반환

def solution(n,a,b):
    answer = 0
    while a != b:
        a = (a + 1) // 2
        b = (b + 1) // 2
        answer += 1

    return answer

08.해시

1) 해시의 개념

해시(Hash) : 해시 함수를 사용해서 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조

해시 자세히 알아보기

가장 쉽게 볼 수 있는 해시의 예는 연락처이다.

최종으로 얻고자 하는 정보는 전화번호=값(value), 값을 검색하기 위해 활용하는 정보=키(key)

그 사이에 키를 이용해 해시 값 or 인덱스로 변환하는 해시 함수 있음

⇒ 해시 함수는 키를 일정한 해시값으로 변환 시켜 값을 찾을 수 있게 해줌

해시의 특징

1) 해시는 단방향으로 동작 키를 통해 값 찾기 O, but 값을 통해 키 찾기 X

2) 찾고자 하는 값을 O(1)에서 바로 찾을 수 있음 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정 필요 X

3) 값을 인덱스로 활용하려면 적절한 변환 과정을 거쳐야 함 해시 함수가 중간에서 값이 있는 위치를 찾는 데 도움을 줌

$\therefore$ 해시를 사용하면, 순차 탐색할 필요 없이 해시 함수를 활용해서 특정 값이 있는 위치를 바로 찾을 수 있어 탐색 효율이 좋음

해시가 활용되는 실제 사례

1) 비밀번호 관리 해시 함수를 활용해 해싱한 비밀번호를 저장, 반대의 경우도 같음

2) 데이터베이스 인덱싱 DB에 저장된 데이터를 효율적으로 검색 시 해시 활용

3) 블록체인 블록체인에서 해시 함수는 핵심 역할을 함 각 블록은 이전 블록의 해시값을 포함, 이를 통해 데이터 무결성 확인 가능

2) 해시 함수

해시 함수를 구현할 때 고려할 내용

1) 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안됨(0 ~ N-1)

2) 해시 함수가 변환한 값의 충돌은 최대한 적게 발생해야 함

충돌의 의미 : 서로 다른 두 키에 대해 해싱 함수를 적용한 결과가 동일한 것을 의미

자주 사용하는 해시 함수 알아보기

나눗셈법(Division Method) 가장 떠올리기 쉬운 단순한 해시 함수

키를 소수로 나눈 나머지를 활용 ⇒ 키를 소수로 나눈 나머지를 인덱스로 사용 ⇒ 소수를 사용하는 이유 : 다른 수를 사용할 때보다 충돌이 적기 때문

왜 충돌이 많이 발생할까?

N의 약수 중 하나를 M이라고 한다면, 임의의 수 K에 대해 M * K = N이 되는 수가 반드시 있음

K를 주기로 같은 해시값이 반복됨을 알 수 있음

$\therefore$ K는 1과 자신 빼고는 약수가 없는 수=소수를 사용하는 것이 좋음

곱셈법(Multiplication Method) 나눗셈법과 비슷하게 모듈러 연산을 활용하지만 소수는 활용하지 X

01) 키에 황금비를 곱함

02) 01 단계에서 구한 값의 모듈러 1을 취함 → 정수 부분은 버리고 소수 부분만 취함(0.xxx 형태의 값)

03) 02 단계에서 구한 값을 가지고 실제 해시 테이블에 맵핑 → 테이블 크기가 m이면 위에서 구한 수에 m을 곱한 후 정수 부분을 취하는 연산을 통해 해시 테이블에 매핑 가능 ⇒ 0.xxx * m → 테이블의 인덱스인 0 ~ (m - 1)에 매치 가능

문자열 해싱 키의 자료형이 문자열일 때 사용할 수 있는 해시 함수 문자열의 문자를 숫자로 변환하고 이 숫자들을 다항식의 값으로 변환해서 해싱

문자열 해싱을 위한 polynomial rolling method 01) 알파벳 a ~ z까지 숫자와 매치한 표와 키

02) “a”는 매치 표를 보면 1 ⇒ $s[0] * p^0$ = 1 * 1 = 1

03) 두 번째 문자열 “p”에 대해 연산 진행. “p” = 16 → $16 * p^1$ = 496

04) 이렇게 곱한 값들을 더하면 최종값 = 4,990,970. 이를 해시 테이블의 크기 m으로 모듈러 연산해 활용

문자열 해시 함수 수정하기

덧셈을 전부 한 다음 모듈러 연산을 하는 수식 대신, 중간 중간 모듈러 연산을 해 더한 값을 모듈러 연산하면 오버플로를 최대한 방지할 수 있음

3) 충돌 처리

충돌(Collision) : 서로 다른 키에 대해서 해시 함수의 결과 값이 같을 경우

체이닝으로 처리하기 해시 테이블에 데이터를 저장할 때 해싱한 값이 같은 경우 충돌을 해결하는 간단한 방법

충돌 발생 시 해당 버킷에 링크드리스트로 같은 해시 값을 가지는 데이터를 연결 → 같은 위치를 가리키므로 데이터를 저장할 때 충돌 발생

$\therefore$ 링크드리스트로 충돌한 데이터를 연결하는 방식으로 충돌을 해결

체이닝 장점

1) 충돌을 링크드리스트로 간단히 해결

체이닝 단점

1) 해시 테이블 공간 활용성이 떨어짐 충돌이 많아지면 그만큼 링크드리스트의 길이가 길어짐, 다른 해시 테이블의 공간은 덜 사용하므로 공간 활용성 ↓

2) 검색 성능이 떨어짐 충돌이 많으면 링크드리스트 자체의 한계 때문에 검색 성능이 떨어짐 → 링크드리스트로 연결한 값을 찾으려면 링크드리스트의 맨 앞 데이터부터 검색해야 하기 때문

개방 주소법으로 처리하기 개방 주소법(Open Addressing) : 체이닝에서 링크드리스트로 충돌 값을 연결한 것과 다르게 빈 버킷을 찾아 충돌 값을 삽입

→ 해시 테이블을 최대한 활용하므로 체이닝보다 메모리를 효율적으로 사용

선형 탐사(Linear Probing) 방식 충돌 발생 시 다른 빈 버킷을 찾을 때까지 일정한 간격으로 이동 ⇒ 선형 탐사 시 테이블의 범위를 넘으면 안 되므로 모듈러 연산 적용

단점 : 충돌 발생 시 1칸씩 이동하며 해시 테이블 빈 곳에 값을 넣으면 해시 충돌이 발생한 값끼리 모이는 영역이 생김 → 클러스터(Cluster)를 형성, 이런 군집이 생기면 해시 값은 겹칠 확률 ↑

이중 해싱 방식 해시 함수를 2개 사용하는 방식, 때에 따라 해시 함수를 N개로 늘리기도 함

두 번째 해시 함수의 역할 은 첫 번째 해시 함수로 충돌 발생 시 해당 위치를 기준으로 어떻게 위치를 정할지 결정하는 역할

4) 몸풀기 문제

문제 18) 두 개의 수로 특정 값 만들기

n개의 양의 정수로 이루어진 리스트 arr와 정수 target이 주어졌을 때 이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True, 없으면 False를 반환하는 함수 작성

def count_sort(arr, k):
  hashtable = [0] * (k + 1)

  for num in arr:
    if num <= k:
      hashtable[num] = 1
  return hashtable

def solution(arr, target):
  hashtable = count_sort(arr, target)

  for num in arr:
    complement = target - num
    if(
            complement != num
            and complement >= 0
            and complement <= target
            and hashtable[complement] == 1
        ):
      return True

  return False

문제 19) 문자열 해싱을 이용한 검색 함수 만들기

문자열 리스트 string_list와 쿼리 리스트 query_list가 있을 때 각 쿼리 리스트에 있는 문자열이 string_list의 문자열 리스트에 있는지 여부 확인. 문자열 있으면 True, 없으면 False. 각 문자열에 대해서 문자열의 존재 여부를 리스트 형태로 반환하는 함수 작성

def solution(string_list, query_list):
  lists = []
  res = []

  for i in range(len(string_list)):
    lists.append(string_list[i])

  for j in range(len(query_list)):
    if query_list[j] in lists:
      res.append(True)
    else:
      res.append(False)

  return res

5) 합격자가 되는 모의 테스트

문제 20) 완주하지 못한 선수

마라톤에 참여한 선수들의 이름이 담김 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 있을 때 완주하지 못한 선수의 이름을 반환하는 함수 작성

def solution(participant, completion):
    di = {}

    for p in participant:
        if p in di:
            di[p] += 1
        else:
            di[p] = 1

    for c in completion:
        di[c] -= 1

    for key in di.keys():
        if di[key] > 0:
            return key

문제 23) 베스트 앨범

노래의 장르를 나타내는 문자열 배열 genres와 노래 별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 반환하는 함수 완성

def solution(genres, plays):
    answer = []
    genre = {}
    play = {}
    play_sort = {}

    for i in range(len(genres)):
        if genres[i] not in genre:
            genre[genres[i]] = {}
            play[genres[i]] = 0

        genre[genres[i]][i] = plays[i]

        play[genres[i]] += plays[i]

    genre_sort = sorted(play.items(), key=lambda x: x[1], reverse=True)

    for j in range(len(genre_sort)):
        play_sort[genre_sort[j][0]] = sorted(genre[genre_sort[j][0]].items(), key=lambda item: item[1], reverse=True)[:2]

        answer.extend([idx for idx, _ in play_sort[genre_sort[j][0]]])

    return answer

06.스택

1) 스택 개념

스택(Stack) : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조 ⇒ 선입후출(FILO$\tiny\bf{First In Last Out}$)

• 푸시(Push) : 스택에 삽입하는 연산
• 팝(Pop) : 스택에서 꺼내는 연산
  

2) 스택의 정의

ADT : 추상 자료형(Abstract Data Type), 인터페이스만 있고 실제로 구현은 되지 않은 자료형, 일종의 설계도

스택의 ADT

연산 정의

(1) push() : 스택에 삽입

(2) pop() : 스택에서 삭제

(3) isFull() : 스택이 가득 찼는지 확인

(4) isEmpty() : 스택이 비었는지 확인

(5) top : 최근에 삽입한 데이터의 위치 저장할 변수

if top = 0, 데이터가 1개 있는 것

스택 세부 동작에 대해 조금 더 자세히 알아보기

push(3) 호출 시 내부적으로

(1) isFull() 수행해 우선 data 배열에 데이터가 가득 찼는지 확인

(2) 아니면 top 1만큼 증가

(3) top이 가리키는 위치에 data[0]에 3 추가

pop() 함수 수행 시 내부적으로

(1) isEmpty() 함수를 우선 수행해 data 배열에 데이터가 없는 건 아닌지 확인

(2) 있다면 top 1만큼 감소

(3) 데이터 ‘3’ 반환

→ top이 가리키는 위치는 -1이므로, 실제 data 배열에 데이터가 남아 있더라도 스택은 비어 있다고 봐도 됨

스택 구현하기

스택 ADT 구현

stack = [] # 스택 리스트 초기화

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼냄
top_element = stack.pop()
next_element = stack.pop()

# 스택의 크기를 구함
stack_size = len(stack)

# top_element : 3
# next_element : 2

3) 몸풀기 문제

문제 08) 괄호 짝 맞추기

열린 괄호나 닫힌 괄호가 마구 뒤섞인 문자열이 있을 때 소괄호가 정상적으로 열고 닫혔는지 판별하는 함수 구현 → 소괄호가 정상적으로 열고 닫혔다면 True, 아니면 False 반환

def solution(s):
  stack = []

  for i in s:
    if i == "(":
      stack.append(i)
    elif i == ")":
      if len(stack) == 0:
        return False
      else:
        stack.pop()

  if len(stack) == 0:
    return True
  else:
    return False

문제 09) 10 진수를 2 진수로 변환하기

10 진수를 입력 받아 2 진수로 변환하는 함수 구현

def solution(decimal):
  stack = []
  binary = ""

  while decimal > 0:
    stack.append(str(decimal % 2))
    decimal //= 2

  while stack:
    binary += stack.pop()

  return binary

4) 합격자가 되는 모의 테스트

문제 10) 괄호 회전하기

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어짐, 이 s를 왼쪽으로 x칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 반환하는 함수 완성

def solution(s):
  x = 0
  s_len = len(s)

  for i in range(s_len):
    stack = []
    for j in range(s_len):
      c = s[(i + j) % s_len]

      if c == "{" or c == "[" or c == "(":
        stack.append(c)
      else:
        if not stack:
          break

      if c == ")" and stack[-1] == "(":
        stack.pop()
      elif c == "]" and stack[-1] == "[":
        stack.pop()
      elif c == "}" and stack[-1] == "{":
        stack.pop()
      else:
        break

    else:
      if not stack:
        x += 1

  return x

문제 11) 짝지어 제거하기

알파벳 소문자로 구성된 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾아 그 둘을 제거한 뒤 앞뒤로 문자열을 이어 붙임, 이 과정을 반복해서 문자열을 모두 제거하면 종료, 문자열 s가 주어 졌을 때 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수 완성

def solution(s):
    answer = 0
    stack = []
    length = len(s)

    for i in range(length):
        if stack and s[i] == stack[-1]:
            stack.pop()
        else:
            stack.append(s[i])

    if stack:
        answer = 0
    else:
        answer = 1

    return answer

07. 큐

1) 큐의 개념

큐(Queue) : 먼저 들어간 데이터가 먼저 나오는 자료구조 ⇒ 선입선출(FIFO$\tiny\bf{First In First Out}$)

• 푸시 : 큐에 삽입하는 연산
• 팝: 큐에서 꺼내는 연산
  

큐의 특성을 활용하는 분야

대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐 활용

• 작업 대기열 : 네트워크 통신을 할 때, 다수의 클라이언트에서 서버에 작업 요청 시 서버는 요청이 들어온 순서대로 작업 처리
• 이벤트 처리 : 어떤 application이나 system에서 사용자의 이벤트(키보드 입력, 마우스 움직임)를 처리할 때 활용 가능
  

큐의 ADT

• 데이터를 넣지 않은 상태 → front = -1, rear = -1 ⇒ 배열의 인덱스가 0부터 시작하므로 아무것도 넣지 않은 상황 표현을 위해 초깃값을 -1로 지정
  

큐의 세부 동작에 대해 조금 더 자세히 알아보기

01 단계> push()

(1) isFull() 연산으로 현재 큐가 가득 찼는지 확인

(2) 아니라면 rear += 1 ⇒ front = -1, rear = 0

(3) rear가 가리키는 위치에 3 push

02 단계> pop()

(1) isEmpty() 연산으로 큐가 비었는지 확인

(2) 비어있지 않다면 front += 1 ⇒ front = 0, rear = 0

(3) isEmpty() 연산 시 큐가 빈 것으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리 가능

03 단계> push()

(1) 5를 push하면 isFull() 연산을 수행해 큐가 가득 찼는지 검사, 아니라면 push

(2) 연거푸 6, 8를 push하면 front = 0, rear = 3

04 단계> isFull()일 때 push()

(1) rear가 3이므로 maxmize - 1과 같음

(2) isFull() 연산은 True이므로 push X

$\therefore$ 큐는 front의 다음부터 rear까지를 큐가 관리하는 데이터라고 생각해야 함

큐 구현하기

큐를 간단하게 구현하는 방식

(1) 리스트를 큐처럼 활용하기

queue = []

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거
first_item = queue.pop(0)
print(first_item) # 1

# 큐에 데이터 추가
queue.append(4)
queue.append(5)

# 큐의 맨 앞 데이터 제거
first_item = queue.pop(0)
print(first_item) # 2

(2) 덱(Double Ended Queue)을 큐처럼 활용하기

양 끝에서 삽입이나 삭제를 할 수 있다는 특징 때문에 큐를 구현할 때는 덱을 사용하는 것이 좋음

from collections import deque

queue = deque()

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거
first_itme = queue.popleft()
print(first_item) # 1

# 큐에 데이터 추가
queue.append(4)
queue.append(5)

# 큐의 맨 앞 데이터 제거
first_item = queue.popleft()
print(first_itme) # 2

2) 몸풀기 문제

문제 15) 요세푸스 문제

N명의 사람이 원 형태로 서 있음. 각 사람은 1번부터 N번까지 번호표를 가짐. 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앰

- 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앰
- 없앤 사람을 기준으로 다시 K번째 사람을 없앰

from collections import deque

def solution(N, K):
  queue = deque(range(1, N + 1))

  while len(queue) > 1:
    for _ in range(K - 1):
      queue.append(queue.popleft())

      queue.popleft()

  return queue[0]

3) 합격자가 되는 모의 테스트

문제 16) 기능 개발

배포 순서대로 작업 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지 반환하는 함수 완성

import math

def solution(progresses, speeds):
    answer = []
    length = len(progresses)

    days_left = [math.ceil((100 - progresses[i]) / speeds[i]) for i in range(length)]

    count = 0
    max_day = days_left[0]

    for i in range(length):
        if days_left[i] <= max_day:
            count += 1
        else:
            answer.append(count)
            count = 1
            max_day = days_left[i]

    answer.append(count)
    return answer

05. 배열

1) 배열 개념

배열(Array) : 인덱스와 값을 일대일 대응해 관리하는 자료구조

임의 접근(Random Access) : 데이터에 한 번에 접근 가능해서 어디에 있는지 알면 빠르게 접근하는 방식

배열 선언

• 파이썬의 경우 배열 지원 X → 리스트 문법 지원

(1) 일반적인 방법

arr = [0, 0, 0, 0, 0, 0]
arr = [0] * 6

(2) 리스트 생성자를 사용하는 방법

arr = list(range(6)) #[0, 1, 2, 3, 4, 5]

(3) 리스트 컴프리헨션을 활용하는 방법

arr = [0 for _ in range(6)] #[0, 0, 0, 0, 0,0]

• 리스트 컴프리헨션(List Comprehension) 참고

: 기존 리스트를 기반해 새 리스트를 만들거나, 반복문, 조건문을 이용해 복잡한 리스트 생성하는 등 다양한 상황에서 사용할 수 있는 문법

배열과 차원

배열은 다차원 배열을 사용할 때도 있지만 컴퓨터 메모리의 구조는 1차원이므로 다차원 배열도 실제로는 1차원 공간에 저장. 즉, 배열은 차원과 무관하게 메모리에 연속 할당됨

리스트 컴프리헨션을 활용한 2차원 배열 선언

# 크기가 3 * 4인 리스트 선언
arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2]]

2) 배열의 효율성

배열 연산의 시간 복잡도

배열의 데이터에 접근하기 위한 시간 복잡도는 O(1)

배열에 데이터를 추가, 삭제 연산에 대한 시간 복잡도는 다름

(1) 맨 뒤에 삽입할 경우

데이터를 삽입해도 다른 데이터 위치에 영향 X

임의 접근이 가능하여 시간 복잡도는 O(1)

(2) 맨 앞에 삽입할 경우

기존 데이터를 뒤로 한칸씩 밀어야 하기 때문에 연산 필요

데이터 개수를 N개로 일반화하면 시간 복잡도는 O(N)

(3) 중간에 삽입할 경우

현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산 필요

밀어야 하는 데이터 개수가 N개라면 시간 복잡도는 O(N)

배열로 데이터를 저장하기 전에 항상 이런 비용을 생각해보는 것이 좋음

배열을 선택할 때 고려할 점

(1) 할당할 수 있는 메모리 크기를 확인

배열로 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당 실패↑

보통 정수형 1차원 배열 - 1000만 개, 2차원 배열 - 3000 * 3000 크기를 최대로 생각

(2) 중간에 데이터 삽입이 많은지 확인

배열은 선형 자료구조이기 때문에 중간이나 처음에 데이터를 빈번하게 삽입하면 시간 복잡도↑

3) 자주 활용하는 리스트 기법

리스트에 데이터 추가

(1) append() 메서드로 데이터 추가

맨 끝에 데이터 추가하려면 append() 사용

my_list.append(2)

(2) +연산자로 데이터 추가

+연산자로 리스트 맨 끝에 다른 리스트의 데이터 추가 가능

my_list = [1, 2, 3]
my_list = my_list + [4, 5]

(3) insert() 메서드로 데이터 삽입

insert() 사용하면 특정 위치에 데이터를 삽입 가능

eg) insert(데이터를 삽입할 위치, 삽입할 데이터)

my_list = [1, 2, 3, 4, 5,]
my_list.insert(2, 9999) # [1, 2, 9999, 3, 4, 5]

리스트에서 데이터 삭제

(1) pop() 메서드로 특정 위치의 데이터 팝

eg) pop(팝할 데이터의 인덱스)

삭제하고 삭제한 데이터의 값을 반환

my_list = [1, 2, 3, 4, 5]
poped_element = my_list.pop(2) # 3
print(my_list) # [1, 2, 4, 5]

(2) remove() 메서드로 특정 데이터 삭제

remove() 메서드는 특정 데이터 자체를 삭제하는 함수

→ 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제

my_list = [1, 2, 3, 2, 4, 5]
my_list.remove(2) # [1, 3, 2, 4, 5]

리스트 컴프리헨션으로 데이터에 특정 연산 적용

(1) 리스트에 제곱 연산 적용 예시

numbers = [1, 2, 3, 4, 5]
squares = [num**2 for num in numbers] # [1, 4, 9, 16, 25]

• 주목해야 할 점 : numbers 리스트의 값 변화 유무 → numbers의 값 자체는 변형되지 않음 → 리스트 컴프리헨션은 연산이 끝난 리스트를 반환, 연산 대상 리스트 변형 X
  

리스트 연관 메서드

len() : 리스트의 전체 데이터 개수 반환

index() : 특정 데이터가 처음 등장한 인덱스 반환, 없으면 -1 반환

sort() : 사용자가 정한 기준에 따라 리스트 데이터 정렬

count() : 특정 데이터 개수 반환

fruits = ["apple", "banana", "cherry", "apple", "orange", "banana", "kiwi"]
len(fruits) # 7
fruits.index("banana") # 1
fruits.sort() # ["apple", "apple", "banana", "banana", "cherry", "kiwi", "orange"]
fruits.count("apple") # 2

4) 몸풀기 문제

문제 01) 배열 정렬하기

정수 배열을 정렬해서 반환하는 함수 완성

def solution(arr):
    ary = arr.sort()
    return ary

문제 02) 배열 제어하기

정수 배열 하나 받음, 배열의 중복 값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 함수 구현

def solution(arr):
    for i in range(0, len(arr)):
        if(arr.count(i) > 1):
            arr.pop(i)

    arr.sort(reverse=True)
    return arr

5) 합격자가 되는 모의 테스트

문제 03) 두 개 뽑아서 더하기

정수 배열 numbers가 주어짐, numbers에서 서로 다른 인덱스에 있는 2개의 수를 뽑아 더해 만들 수 있는 모든 수를 배열에 오름차순으로 담아 반환하는 함수 완성

def solution(numbers):
  result = []

  for i in range(len(numbers)):
    for j in range(i+1, len(numbers)):
      if(i != j):
        result.append(numbers[i] + numbers[j])
        result = sorted(set(result))

  return result

문제 04) 모의고사

수포자의 1번 문제부터 마지막 문제까지 다음과 같이 찍는다

- 1번 수포자 찍는 방식 : 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, …
- 2번 수포자 찍는 방식 : 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, …
- 3번 수포자 찍는 방식 : 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, …

1번 문제부터 마지막 문제까지의 정답이 순서대로 저장된 배열 answers가 주어졌을 때 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 반환하도록 함수 작성

def solution(answers):
  result = []
  pattern = [
        [1, 2, 3, 4, 5],
        [2, 1, 2, 3, 2, 4, 2, 5],
        [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    ]
  count1 = count2 = count3 = 0

  for i in range(len(pattern)):
    for j in range(len(answers)):
      if(pattern[i][j] == answers[j]):
        if(i == 0):
          count1 += 1
        elif(i == 1):
          count2 += 1
        else:
          count3 += 1

  cnt = [count1, count2, count3]
  max_cnt = max(cnt)

  for i in range(len(cnt)):
    if max_cnt == cnt[i]:
      result.append(i + 1)

  return sorted(result)

문제 05) 행렬의 곱셈

2차원 행렬 arr1과 arr2를 입력 받아 arr1에 arr2를 곱한 결과를 반환하는 함수 완성

def solution(arr1, arr2):
  result = [[0 for j in range(len(arr2))] for i in range(len(arr1))]

  for i in range(len(arr1)):
    for j in range(len(arr1[i])):
      for k in range(len(arr2)):
        result[i][j] += arr1[i][k] * arr2[k][j]

  return result

문제 06) 실패율

실패율 정의 : 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어의 수

전체 스테이지 개수가 N, 게임을 이용하는 사용자가 현재 멈춰 있는 스테이지의 번호가 담긴 배열 stages가 주어질 때 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨 있는 배열 반환하는 함수 완성

def solution(N, stages):
  result = []
  res = {}
  challengers = len(stages)

  for i in range(1, N + 1):
    fails = stages.count(i)
    res[i] = fails / challengers
    challengers -= fails

  result = sorted(res, key=lambda x : res[x], reverse=True)

  return result

문제 07) 방문 길이

명령어가 매개변수 dirs로 주어질 때 게임 캐릭터가 처음 걸어본 길의 길이를 구해 반환하는 함수

def solution(dirs):
    answer = set()
    x = y = 5
    nx = ny = 0
    list_dirs = list(dirs)

    for i in range(len(list_dirs)):   
      if 0 < y < 10:
        if list_dirs[i] == "U":
          nx, ny = x, y + 1  
        elif list_dirs[i] == "D":
          nx, ny = x, y - 1

      if 0 < x < 10:
        if list_dirs[i] == "R":
          nx, ny = x + 1, y 
        elif list_dirs[i] == "L":
          nx, ny = x - 1, y

      answer.add((x, y, nx, ny))
      answer.add((nx, ny, x, y))
      x = nx
      y = ny

    return len(answer) // 2

도서 링크 코딩 테스트 합격자 되기 파이썬 편

목표

1. 습관 들이기 위한 매일 최소 1개의 코테 문제 풀기
2. 매일 1시간 정도 공부하기

00. 코딩 테스트를 준비하기 전에

타인의 풀이를 보면 사고를 넓힐 수 있다

작성된 코드를 보다보면 다양한 문제 풀이 접근 방식이나 코딩 스킬을 습득 가능

나만의 테스트 케이스를 추가하는 건 좋은 알고리즘을 생각할 때 도움이 된다

충분한 시간을 들여 문제 분석 후 구현 전에 예외 상황을 확인 가능하도록 나만의 테스트 케이스 만들어 보기

01. 코딩 테스트 효율적으로 준비하기

문제 분석 연습

코딩 테스트는 문제 풀이 능력을 확인하는 것이 핵심

• 문제를 쪼개서 분석
• 제약 사항 파악, 테스트 케이스 추가
• 입력 값 분석
• 핵심 키워드 파악
• 데이터 흐름, 구성 파악
  

의사 코드로 설계 연습

코드 설계 = 의사 코드(Pseudo Code) 작성

작성 이점

• 설계 아이디어에 집중 가능
• 수정 시간이 비교적 짧음

작성 방법

• 세부 구현이 아닌 동작 중심으로 작성
  • 세부 구현 고민 시 의사 코드는 설계가 아닌 구현이 목적이 됨
• 문제 해결 순서로 작성
  • 의사 코드 완성 시 이를 토대로 코드 구현하기 때문
  • 자신의 코드 분석 시에 상당히 유용
• 충분한 테스트
  

02. 프로그래머스 완벽 활용 가이드

프로그래머스 가이드이므로 생략

03. 알고리즘의 효율 분석

가장 효율적으로 해결하는 알고리즘, 알고리즘이 실행되는 제한 시간과 관련↑ 시간 복잡도를 보고 선정

시간 복잡도(Time Complextity)

입력 크기에 대한 연산 횟수의 상한을 의미, 낮을 수록 Good 빅오 표기법, 점근적 표기법은 상한선을 활용하는 방식

04. 코딩 테스트 필수 문법

기본 데이터 타입 : int, float, string 컬렉션 데이터 타입 : list, tuple, set, dictionary

Epsilon을 포함한 연산에 주의

파이썬은 부동소수형 데이터를 이진법으로 표현하기 때문 표현 과정에서 오차 발생

리스트(List)

순서가 있는 자료형으로 인덱싱과 슬라이싱 가능 Indexing : 인덱스를 활용해서 특정 위치의 원소에 접근 Slicing : 시퀀스 자료형의 범위를 지정해서 값들을 복사하여 가져오는 방식

람다식(Lambda Expression)

함수를 더 간단하게 표현하는 방법 익명 함수(Annoymous Function)을 만드는 데 사용

사용 방식

• 변수로 참조 가능
  • 변수에 람다식 할당, 람다식 실행이 필요한 경우 호출
• 인수로 람다식 넘기는 방법
  • 함수에 인수로 람다식 사용
    

코딩테스트 플랫폼

1. 프로그래머스
2. LeetCode
3. AtCoder