[알고리즘] 시간복잡도, 코딩테스트 알고리즘 요약 정리

문제를 보면 입력 데이터의 개수를 보고 시간복잡도부터 계산하자 (코테의 가장 기본)

백준

프로그래머스

1초 = 1억번 연산 임을 인지하고 이를 토대로 시간복잡도를 계산하여, 시간초과가 나지 않을 적절한 알고리즘을 선택해야함

보통 프로그래머스의 경우 명시를 해두지 않았다면 제한 시간이 10초 라고 한다.

 

O(1): 입력 데이터의 개수와 상관없이 항상 상수의 시간을 가지는 알고리즘 (ex. 배열의 마지막 수 꺼내오기, 해시 테이블 삽입/삭제/검색)

O(logn): 크기가 커지면 커질수록 처리 시간이 절반으로 줄어드는 알고리즘 (ex. 이분탐색, 힙(우선순위 큐))

O(n): 입력 데이터의 개수만큼 시간이 소요되는 알고리즘 (ex. for문 1개, 배열/문자열 탐색, 배열/문자열 재정렬, set()으로 중복 제거)

O(nlogn): 입력 데이터의 개수에 비례하여 logn 만큼이 추가적으로 소요되는 알고리즘 (ex. 정렬)

O(n^2): 입력 데이터 개수의 제곱만큼 시간을 소요하는 알고리즘 (ex. 이중 반복문)

 

정리하면

시간 제한이 1-2초 라는 전제하에

입력 데이터가 1000개 이하 -> O(n^2) 이하인 알고리즘 (이중 반복문, 완탐으로 돌려도 무방)

입력 데이터가 10000개 -> O(n^2) 알고리즘 최대한 지양하여 미만인 알고리즘 선택 (완탐이 아닌 다른 알고리즘을 고민해봐야함)

입력 데이터가 100,000개 (10만) -> O(nlogn) 이하인 알고리즘 : 정렬, 이분탐색, 우선순위 큐 고민

입력 데이터가 1,000,000개 (100만) ->  O(nlogn) 미만인 알고리즘 : 이분탐색, 우선순위 큐 고민

 

✅ print문은 시간이 꽤 오래 걸리는 편에 속한다. 많은 양을 print 해야하는 경우 매번 print 하는 것이 아닌 다른 방법을 고민해야함

✅ 전반적으로 list/array 보다는 set, dictionary 연산속도가 빠름

✅ Swift 기준 시간복잡도가 포스팅된 블로그

https://demian-develop.tistory.com/30

iOS) Swift의 Time complexity에 관한 고찰

 

단순 구현,  시뮬레이션

- 요구사항을 꼼꼼히 다 읽고 메모할 것!!! 제발!!! (항상 이것때문에 틀림 ㅡㅡ)

- 시뮬레이션 : 다양한 문제를 접하면서 익숙해져야하는 유형

 

 1) 이동 방향에 따른 좌표 이동을 배열로 묶으면 편하다.

let dx = [0, 0, -1, 1] //이동 방향을 차례대로 x, y 따로 분리하여 배열로
let dy = [-1, 1, 0, 0]

// 3차원 배열일경우
let dx = [0, 0, -1, 1, 0, 0]
let dy = [0, 0, 0, 0, -1, 1]
let dz = [-1, 1, 0, 0, 0, 0]


var nx = x + dx[0] //nx, ny : x, y에서 현재 이동방향대로 이동한 값
var ny = y + dy[0]

//이동 시 -> x = nx, y = ny

2) 이동하는 좌표가 보드판의 범위를 벗어나지 않는지 매번 확인해야만 런타임 에러를 줄일 수 있다.

// 범위 안에 수가 포함되어있는지 판단하는 연산자
guard 1...n ~= nx && 1...n ~= ny else { continue }

 

완전 탐색 (Brute Force)

- 입력 크기가 매우 작은 편인지? (시간복잡도를 계산했을 때 시간초과가 나지 않을 만큼의 입력 크기인지)

- 시작 위치에서 다른 목표 위치까지 갈 수 있는 모든 방향을 체크하면서 모든 가능성을 따지는가?

- 탐색 범위를 잡아서 for문 혹은 while문의 조합

 

백트래킹 

https://devyul.tistory.com/189

[알고리즘] 백트래킹 유형 정리

- 모든 경우의 수를 탐색하되 중간에 조건에 맞지 않는 해가 있다면 더이상 탐색하지 않고 다른 가능성있는 경우의 수를 탐색함으로써 탐색 시간을 줄여주는 알고리즘

- 시간복잡도 보통은 O(2^n) -> 지수

- 완전탐색 + 수학적으로 조합/순열이 떠오를 때 / 조건에 맞게 탐색하기 위해 중간에 방향을 트는 경우가 있을 때 고려해볼만한 알고리즘

 

 ✅ 백트래킹 시간 줄이는방법

visited를 배열이 아닌 딕셔너리를 만들고, key가 원소 value가 원소의 개수인 것으로 초기화한 다음

방문할때마다 -1, 백트래킹, 다시 +1 로 돌리는 과정을 거치면 딕셔너리 특성으로 인해 더 빠르게 백트래킹을 실행할 수 있다.

def backtracking(n, current, goal):
  if n == goal:
    print(''.join(current))
    return

  for i in visited:
    if visited[i]:
      visited[i] -= 1
      backtracking(n+1, current+i, goal)
      visited[i] += 1

for str in arr:
  visited = {}

  # 각 문자열의 문자 개수를 딕셔너리 형태로 저장
  for s in str:
    if s in visited:
      visited[s] += 1
    else:
      visited[s] = 1
      
  backtracking(0, '', len(str))

 

✅ 백트래킹에서 return문을 써야할 때와 쓰지 말아야할 때

https://www.acmicpc.net/board/view/107433

글 읽기 - 고수님들 차이점 명확히 알고싶습니다.

만약 위 문제에서 [-1, 1, 0] 이라는 배열에서 합이 0인 부분수열의 개수를 구한다고 할 때 0도 같이 포함하여 카운팅 해야하지만, return을 시켜버리면 0까지 포함하지 않고 count 하게된다.

return은 말그대로 현재 상황에서 이전 상황으로 다시 돌아갈것인지, 돌아가지 않을 것인지를 판단하여 코드를 넣는것이기 때문에

현 상황에서 돌아가야 하는지,돌아가지 않아야 하는지를 판단해야한다.

 

✅ 외판원 순회 문제

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

 

✅ 그래프 탐색에서 외곽의 아무 빈 지점이나 들어갈 수 있다는 조건이 있는 경우, 맨 왼쪽과 맨 오른쪽에 빈 공간을 한줄씩 넣고 시작점을 (0,0) 으로 하게되면 탐색을 통해 외곽의 빈 입구를 찾아서 들어가게 된다.

관련문제 --> https://www.acmicpc.net/problem/9328

9328번: 열쇠

 

재귀

1) 점화식이 존재하는 문제는 재귀로 접근해볼 것

2) 처음 시작할때부터 목표 지점까지의 상태를 지정할 수 있고, 그 과정에서 매개변수를 활용한 로직을 짤 수 있다면 재귀로 설계해볼 것

3) 처음부터 목표까지 차례대로, 모든 경우의 수를 끝까지 채워나가면서 경우의 수를 따지는 케이스라면 반복문 안의 재귀 로직을 떠올릴 것

 

비트마스크

https://velog.io/@sun02/Swift-%EB%B9%84%ED%8A%B8%EC%97%B0%EC%82%B0

[Swift] Bitwise Operator(비트 연산자)

- 배열의 사이즈가 커서 원소가 존재하는지 확인하는 비용이 부담되거나, 특정 규칙을 만족하는 원소를 찾을 때

 

그래프 탐색(DFS/BFS) 

- 양쪽 다 연결되어있다면 입력받을 때 반드시 2개 노드 모두 연결되어있는 노드 리스트에 서로 추가해주어야함 (문제 잘읽기)

ex) 노드 1, 2가 서로 양방향으로 연결되어있다면 graph[1].append(2), graph[2].append(1) 이렇게 추가해주어야함

- 코딩테스트에서 탐색 문제를 만나면, 그래프 형태로 그림을 그려본 다음 풀이방법을 고민해보자.

- 문제지문이 반드시 그래프 형태여야만 하는게 아니고, 특정 지점에서 다른 지점까지 도달하는 과정이 있다면 DFS/BFS 고려 + 최소 시간이나 특수성 등 고려하여 둘중 하나 선택

 

📚 DFS (스택 사용) 

- 시간복잡도 O(V+E)

- 깊은 부분부터 탐색하는 방법

https://github.com/yurrrri/swift_algorim_practice/blob/main/%EA%B7%B8%EB%9E%98%ED%94%84%20%ED%83%90%EC%83%89/dfs.swift

GitHub - yurrrri/swift_algorim_practice: 스위프트 알고리즘 풀이 레포

 

📚 BFS (큐 사용)

- 시간복잡도 O(V+E)

- 가까운 노드부터 탐색하는 방법

https://github.com/yurrrri/swift_algorim_practice/blob/main/%EA%B7%B8%EB%9E%98%ED%94%84%20%ED%83%90%EC%83%89/bfs.swift

GitHub - yurrrri/swift_algorim_practice: 스위프트 알고리즘 풀이 레포

- 파이썬 : from collections import dequeue 를 통해 덱을 사용하여 큐 구현

https://github.com/ndb796/python-for-coding-test/blob/master/5/9.py

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

✅ DFS vs BFS?

1) 그래프의 모든 정점을 방문해야하는 문제
DFS, BFS 뭐든 상관없다. 편한걸 쓰면 된다.
다만 무관하다면 BFS가 더 속도가 빠르므로 BFS를 쓰자.

2) 경로의 특징을 저장하는 문제
예시로 각 정점에 숫자가 있고 a부터 b까지 경로를 구하는데 경로에 같은 숫자가 있으면 안된다는 문제. 각각의 경로마다 그 특징을 저장해두어야하는 문제는 DFS를 사용한다.

3) 최단거리, A와 B간의 거리 구하는 문제 ⭐
미로찾기등 최단거리를 구하는 경우 BFS가 좋다. DFS로 경로를 탐색하면 처음 발견하는 해답이 최단거리가 아닐수도 있지만 BFS는 현재노드에서 가까운 곳부터 찾기 때문에 경로를 탐색시 먼저 찾아지는 해답이 곧 최단거리다.

- 경로를 이동하면서, 그 전 경로의 수에 +1 을 한 다음, 탐색이 끝났을 때의 값이 곧 처음부터 해당 정점까지 가는 데 소요되는 최단 거리이다.

4) 검색 대상 그래프가 많이 클때 DFS

5) 검색대상의 규모가 별로 크지않고 검색시작지점으로부터 원하는 대상이 별로 멀지 않으면 BFS

 

✅ DFS/BFS 문제에서, 노드와 노드 간의 거리를 계산하는 경우에는 거리를 저장하는 배열을 따로 만들어서, 노드를 방문할 때마다 배열[노드] = 배열[이전 노드] + 1 하면 거리를 구할 수 있다. ⭐⭐

 

✅ BFS에서 큐 사용할 때 시간초과 줄이는법 (q의 인덱스 활용)

var q:[(Int, Int)] = []
var idx = 0

func bfs() {
  while idx < q.count{
    let (x, y) = q[idx]
    idx += 1
  }
  
  //이전
  /*
  while !q.isEmpty {
  	let (x, y) = q.removeFirst()
  }
  */
  
  //나머지는 기존 로직과 같음
}

 

✅ 그래프에서 특정 조건을 만족하는 구역을 정하는 문제

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

def dfs(x, y):	
	visited[x][y] = True  # 방문처리하기
	house_count += 1    # 방문할 때마다 각 집의 개수를 구함

	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		
		if 0<=nx<n and 0<=ny<n and not visited[nx][ny] and board[nx][ny] == 1:
			dfs(nx, ny)

answer = []
for i in range(n):
	for j in range(n):
		if board[i][j] == 1 and not visited[i][j]: # 구역을 짓기 시작하는 값인 1인데, visited가 false인 경우 아직 구역을 안지었다는 의미
			house_count = 0
			count += 1   # 구역의 개수 (구역을 짓기 시작할 때 개수 세기)
			dfs(i, j)
			answer.append(house_count)

 

✅ 트리의 지름

트리에서 임의의 정점 x를 잡아서 DFS/BFS로 탐색 --> 거리가 가장 먼 정점 y를 찾아서 --> y에서 DFS/BFS를 돌렸을 때 가장 먼 정점 z와의 거리가 곧 트리의 지름임을 활용한다.  관련 문제

def bfs(start, n):
  visited = [0] * n
  visited[start] = 1
  q = deque([start])
  maxValue = (0, 0) # 정점, 거리

  while q:
    node = q.popleft()

    for n, d in graph[node]:
      if not visited[n]:
        visited[n] = visited[node] + d
        q.append(n)
        if visited[n] > maxValue[1]:
          maxValue = (n, visited[n])

  return maxValue

node, dist = bfs(1, n+1)   # 가장 먼 노드를 찾아서
node, dist = bfs(node, n+1)  # 그 먼 노드에서 가장 길이가 먼 최대값을 찾음

print(dist-1)

 

✅ DFS를 활용하여 사이클을 이루는 집합/원소 구하기

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(node):
  global result
  
  cycle.append(node)
  visited[node] = True
  next = graph[node]

  if visited[next]: # 이미 방문한 노드이고
    if next in cycle: # 사이클에 있다면, 
      result += cycle[cycle.index(next):]
      return
  else:
    dfs(next)
  
n = int(input())
graph = [0]

for a in range(1, n+1):
  b = int(input())
  graph.append(b)

visited = [False] * (n+1) # 노드 방문 여부 확인

result = [] # 결과 집합
for i in range(1, n+1):
  if not visited[i]:
    cycle = []
    dfs(i)

for i in sorted(result):
  print(i)

 

✅ 인접한 4칸이 아닌 범위 내의 상하좌우 모두 탐색해야 하는 경우 (ex. 관련 문제)

  while q:
    x, y = q.popleft()

    for i in range(4):
      nx = x
      ny = y
      while True:
        nx += dx[i]
        ny += dy[i]
        if not(0<=nx<n and 0<=ny<n):  # 범위에서 벗어나기 전까지 계속 더함
          break
        if board[nx][ny] == 'O':   # 장애물을 만났다면 break
          break

 

이분탐색

데이터의 범위가 10만 단위 이상으로 넘어가면, 이진 탐색을 의심해보자

배열 내부의 데이터가 이미 정렬되어 있어야만 사용할 수 있는 알고리즘이며, 탐색 범위를 절반씩 좁혀가며 탐색하는 알고리즘

-> 배열이 정렬이 안되어있다면 먼저 sort 해주어야함!

 

시작점, 끝점, 중간점 설정이 중요하며 중간점 위치에 있는 데이터와 찾으려는 데이터를 반복적으로 비교하며 값을 찾아내는 알고리즘

 

시간복잡도 O(logN) : 탐색할 때마다 확인할 원소의 갯수가 절반씩 줄어든다는 특성

func binary_search(_ arr: [Int], _ target: Int) -> Int? {
  var start = 0
  var end = arr.count-1 // 특수한 경우가 아니라면, start와 end는 항상 양끝을 가리키게 함
  var mid = 0
  
  while start <= end {
    mid = (start+end) / 2   // 중간지점

	// 아래가 이분탐색 문제 유형에 따라 바뀔 수 있는 부분
    if arr[mid] == target {  // 만약 중간지점이 찾고자하는 값과 같다면, 해당 값을 리턴하고 탐색 중지
      return arr[mid]
    }
    else if arr[mid] < target { //찾고자 하는 수가 중간점보다 뒤에 있다면, 중간점 이후 탐색
      start = mid + 1
    }
    else { //찾고자 하는 수가 중간점보다 앞에 있다면, 끝점을 중간점 앞으로 (중간점 이전 탐색)
      end = mid - 1
    }
  }
  return nil
}

var arr = [1, 2, 3, 5, 6, 7, 9]
print(binary_search(arr, 7, 0, arr.count-1))

 

⭐️파라메트릭 서치(Parametric search)

원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제로, 배열이 정렬되어있지 않아도 이분탐색 원리를 이용해서 최적해를 찾는 알고리즘임

 

문제 예시 (키워드)

https://www.acmicpc.net/problem/1654

적어도 ~를 얻기 위해 설정할 수 있는 ~의 최소값/최대값

~를 만족하는 ~의 최소값/최대값

어떠어떠한 조건을 만족하는 값은?

-> 무언가를 만족해야하는 값을 찾기 위해 두 갈래로 나눠서 탐색하고, 만족할 수 있는 값을 계속 저장해두고 있다가 탐색의 마지막에 저장해두고 있었던 값 반환

 

💡 이분탐색/파라메트릭 서치의 문제 풀이 흐름

1) 입력 크기가 매우 크다 -> 2) 이분탐색으로 풀어야겠다 -> 3) 어떤 것을 탐색 기준으로 삼을까? 를 고민 (보통 최종 정답이 되는 값을 기준으로 탐색을 한다고 고려하되, 한번 더 탐색하는 데이터로 적절한지 확인할 필요 O)

4) 처음과 끝 지점 고민 (탐색 기준으로 삼은 값을 기준으로) -> 5) while 문으로 범위를 줄이면서 중간값이 최적해인지 확인

 

✅ 이분탐색 관련 Python 라이브러리

 

from bisect import

- bisect(배열, 찾을 값): 배열에서 원하는 값이 있는 인덱스 반환 (bisect_right과 동일하게 동작하며, 오른쪽을 우선으로 탐색함)

- bisect_left(배열, 찾을 값): 배열의 왼쪽 방향을 우선으로 해서 원하는 값이 있는 인덱스 반환 (대강 어느 방향인지 알고있다면 방향을 정해주는 것이 좋음)

단, 인덱스가 0부터 시작하는 것이 아닌 1부터 시작하므로 해당 사항을 주의하여 코딩

 

DP 

- 특정 범위가 반복되거나, 겹치는 구조를 가질 경우에 그 전에 계산된 값을 이용하여 중복적인 연산을 방지하는 알고리즘 기법

- 입력되는 수의 크기가(N) 매우 큰지 살필 것 (완전탐색으로 풀기에는 시간초과가 날만한 수의 범위인지)

ex) 피보나치

var dp = Array(repeating: 0, count:101) //수의 범위가 100까지일 때 초기화

dp[1] = 1
dp[2] = 1

n = 100

for i in 3..<n+1 {
	dp[i] = dp[i-1] + dp[i-2] //그전에 저장해둔 데이터 이용
}

print(dp[n])

 

✅ 냅색 알고리즘

적은 비용을 가지고 최대의 가치를 내야하는 키워드가 있을 때 의심해볼 알고리즘

특정 기준을 넘지 않는 선에서(혹은 최소로 하면서) 가치가 최대가 되도록 (특정 기준 이상의 가치를 만드는) 물건을 고르는 알고리즘

k = 버틸 수 있는 무게 = 최대 넣을 수 있는 물건의 무게

n = 물건의 개수

dp 테이블 = x축 / 물건의 개수, y축 / 물건의 무게, dp[i][j] = 가치의 최대값 

import Foundation

let nk = readLine()!.split(separator:" ").map { Int($0)! }
let n = nk[0], k = nk[1]

var dp = Array(repeating: Array(repeating:0, count: k+1), count:n+1)
var arr:[(Int, Int)] = [(0, 0)]
for _ in 0..<n {
  let input = readLine()!.split(separator:" ").map { Int($0)! }
  arr.append((input[0], input[1]))
}

// j: 현재 내가 배낭에 들어갈 수 있는 최대 무게
for i in 1...n {
  for j in 1...k {
    let (w, v) = arr[i] // 각 물건의 무게, 가치

    if j >= w { // j가 현재 담으려는 물건의 무게보다 크거나 같으면
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
      // i-1: 현재 i라는 물건을 안담았을 때를 의미함
    } else { // j < w : 물건의 무게가 현재 배낭의 무게보다 큰 경우
      dp[i][j] = dp[i-1][j] // 이전 값 그대로 가져옴
    }
  }
}

print(dp[n][k])

 

자료구조 활용 (스택, 큐, 트리, 우선순위 큐)

1) 스택

- 후입 선출의 구조인게 보일 때, 순서를 저장해두고 있어야할 때

- 연속적으로 벌어지는 일 도중 특정 시점을 알아야할 때 

- 후위 표기법, 괄호 (이외에도 짝을 지어야만 하는 것들 관련을 다룰때)

 

2) 큐 (from collections import deque 사용)

- 선입 선출의 구조인게 보일 때, 순서를 저장해두고 있어야할 때

- 항목을 모두 모아서 처리해야할 때

=> 리스트보다 appendleft, popleft 의 시간복잡도가 더 빠름(O(1)임)

 

3) 트리 순회

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

 

4) 우선순위 큐

- 최소값/최대값을 O(1)의 시간복잡도로 찾아낼 수 있는 자료구조

- import heapq를 통해 라이브러리 호출 및 사용

 

투포인터

배열에서 이중 for문으로 O(n^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(n)에 해결하는 알고리즘

(n이 매우 클 때, 구간에 관련된 연산을 할 때 연산의 크기를 줄여주는 알고리즘)

주로 특정 구간과 관련하여 "구간 합", "누적 합", "범위가 큰 배열의 정렬", "최장 부분 수열" 등의 유형에서 쓰인다.

어 뭔가 이 문제 조건을 만족하는 조합 구하는것 같은데? 그런데 0부터 돌아야될것 같네? -> 투포인터 의심

전형적인 투포인터 문제 : BOJ 2003

let input = readLine()!.split(separator:" ").map { Int(String($0))! }
let n = input[0], m = input[1]
let arr = readLine()!.split(separator:" ").map { Int(String($0))! }

var start = 0, end = 0
var sum = 0, count = 0

while end < n {
    if sum >= m {
        sum -= arr[start]
        start += 1
    } else {
        sum += arr[end]
        end += 1
        if end >= n { break }
    }
    if sum == m { count += 1 }
}

print(count)

1) start와 end를 초기에 0으로 잡는다.

2) sum이 m에 미치지 못하면 더 큰 수를 더 해야하므로 end를 ++ 하고, 더 크면 더 작게 만들어하므로 기존 수를 뺀 다음 start를 ++ 해준다. (기준에 미치지 못하면 end를 이동하고, 미치지 않거나 이미 미친 상황에서 추가 조건을 따져야할 때 start 조절하는 형태)

 

+ 추가 예시 문제  (딕셔너리 이용)

https://www.acmicpc.net/problem/15565

 

 

import sys
from collections import defaultdict

input = sys.stdin.readline
n, k = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))

dic = defaultdict(int)

start = 0
end = 0

dic[arr[start]] = 1
answer = int(1e9)

while end < n:
  if dic[1] < k:
    end += 1
    if end >= n:
      break
    dic[arr[end]] += 1
  else:
    answer = min(answer, end - start + 1)
    dic[arr[start]] -= 1
    start += 1

if answer == int(1e9):
  print(-1)
else:
  print(answer)

https://www.acmicpc.net/problem/15961

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

 

⭐️ 구간합 빠르게 구하기

# 데이터의 개수 N과 전체 데이터 선언
n = 5
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)

# 구간 합 계산 (세 번째 수부터 네 번째 수까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left - 1])

 

⭐️ 이분탐색  vs 투포인터

1) 이분탐색은 데이터가 정렬되어있어야 하고, 투포인터는 그런 제약이 없음

2) 이분탐색은 중간점을 바꿔가면서 탐색 범위를 절반으로 줄이고, 투포인터는 조건에 따라 포인터를 움직여가며 적절한 값을 찾아냄 

 

⭐️ 슬라이딩 윈도우

투포인터랑 원리는 똑같은데, 슬라이딩 윈도우는 start와 end가 이동하는 구간이 항상 같다. (길이가 2로 고정된 창틀을 차례대로 움직이는 그림과 같음)

 

전형적인 슬라이딩 윈도우 문제: https://www.acmicpc.net/problem/2559

import Foundation

let input = readLine()!.split(separator:" ").map { Int($0)! }
let n = input[0], k = input[1]
let arr = readLine()!.split(separator:" ").map { Int($0)! }

var start = 0, end = k-1
var sum = arr[start...end].reduce(0, +), answer = -987654321

while true {
  if sum > answer {
    answer = sum
  }

  if end == n-1 {
    break
  }
  
  sum -= arr[start]   // sum에서 기존 start의 값을 빼고
  start += 1   // start를 늘리고 
  end += 1  //end를 늘린다음
  sum += arr[end]   // sum에 end의 값을 더해줌
  // 정해진 길이의 창문을 이동하는 것과 같음
}

print(answer)

 

최단경로 알고리즘 (다익스트라, 플로이드 워셜)

다익스트라

- 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘

- 가중치가 양수일 때 사용 가능

- 우선순위 큐(힙) 사용 (Swift에서는 힙 라이브러리가 없어서 직접 구현해야함 - Python은 import heapq 사용)

- 각 노드에 대한 최단거리를 담는 배열을 선언하고, 순차 탐색하며 방문하지 않은 노드 중에 최단 거리가 가장 짧은 노드를 선택하며 해당 배열을 갱신하는 방식이다.

- 우선순위 큐를 사용한 다익스트라의 시간복잡도는 O(ElogV) 이므로, 수의 범위가 크면 다익스트라를 사용하는 것이 유리하다.

- 각각의 distance의 인덱스에 해당하는 값은, start 지점에서 해당 인덱스 노드까지 이동했을 때의 최단거리이다.

 

Python

https://github.com/yurrrri/python_algorithm_practice/blob/main/This_is_codingtest/ShortPath/Dijkstra/dijkstra_queue.py

GitHub - yurrrri/python_algorithm_practice: 파이썬 알고리즘 문제풀이 레포

 

플로이드 워셜

- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우

- 시간복잡도 O(n^3) 이므로, 수의 범위가 크지 않을 때 사용하는 것이 유리하다.

- A에서 B로 가는 최단경로일 때, A->B 와 A->K->B 경로 중 최소값을 2차원 배열에 저장해나가는 방식이다.

https://github.com/yurrrri/swift_algorim_practice/blob/main/This_is_codingtest/floyd-warshal.swift

GitHub - yurrrri/swift_algorim_practice: 스위프트 알고리즘 풀이 레포

 

💡BFS로 최단거리를 구하는것 VS 다익스트라 / 플로이드 워셜 차이점

 

- 가장 큰 차이점은 BFS는 모든 노드의 간선 가중치가 1이라고 가정(1-0 BFS 알고리즘은 0과 1만 존재)하는 것이고,

다익스트라와 플로이드 워셜은 가중치가 1뿐만 아니라 다양하게 존재한다는 것이다. 따라서 문제를 볼 때 가중치의 값을 먼저 확인해야한다.

 

LIS, LCS

https://devyul.tistory.com/entry/%08Swift-백준-가장-긴-증가하는-부분-수열LIS-관련-문제풀이