[Algorithm] 코딩테스트를 위한 기본 알고리즘 정리

구현/시뮬레이션

특징

• 알고리즘 문제의 80%는 구현이다. 문제 풀 때, 대부분 구현 문제라고 접근해도 무방하다.

접근방법

• 모든 경우의 수를 따져야 함.
  • 주어진 범위 내에 모든 수를 탐색해보면서 조건에 맞으면 탐색한다.
• 예시 1) 2503번: 숫자 야구
  • 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.
    • 주어진 범위 → 세자리수
    • 스트라이크&볼 → 조건
    • 순회 → 모든 수 탐색
      • 민혁: 123 영수: 1 스트라이크 1 볼.
      • 민혁: 356 영수: 1 스트라이크 0 볼.
      • 민혁: 327 영수: 2 스트라이크 0 볼.
      • 민혁: 489 영수: 0 스트라이크 1 볼.
    • 이때 가능한 답은 324와 328, 이렇게 두 가지이다. 

import sys
from itertools import permutations

# 입력한 결과에 맞는 가능한 숫자 조합 찾기 
def get_results(guess, results):
  can = []
  # 가능한 모든 순열에 대해서
  for p in permutations('123456789', 3):
    # 스트라이크 개수 계산
    strike = sum(p[i] == guess[i] for i in range(3))
    # 볼 개수 계산
    ball = sum(guess[i] in p for i in range(3)) - strike
    # 결과가 맞는 경우 가능한 조합 리스트에 추가
    if results == (strike, ball):
      can += [p]
  return can

# 모든 입력 결과에 대해 가능한 조합 리스트를 구하고, 이전 입력 결과에서 가능한 조합과 겹치는 것만 result 리스트에 남김
result = []
for _ in range(int(input())):
    guess, strike, ball = map(int,sys.stdin.readline().split())
    can = get_results(str(guess), (strike, ball))
    # result 리스트가 비어있으면, 가능한 조합 리스트 전체를 result 리스트로 할당
    if result == []:
        result = can
    # result 리스트가 비어있지 않으면, 가능한 조합 리스트 중 이전에 구한 가능한 조합 리스트에도 포함된 것만 남김
    else:
        result = [c for c in can if c in result]

# 가능한 조합의 개수 출력
print(len(result))

• 예시 2) 상하좌우
  • 난이도가 낮으면, 아래 문제 유형과 같이 입력이 주어진다.
  • 여행가 A는 N x N 크기의 정사각형 공간에 위치. 가장 왼쪽 위 좌표는 (1, 1)
  • 여행가 A는 상, 하, 좌, 우 방향으로 이동 가능하면 시작 좌표는 (1, 1)
    • 한 줄에 띄어쓰기를 기준으로 L, R, U, D 중 하나의 문자가 반복적으로 적혀있음
    • 각 방향으로 한 칸 이동 (L: 왼쪽, R: 오른쪽, U: 위, D: 아래)
    • N x N 정사각형 공간을 벗어나는 움직임은 무시됨
  • 여행가 A가 이동할 계획서
    • 가장 오른쪽 아래 좌표는 (N, N)
    • 이 공간은 1 x 1 크기의 정사각형으로 구성되어있음

# 5
# R R R U D D

actions = ['L', 'R', 'U', 'D']
actions_move = [(-1, 0), (1, 0), (0, -1), (0, 1)]

start = (1, 1)
x, y = start

for step in steps:
    next_step = ()

    if step == 'L':
        next_step = actions_move[0]
    elif step == 'R':
        next_step = actions_move[1]
    elif step == 'U':
        next_step = actions_move[2]
    elif step == 'D':
        next_step = actions_move[3]

    next_x, next_y = next_step
    if (y + next_y) <= 0 or (x + next_x) <= 0 or (y + next_y) > n or (x + next_x) > n:
        continue
    x += next_x
    y += next_y

print(y, x)

• 난이도가 높아지면, 이동 조건이 추가된다. ex) 게임개발. 
  • 이러한 유형은 주어진 조건 하에 완전탐색 해야 한다. 

while True:
  # 일단 왼쪽 방향부터 확인 
  turn_left()
  next_x, next_y = action_moves[direction]
  nx = x + next_x
  ny = y + next_y

  # 방문하지 않았고 그곳이 육지이면
  if d[nx][ny] == 0 and game_map[nx][ny] == 0:
    # 방문처리 
    d[nx][ny] = 1
    # 실제 이동 처리 
    x = nx
    y = ny 
    count += 1
    # 턴 초기화 
    turn_time = 0
    continue
  else:
    turn_time += 1
  if turn_time == 4:
    nx = x - next_x
    ny = x - next_y
    if game_map[nx][ny] == 0:
      x = nx
      y = ny
    else:
      break
    turn_time = 0

 

완전탐색 (브루트포스)

특징

• 구현과 유사하지만, 모든 경우를 다 따져봐야 하는 경우이다. 구현과 완전탐색 유형을 구분하지 않기도 한다.

접근방법

• 답은 나오지만 효율성 문제가 생기는 경우 -> 누적합, DP, 그리디, 우선순위 큐, 투포인터, 이분 탐색 순으로 시도하자.
• 예시 1) 시각

hour = int(input())
second = 60
minute = 60

count = 0

for i in range(0, hour+1):
  for j in range(0, minute):
    for k in range(0, second):
      time = str(i) + str(j) + str(k)
      if '3' in time:
        count += 1

print(count)

 

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램

DP

특징

• 정말 정말 자주 등장한다.
• 그리디, 완전탐색, 이분탐색, DFS, BFS 등 함께 활용되는 케이스가 가장 많은 유형이다.
• 시간 제한이 타이트한 문제일 경우, 예를 들어 N이 10만 넘어갈 경우, N^2 시간 복잡도를 갖는 알고리즘은 절대 1-2초 안에 통과 못한다.
  • 거의 대부분 DP를 활용한다.
• 점화식만 잘 세우면 거의 해결된다.
  • 그게 어렵지만..
  • 대부분 프로그래밍 관점

접근방법

• 문제에서 구하라고 하는 값의 후보군을 배열에 담는다.
• 만약 조건이 여러 개인 경우에는 2차원 배열을 선언해야 한다.
  • 이게 좀 까다롭다..
• 예시 1) 구간 합 구하기 5 → 2차원 배열에 값을 담는 경우
  • (2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)
  • dp 테이블에 값을 갱신하지 않으면, 값을 그 때마다 추가로 계산해줘야 하므로 알고리즘 성능이 악화되게 된다.

  n, m = list(map(int, input().split()))
  dp = [[0] * (n+1) for _ in range(n+1)]
  numbers = []
  input_numbers = []
  
  for _ in range(n):
    numbers.append(list(map(int, input().split())))
  
  for _ in range(m):
    input_numbers.append(list(map(int, input().split())))
  
  # 누적합된 값
  for i in range(1, n+1):
    for j in range(1, n+1):
      dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + numbers[i-1][j-1]
  
  result = []
  
  for x, y, z, w in input_numbers:
    print(dp[z][w] - dp[x-1][w] - dp[z][y-1] + dp[x-1][y-1])

   
• 11660번: 구간 합 구하기 5
• N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 
• 예시 2) 금광 → 2차원 배열에 값을 담는 경우 

# 테스트 케이스(Test Case) 입력
for tc in range(int(input())):
  # 금광 정보 입력 (n : 세로길이, m : 가로길이)
  n, m = map(int, input().split())
  array = list(map(int, input().split()))
    
  # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화 (n x m)
  dp = []
  idx = 0
  for i in range(n):
    dp.append(array[idx:idx + m])
    idx += m
  
  # j가 0인 경우, 왼쪽 값을 계산할 수 없으므로 제외 
  for j in range(1, m):
    for i in range(n):
      # 1) 왼쪽 위
      if i == 0:
        left_up = 0 # 예외처리 1) : 왼쪽 최상단인 경우, 고려하지 않음
      else:
        left_up = dp[i-1][j-1]
      # 2) 왼쪽 아래 
      if i == n - 1:
        left_down = 0 # 예외처리 2) : 왼쪽 최하단인 경우, 고려하지 않음
      else:
        left_down = dp[i+1][j-1] 
      # 3) 왼쪽
      left = dp[i][j-1] # 왼쪽의 경우에는 따로 예외처리 하지 않음
      dp[i][j] = dp[i][j] + max(left_up, left_down, left)
  
  result = 0
  # dp 테이블의 가장 오른쪽의 값 중 최댓값을 결과값으로 담는다 
  for i in range(n):
    result = max(result, dp[i][m-1])
  
  print(result)

• n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다.이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다.
• 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.
• 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다.
• 예시 3) 편집거리

# 최소 편집 거리(Edit Distance) 계산을 위한 다이나믹 프로그래밍
def edit_dist(str1, str2):
  n = len(str1)
  m = len(str2)

  # 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
  dp = [[0] * (m + 1) for _ in range(n + 1)]

  # DP 테이블 초기 설정
  for i in range(1, n + 1):
    dp[i][0] = i
  for j in range(1, m + 1):
    dp[0][j] = j
  
  # 최소 편집 거리 계산
  for i in range(1, n + 1):
    for j in range(1, m + 1):
      # 문자가 같다면, 왼쪽 위에 해당하는 수를 그대로 대입
      if str1[i - 1] == str2[j - 1]:
        dp[i][j] = dp[i - 1][j - 1]
      # 문자가 다르다면, 세 가지 경우 중에서 최솟값 찾기
      else: # 삽입(왼쪽), 삭제(위쪽), 교체(왼쪽 위) 중에서 최소 비용을 찾아 대입
        dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

  return dp[n][m]

# 두 문자열을 입력 받기
str1 = input()
str2 = input()

# 최소 편집 거리 출력
print(edit_dist(str1, str2))

• 두 개의 문자열 A와 B가 주어졌을 때, 문자열 A를 편집하여 문자열 B로 만들고자 합니다.
  1. 삽입(Insert): 특정한 위치에 하나의 문자를 삽입합니다.
  2. 삭제(Remove): 특정한 위치에 있는 하나의 문자를 삭제합니다.
  3. 교체(Replace): 특정한 위치에 있는 하나의 문자를 다른 문자로 교체합니다.이때 편집 거리란 문자열 A를 편집하여 문자열 B로 만들기 위해 사용한 연산의 수를 의미합니다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하세요. 예를 들어 "sunday"와 "saturday"의 최소 편집 거리는 3입니다.
• 문자열 A를 편집할 때는 다음의 세 연산 중에서 한 번에 하나씩 선택하여 이용할 수 있습니다.

누적합

소개

• 누적합은 말 그대로 구간의 value를 누적합 형태로 구현하여 시간복잡도 측면에서 이득을 취하고자 하는 알고리즘이다. 일반적으로 사용되는 배열에 값을 저장하고 지정된 인덱스부터 하나씩 더해가는 방식은 최악의 경우 O(n^2)의 시간복잡도가 필요하기 때문에 입력 범위가 클 때 사용할 수 없다. 하지만 Prefix Sum방식의 누적합을 사용하면 입력과 동시에 누적합을 저장하고 필요한 구간의 값만 취하면 되기 때문에 O(n)으로 해결할 수 있다. 누적합은 문제에서 수열이 주어지고 어떤 구간의 합을 구해야할 때 쓰인다. 예를 들어 크기가 10인 배열에서 2번 index부터 8번 index 구간의 합을 구한다고 가정하면, 입력 후에 for문으로 다시 값을 구하는 것이 아닌 입력과 동시에 구간합을 저장하고 누적합은 psum[8] - psum[1]으로 표현할 수 있다.

접근방법

• 시간 제한에 걸릴 경우, DP, 그리디, 투포인터, 이분 탐색 등을 적용하여, 연산 횟수를 줄여야 한다.
  • 예시 2 → DP
• 예시 1) 11659번: 구간 합 구하기 4

for i in range(2, len(numbers)+1):
  psum[i] = psum[i-1] + numbers[i-1]

for value in input_values:
  start, end = value
  number_sum = 0
  
  if start == 1:
    result.append(psum[end])
  else:
    result.append(psum[end] - psum[start-1])

for element in range(len(result)):
  print(result[element])

• 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

그리디

특징

• 보통 쉬운 난이도의 문제는 정렬만 해도 쉽게 문제 해답에 대한 힌트를 얻을 수 있다.
• 어려운 난이도로 올라가면, 정렬 & 그리디 알고리즘 만으로 해결이 안된다.
  • 완전탐색의 접근 방법에서 언급했듯, 시간복잡도 제한이 까다로울 경우 우선순위 큐 등을 사용해야 할 수 있다.

접근방법

• 대표적인 유형
  • 예시 1) 14916번: 거스름돈
    • 단위가 큰 동전부터 거슬러주면 끝

n = int(input())
count = 0

while True:
  if n < 2:
    count = -1
    break
  
  if (n - 5) % 5 == 0 or (n - 5) % 2 == 0:
    n -= 5
  elif (n - 2) % 5 == 0 or (n - 2) % 2 == 0:
    n -= 2
  else:
    count = -1
    break

  count += 1  
  if n == 0:
    break

print(count)

• 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. ex) 13 -> 5
• 예시 2) 무지의 먹방 라이브
  • 한번만 정렬해도 되면 sort 함수를 사용하면 된다. 하지만 반복적으로 값을 넣었다 빼야 하는 경우에는 heap을 사용하는 것이 좋다. heappush된 원소를 heappop을 통해 자동으로 정렬된 상태로 반환되기 때문이다.

  def solution(food_times, k):
      # 총 음식 식사 시간보다 K가 크면 남은 음식이 없으므로
      if sum(food_times) <= k:
          return -1
  
      q = []  # 시간이 작은 음식부터 빼야 하므로 우선순위 큐(최소 힙)를 이용
      for i in range(len(food_times)):
          heapq.heappush(q, (food_times[i], i+1))  # (시간, 인덱스)
  
      sum_value = 0  # 먹기 위해 사용한 시간
      previous_eat_time = 0  # 직전에 다 먹은 음식 시간
      rest_food_count = len(food_times)  # 남은 음식 수
  
      # sum_value + (현재의 음식 시간 - 이전 음식 시간) * 현재 음식 개수와 K 비교
      while sum_value + ((q[0][0] - previous_eat_time) * rest_food_count) <= k:
          current_eat_time = heapq.heappop(q)[0]  # 현재 음식을 먹는데 걸리는 시간
          sum_value += (current_eat_time - previous_eat_time) * rest_food_count
          rest_food_count -= 1  # 다 먹은 음식 제외
          previous_eat_time = current_eat_time  # 이전 음식 시간 재설정
  
      result = sorted(q, key=lambda x: x[1])  # 인덱스 기준으로 정렬
      return result[(k-sum_value) % rest_food_count][1]  # 남은 음식 기준으로 나머지

• 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.
• 예시 3) 최단 경로 알고리즘(dijkstra) : 그리디 알고리즘과 다이나믹 프로그래밍이 그대로 적용된다.

# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
  min_value = INF
  index = 0
  for i in range(1, n+1):
    if min_value > distance[i] and not visited[i]:
      min_value = distance[i]
      index = i
  return index

def dijkstra(start):
  # 출발 노드에 관해서 초기화해줘야 한다. 
  distance[start] = 0
  visited[start] = True
  for dist, time in graph[start]:
    distance[dist] = time
  
  # 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복한다. 
  for i in range(n-1):
    # 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 
    now = get_smallest_node()
    visited[now] = True
    # 현재 노드와 연결된 노드를 확인 
    for j in graph[now]:
      # 최단거리까지 가는 거리 + 최단거리에서 다른 노드로 가는 비용
      cost = distance[now] + j[1]
      # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 기존 거리보다 짧은 경우 
      if cost < distance[j[0]]:
        distance[j[0]] = cost

투포인터

소개

• 리스트에 순차적으로 접근해야 할 때, 두 개의 점의 위치를 기록하면서 처리하는 알고리즘. 정렬되어 있는 두 리스트의 합집합에도 사용됨.
• 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다.
• 누적합 알고리즘과 자주 함께 사용된다.
  • 사용하지 않았을 때보다 성능 개선 → O(N) 만큼만 소요되도 처리되기 때문

접근방법

• 예제 1) 수들의 합 2
• 구체적인 설명 → https://butter-shower.tistory.com/226

n, m = list(map(int, input().split()))
numbers = list(map(int, input().split()))

left, right = 0, 1
count = 0

while left <= right and right <= n:
    total = sum(numbers[left:right])

    if total == m:
        count += 1
        right += 1
    elif total < m:
        right += 1
    else:
        left += 1

print(count)

• N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

이분탐색

특징

• 순차적인 배열 탐색으로는 시간 초과가 나는 문제에서 사용한다.
• 시간 복잡도 : O(logN)로 그냥 순회하는 O(N)보다 빠르다.
• 누적합 + DP 등 다른 유형과 연계되는 문제가 출제될 수 있다.

접근방법

• 예시 1) 이진탐색으로 값을 구하는 경우
  • 가장 일반적인 유형

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

def binary_search(array, target, start, end):
  if start > end:
    return None

  mid = (start + end) // 2
  
  if target == array[mid]:
    return mid
  # 타겟 값이 중간값보다 작을 때
  elif target < array[mid]:
    return binary_search(array, target, start, mid-1)
  # 타겟 값이 중간값보다 클 때
  else: 
    return binary_search(array, target, mid+1, end)

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)

• 예시 2) 다른 유형의 문제와 결합된 경우 - 누적합

def lower_bound(array, target):
    start, end = 0, len(array)

    while start < end:
        mid = (start + end) // 2
        if target <= array[mid]:
            end = mid
        else:
            start = mid + 1
    return start

for line in range(1, h+1):
    one = len(odd) - lower_bound(odd, line)
    two = len(even) - lower_bound(even, h - line + 1)
    obs_cnt[line] = one + two

print(min(obs_cnt), obs_cnt.count(min(obs_cnt)))

• 동굴의 크기와 높이, 모든 장애물의 크기가 주어진다. 이때, 개똥벌레가 파괴해야하는 장애물의 최솟값과 그러한 구간이 총 몇 개 있는지 구하는 프로그램을 작성하시오.
• 예시 3)
  • 문제가 복잡해질 경우, 이진탐색을 활용한 내장함수를 사용하는 편이 좋다.
    • bisect_left, bisect_right

from bisect import bisect_left, bisect_right

n_numbers, m_numbers = [], []
for i in range(n):
    for j in range(i+1, n+1):
        n_numbers.append(sum(n_number[i:j]))
for i in range(m):
    for j in range(i + 1, m + 1):
        m_numbers.append(sum(m_number[i:j]))

n_numbers.sort()
m_numbers.sort()

ans = 0
for i in range(len(n_numbers)):
    bmp = t - n_numbers[i]
    left = bisect.bisect_left(m_numbers, bmp)
    right = bisect.bisect_right(m_numbers, bmp)
    ans += (right - left)

print(ans)