동빈북

16989 단어 코딩테스트나동빈파이썬코테이것이 코딩테스트다나동빈

🦚 복잡도

시간복잡도: 알고리즘이 얼마나 오래 걸리는가
공간복잡도: 알고리즘이 얼마나 많은 메모리를 차지하는가

연산 횟수 10억 -> 대략 1초

제한 시간이 1초일때
N의 범위가 500 -> O(N^3)
N의 범위가 2,000 -> O(N^2)
N의 범위가 100,000 -> O(NlogN)
N의 범위가 10,000,000 -> O(N)

공간 복잡도의 경우 리스트를 사용한다면 크게 걱정할 필요는 없다.

🦞 그리디

그리디는 탐욕적 문제 해결 방식이다.
기준에 따라 좋은 것을 선택하는 알고리즘이므로
문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시하는 경우가 많다.

ex1. 거스름돈

n = int(input())
dic = {
  '500': 0,
  '100': 0,
  '50': 0,
  '10': 0,
}

while(n >= 10):
  if (n >= 500):
    dic['500'] += 1
    n -= 500
  elif (n >= 100):
    dic['100'] += 1
    n -= 100
  elif (n >= 50):
    dic['50'] += 1
    n -= 50
  else:
    dic['10'] += 1
    n -= 10

for i in dic.values():
  print(i)

위와 같은 방식은 금액의 크기에 영향을 받기 때문에 좋은 코드는 아니다.

n = int(input())
cnt = 0
coin_types = [500, 100, 50, 10]
for coin in coin_types:
	cnt += n // coin
    n %= coin
print(cnt)

시간 복잡도가 무조건 O(K)인 알고리즘이다.

ex2. 큰 수의 법칙

N, M, K = map(int, input().split())
res = 0

data = list(map(int, input().split()))
data.sort()
max1 = data[N - 1]
max2 = data[N - 2]

while M > 0:
  for i in range(0, K):
    if M > 0:
      M -= 1
      res += max1
  if M > 0:
    res += max2
    M -= 1

print(res)

ex3. 숫자 카드 게임

col, row = map(int, input().split())
datas = []
for i in range(col):
  data = list(map(int, input().split()))
  data.sort()
  datas.append(data)

max = 0
for i in range(col):
  if max < datas[i][0]:
    max = datas[i][0]
print(max)

//min()과 max()함수를 사용한 예
col, row = map(int, input().split())
res = 0
for i in range(col):
	data = list(map(int, input().split()))
    min_val = 10001
    for a in data:
    	min_val = min(min_val, a)
    res = max(res, min_val)
print(res)

ex4. 1이 될 때까지

n, k = map(int, input().split())
cnt = 0
while n != 1:
  if (n % k == 0):
    n /= k
  else:
    n -= 1
  cnt += 1
print(cnt)

실전1. 왕실의 나이트

dx = [1, 2, 2, 1, -1, -2, -2, -1]
dy = [2, 1, -1, -2, -2, -1, 1, 2]

//dx와 dy를 합쳐서 표현하는 방법도 알아두자.
steps = [(-2,1), (-1,-2), ... ,(-2,1)]

pos = input()
x = ord(pos[0]) - 96
y = int(pos[1])

cnt = 0
for i in range(0, 8):
  if (x + dx[i] > 0 and x + dx[i] < 8):
    if (y + dy[i] > 0 and y + dy[i] < 8):
      cnt += 1
print(cnt)

실전2. 게임 개발

col, row = map(int, input().split())
x, y, direction = map(int, input().split())
maps = []
step = []
d = [[0] * row for _ in range(col)]
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

for i in range(col):
  maps.append(list(map(int, input().split())))

def direction_set():
  global direction
  global step
  if direction == 0:
    step = [0, -1]
  elif direction == 1:
    step = [1, 0]
  elif direction == 2:
    step = [0, 1]
  elif direction == 3:
    step = [-1, 0]

cnt = 1
d[x][y] = 1
turn = 0

while(1):
  direction -= 1
  if (direction < 0):
    direction = 3

  direction_set()

  if not maps[x + step[0]][y + step[1]] and not d[x + step[0]][y + step[1]]:
    x += step[0]
    y += step[1]
    d[x][y] = 1
    cnt += 1
    turn = 0
  else:
    turn += 1
  if turn == 4:
    nx = x - step[0]
    ny = y - step[1]
    if maps[nx][ny] == 0:
      x = nx
      y = ny
    else:
      break
    turn = 0

print(cnt)

🐞 BFS, DFS

BFS는 무조건 최단 경로로 나오고, DFS는 그렇지 않을 수도 있다.

실전 3. 음료수 얼려 먹기

n, m = map(int, input().split())
datas = []
for _ in range(n):
  datas.append(list(map(int, input())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def dfs(x, y):

//처음에 이 예외처리를 안해서 틀림.
  if x < 0 or x > n-1 or y < 0 or y > m-1:
    return False
    
  if (datas[x][y]):
    return False
  else:
    datas[x][y] = 1
    for i in range(4):
      dfs(x + dx[i], y + dy[i])
    return True
  return False

cnt = 0
for i in range(n):
  for j in range(m):
    if dfs(i, j):
      cnt += 1

print(cnt)

실전 4. 미로 탈출

from collections import deque

n, m = map(int, input().split())
datas = []
for _ in range(n):
  datas.append(list(map(int, input())))

dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]

q = deque()
q.append((0, 0))

while q:
  x, y = q.popleft()
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    if (nx < 0 or nx > n - 1 or ny < 0 or ny > m - 1):
      continue
    if datas[nx][ny] == 1:
      q.append((nx, ny))
      datas[nx][ny] = datas[x][y] + 1

print(datas[n-1][m-1])

🦔 정렬

버블 정렬

가장 간단한 알고리즘이다.
시간 복잡도는 O(N^2) 이다.
느린 알고리즘이지만 코드가 간단하여 많이 사용된다.

선택 정렬

가장 작은 값과 가장 작은 인덱스에 있는 값을 swap하는 정렬이다.
대부분의 프로그래밍 언어에서는 임시변수를 선언하여 값을 바꿔야 하지만,
파이썬에서는 다음과 같은 방법으로 swap이 가능하다.

arr[0], arr[1] = arr[1], arr[0]

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

삽입 정렬

첫 번째 데이터는 그대로 두고(이미 정렬되어있다고 생각한다),
두 번째 데이터를 첫 번째 데이터의 왼쪽에 둘지 오른쪽에 둘지 판단한다.
세 번째 데이터부터는 이전 데이터와 비교하여 자신의 자리를 찾아간다.
시간 복잡도는 마찬가지로 O(N^2) 이다.

퀵 정렬

퀵 정렬의 대표적인 분할 방식은 호어 분할 방식이다.
호어 분할 방식에서는 리스트 첫 번째 데이터를 피벗으로 정한다.
그 다음 왼쪽에서부터 피벗보다 큰 데이터를 찾고,
오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
이후 그 둘을 swap한다.
위치가 엇갈릴 경우에는, 작은 데이터와 피벗의 위치를 바꾼다.
그 이후에는 재귀적으로 앞의 방법을 반복한다.
시간 복잡도는 O(NlogN)이다. (증명은 복잡하다)

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있다.
최악의 경우에도 수행 시간 O(N+K)를 보장한다.
(데이터의 개수=N, 데이터 중 최댓값=K)
가장 작은 데이터와 가장 큰 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다.

병합 정렬

병합 정렬은 파이썬의 정렬 라이브러리(sorted)로도 쓰인다.
최악의 경우에도 O(NlogN)의 시간복잡도를 보장한다.

실전 2. 위에서 아래로

//reverse, end라는 key를 잘 기억해두자.
n = int(input())
arr = []
for _ in range(n):
  arr.append(int(input()))
arr.sort(reverse=True)
for e in arr:
  print(e, end=' ')

실전 3. 성적이 낮은 순서로 학생 출력하기

//lambda의 활용을 기억하자.
n = int(input())
arr = []
for _ in range(n):
  a = input().split()
  arr.append((a[0], int(a[1])))
arr.sort(key=lambda e: e[1])
for e in arr:
  print(e[0], end=' ')

실전 4. 두 배열의 원소 교체

n, k = map(int, input().split())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
arr1.sort()
arr2.sort(reverse=True)
for i in range(k):
  if (arr1[i] < arr2[i]):
    arr1[i], arr2[i] = arr2[i], arr1[i]
print(sum(arr1))

🐝 이진 탐색

순차 탐색

앞에서부터 차례대로 확인하는 방법이다.
O(N)의 시간 복잡도를 가진다.

이진 탐색

O(logN)의 시간 복잡도를 가진다.
탐색 범위가 2000만을 넘어가면 이진 탐색을 사용해야 한다.

실전 2. 부품 찾기

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

arr.sort()
for e in sarr:
  start = 0
  end = n
  for _ in range(n):
    mid = (start + end) // 2
    if e == arr[mid]:
      print("yes")
      break
    elif e < arr[mid]:
     end = mid
    elif e > arr[mid]:
      start = mid
  else:
    print("no")

실전 3. 떡볶이 떡 자르기

n, m = map(int, input().split())
arr = list(map(int, input().split()))
h = max(arr) - 1
while(h > 0):
  arr_sliced = []
  for i in range(n):
    if arr[i] > h:
      arr_sliced.append(h)
    else:
      arr_sliced.append(arr[i])
  res = [arr[i] - arr_sliced[i] for i in range(n)]
  if (sum(res) >= m):
    print(h)
    break
  else:
    h -= 1

이진 탐색으로 문제를 해결하지 않았기 때문에 시간 초과가 뜰 가능성이 높다.
이 문제는 파라메트릭 서치 유형의 문제이다.
이 기법은 '조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 이용된다.

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

start = 0
end = max(arr)

res = 0
while(start <= end):
  total = 0
  mid = (start + end) // 2
  for x in arr:
    if x > mid:
      total += x - mid
  if total < m:
    end = mid - 1
  else:
    res = mid
    start = mid + 1
print(res)

재귀적으로 문제를 풀면 최악의 경우에도 시간초과가 나지 않는다.

🐋 다이나믹 프로그래밍

다이나믹 프로그래밍으로 해결할 수 있는 대표적 예시는 피보나치 수열이다.
피보나치 수열을 재귀 함수를 이용해 만들 수 있다.
하지만 그렇게 하면 시간복잡도가 O(N^2)가 되어, 문제를 풀 때 시간초과가 뜰 가능성이 높다.
이런 문제는 다이나믹 프로그래밍을 사용하면 쉽다.
다이나믹 프로그래밍은 다음과 같은 조건을 만족할 때 사용가능하다.

  1. 큰 문제를 작은 문제로 나눌 수 있다.
  2. 작은 문제에서 구한 정답은 큰 문제에서도 동일하다.

피보나치 수열은 이 조건을 만족한다.
메모이제이션 기법(값을 리스트에 저장하는 방법)을 이용해서 피보나치 수열을 구현해보자.

d = [0] * 100
def fibo(x):
  if x == 1 or x == 2:
      return 1
  if d[x] != 0:
      return d[x]
  d[x] = fibo(x-1) + fibo(x-2)
  return d[x]
print(fibo(99))

이런 방식으로 구현하면 시간복잡도가 O(N)이다.

재귀 함수를 이용한 다이나믹 프로그래밍을 Top-down 방식이라고 한다.(하향식)
단순히 반복문을 이용하여 코드를 작성하면 Bottom-up 방식이다.(상향식)
메모이제이션은 탑다운 방식에 국한되어 사용되는 표현이다.

Top-down 방식은 점화식을 이해하기 쉽다는 장점이 있고,
Bottom-up 방식은 재귀함수를 이용하지 않기 때문에 시간과 메모리 사용량을 줄일 수 있다는 장점이 있다.

문제를 풀 때, 주어진 문제가 완전탐색으로 풀면 시간 초과가 뜰 것 같을 때 다이나믹 프로그래밍으로 접근해보는 습관을 가지자.

실전 2. 1로 만들기

x = int(input())
cnt = 0
n = 1
while (n < x):
  if (n * 5 <= x):
    n *= 5
  elif (n * 3 <= x):
    n *= 3
  elif (n * 2 <= x):
    n *= 2
  else:
    n += 1
  cnt += 1
print(cnt)

1에서부터 거꾸로 수를 곱하거나 더하는 방식을 사용했는데, 틀린 답이 나왔다.
27을 만들기 위해서는 3을 3번 곱하는 것이 더 좋다.
하지만 나의 알고리즘은 5를 2번 곱하고 2를 2번 더한다. -> 총 4번이 된다.
정답:

x = int(input())
d = [0] * 30001
for i in range(2, x+1):
  d[i] = d[i-1] + 1
  if i % 2 == 0:
    d[i] = min(d[i], d[i // 2] + 1)
  if i % 3 == 0:
    d[i] = min(d[i], d[i // 3] + 1)
  if i % 5 == 0:
    d[i] = min(d[i], d[i // 5] + 1)

print(d[x])

실전 3. 개미 전사

n = int(input())
arr = list(map(int, input().split()))
d = [0] * 100
d[0] = arr[0]
d[1] = max(arr[0], arr[1])
for i in range(2, n):
  d[i] = max(d[i-1], d[i-2]+arr[i])
print(d[n-1])

풀이가 참신하다.. 점화식을 만들면 비교적 간단하게 풀이할 수 있다.
유형을 기억해두면 좋겠다.

실전 4. 바닥 공사

다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다.
점화식을 구하는 방법에 대한 동영상이다.
https://www.youtube.com/watch?v=YHZiWaL49HY

n = int(input())

d = [0] * 1001
d[1] = 1
d[2] = 3
for i in range(3, n+1):
  d[i] = (d[i-1] + 2 * d[i-2]) % 796796
print(d[n])

실전 5. 효율적인 화폐 구성

<문제 해결방법>
1. 초기화
10001개의 배열을 만든다.
배열을 INF로 초기화한다.
이 문제에서는 10001이 INF가 될 수 있다.

2. 제일 작은 화폐의 단위부터 배열에 값을 채우기 시작한다.
만약 화폐 단위가 2, 7이고 17을 만들려고 한다면
0, INF, 1, INF, 2, INF, 3, INF, 4, INF, 5, INF, 6, INF, 7, INF, 8, INF 일 것이다.
화폐단위 7도 해보면
0, INF, 1, INF, 2, INF, 3, 1, 4, INF, 5, INF, 6, INF, 2, INF, 8, INF 일 것이다.
이렇게 되면 9(2+7), 13(2+2+7)과 같은 수들을 놓치게 된다.

3. 다음과 같은 코드를 추가한다.

if arr[j - coin] != INF:
	arr[j] = arr[j - coin] + 1

화폐단위가 7이고 arr 인덱스가 9라면, arr[2] = 1이므로 arr[9] = 2가 된다.
마찬가지로 arr[13] = 3이 된다.
전체 코드는 다음과 같다.

INF = 10001
n, m = map(int, input().split())
arr = [10001] * INF
arr[0] = 0
coins = []

for i in range(n):
  coin = int(input())
  coins.append(coin)
  arr[coin] = 1

for coin in coins:
  for j in range(min(coins), m + 1):
    if j % coin == 0:
      arr[j] = arr[j - coin] + 1
    elif arr[j - coin] != INF:
      arr[j] = arr[j - coin] + 1
      
if arr[m] != 10001: 
  print(arr[m])
else:
  print(-1)

최단 경로

최단 경로 알고리즘은 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다.
다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘으로 대부분의 코딩 테스트 문제를 푼다.

다익스트라 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다.
원리는 다음과 같다.

  1. 출발 노드 설정
  2. 최단거리 테이블 초기화
  3. 미방문 노드 중 최단거리가 제일 짧은 노드 선택
  4. 해당 노드를 거치고, 다른 노드로 가는 비용을 계산하여 최단거리 테이블 초기화
  5. 3~4 반복

다익스트라는 쉬운 방법, 어려운 방법 두 가지의 구현 방법이 있다.
쉬운 방법은 느리게 동작하기 때문에 되도록이면 어려운 방법으로 연습하는 게 좋다.
쉬운 방법(O(N^2))으로 한다면, 전체 노드의 개수가 5,000개 이하일 때 시간초과가 나지 않는다.

개선된 다익스트라 알고리즘에서는 힙 자료구조를 사용한다.
정확하게는 최소 힙이다. 비용이 적은 노드를 우선하여 방문하기 때문이다.

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
grp = [[] for i in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
  a, b, c = map(int, input().split())
  grp[a].append((b,c))

def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start)) 
  distance[start] = 0
  while q:
    dist, node = heapq.heappop(q)
    if distance[node] < dist:
      continue
    for i in grp[node]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n+1):
  if distance[i] == INF:
    print("INFINITY")
  else:
    print(distance[i])

6 11
1
1 2 2
1 3 5
1 4 1
2 3 3
2 4 2
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

> 0
> 2
> 3
> 1
> 2
> 4

플로이드 워셜 알고리즘

다익스트라 알고리즘은 한 지점에서 다른 지점까지의 최단 경로를 구하는 알고리즘이다.
플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 구할 때 사용한다.
노드의 개수가 N개일 때 시간 복잡도는 O(N^3)이다.
N번의 단계에서(O(N)) 매번 2차원 리스트를 처리해야 하므로 O(N^2)의 시간이 소요되기 때문이다.

다익스트라 알고리즘은 그리디 알고리즘인데 비해 플로이드 워셜 알고리즘은 다이나믹 프로그래밍이다.

INF = int(1e9)

n = int(input())
m = int(input())
grp = [[INF]*(n+1) for _ in range(n+1)]

for i in range(1, n+1):
  for j in range(1, n+1):
    if i == j:
      grp[i][j] = 0

for _ in range(m):
  a, b, c = map(int, input().split())
  grp[a][b] = c

for k in range(1, n+1):
  for a in range(1, n+1):
    for b in range(1, n+1):
      grp[a][b] = min(grp[a][b], grp[a][k] + grp[k][b])

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

4
7
1 2 4
1 4 6
2 1 3
2 3 7
3 1 5
3 4 4
4 3 2

> 0 4 8 6 
> 3 0 7 9 
> 5 9 0 4 
> 7 11 2 0

실전 2. 미래 도시

INF = int(1e9)
n, m = map(int, input().split())
grp = [[INF] * (n+1) for _ in range(n+1)]

for a in range(1, n+1):
  for b in range(1, n+1):
    if a == b:
      grp[a][b] = 0

for _ in range(m):
  node1, node2 = map(int, input().split())
  grp[node1][node2] = 1
  grp[node2][node1] = 1

node_goal, node_check = map(int, input().split())

for k in range(1, n+1):
  for a in range(1, n+1):
    for b in range(1, n+1):
      grp[a][b] = min(grp[a][b], grp[a][k] + grp[k][b])

dist = grp[1][node_check] + grp[k][node_goal]

if dist >= INF:
  print("-1")
else:
  print(dist)

실전 3. 전보

import heapq
INF = int(1e9)
node_num, edge_num, start = map(int, input().split())
grp = [[] for _ in range(node_num+1)]
distance = [INF] * (node_num+1)

for _ in range(edge_num):
  start, end, cost = map(int, input().split())
  grp[start].append((end, cost))

def dijkstra(start):
  q = []
  heapq.heappush(q, (start, 0))
  distance[start] = 0
  while q:
    end, dist = heapq.heappop(q)
    if distance[end] < dist:
      continue
    for i in grp[end]:
       cost = dist + i[1]
       if cost < distance[i[0]]:
         distance[i[0]] = cost
         heapq.heappush(q, (i[0], cost))

dijkstra(start)

cnt = 0
total_time = 0
for i in distance:
  if i != INF:
    cnt += 1
    if total_time < i:
      total_time = i

print(cnt - 1, total_time)

알고리즘 팁

각 문제에 적합한 알고리즘을 잘 골라 사용해야 한다.

<문제의 종류>
1. 하나의 정점 -> 다른 하나의 정점
2. 하나의 정점 -> 다른 모든 정점
3. 각 모든 정점 -> 다른 모든 정점
4. 한 중간 정점을 거쳐서 가는 최단경로

2번에서,
가중치가 모두 같음 -> BFS
가중치가 다름 -> 다익스트라

음수 가중치의 간선이 존재할 때: 벨만-포드
하나의 정점에서 다른 모든 정점까지 최단경로를 구하는 문제: 플로이드 와샬

🐢 팁

빠르게 입력받기

import sys
input_data = sys.stdin.readline().rstrip()

문자열 데이터를 입력받는 방법이다.
공백 문자를 제거하려면 rstrip()이 필요하다.

[DB] SQLP 실기 - 5
[Kotlin_Android] AlertDialog와 NumberPicker로 시간설정창 만들기

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage