AI Lab에서 배우는 코딩테스트준비를 위한 자료구조/알고리즘
1일차
재귀
완전탐색
- 조합
- 순열
- 부분집합
2일차
큐/스택
그래프
- DFS
- BFS
3일차
암시적 그래프
암시적 그래프 DFS
암시적 그래프 BFS
우선순위큐
Dijkstra
완전 탐색 : 정답이 될 가능성이 있는 후보들을 모두 탐색한다.
1. TWO SUM
https://leetcode.com/problems/two-sum/
코드 구현(수업)
nums = [4,9,7,5,1]
n = len(nums)
for i in range(n):
for j in range(i+1, n):
print(nums[i], nums[j], 'n+m: ', nums[i]+nums[j])
if nums[i]+nums[j] == 14:
print('찾았다!')
print('i:', i, 'j:',j)제출코드
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i+1, n):
if nums[i]+nums[j] == target:
return [i, j]
재귀함수 : 자신을 정의할 때 자기자신을 재참조하는 함수
- 점화식
- Base Case
2. 재귀 풀이
# Two Sum 문제를 재귀로 구현
def solution(nums, target):
n = len(nums)
def recursion(ans, start):
if len(ans) == 2:
if nums[ans[0]] + nums[ans[1]] == target:
return ans
return False
for i in range(start, n):
ans.append(i)
if recursion(ans, i+1):
return ans
ans.pop()
return recursion([], 0)
print( solution(nums = [4,9,7,5,1], target = 14) )# leetcode 제출
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
def recursion(ans, start):
if len(ans) == 2:
if nums[ans[0]] + nums[ans[1]] == target:
return ans # return True => 같은 결과
return False
for i in range(start, n):
ans.append(i)
if recursion(ans, i+1):
return ans
ans.pop()
return recursion([], 0)
백트래킹(backtracking) : 정답이 될 가능성이 없는 후보는 더 이상 탐색하지 않고 포기하면서 탐색
조합/순열/부분집합
3. Combinations
https://leetcode.com/problems/combinations/
# Two Sum 문제를 조합으로 구현
def solution(n, k):
choices = []
def recursion(choice, start):
if len(choice) == k:
choices.append(choice[:])
return
for i in range(start, n+1):
choice.append(i)
recursion(choice, i+1)
choice.pop()
recursion([], 1)
return choices
print( solution(1, 1) )# leetcode 제출
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
choices = []
def recursion(choice, start):
if len(choice) == k:
choices.append(choice[:])
return
for i in range(start, n+1):
choice.append(i)
recursion(choice, i+1)
choice.pop()
recursion([], 1)
return choices
itertools 사용하여 코드 작성
from itertools import combinations
print(list(combinations([1,2,3,4,5], 3)))
4. 피로도
https://school.programmers.co.kr/learn/courses/30/lessons/87946
재귀
def solution(k, dungeons):
answer = 0
n = len(dungeons)
visited = [0] * n
def backtrack(k, cnt):
nonlocal answer
if cnt > answer:
answer = cnt
for i in range(n):
if k >= dungeons[i][0] and not visited[i]:
visited[i] = True
backtrack(k - dungeons[i][1], cnt + 1)
visited[i] = False
backtrack(k, 0)
return answer
itertools
from itertools import permutations
def solution(k, dungeons):
max_count = 0
for dungeon_order in permutations(dungeons):
print(dungeon_order)
curr_stamina = k
count = 0
for req, cost in dungeon_order:
if curr_stamina >= req:
curr_stamina -= cost
count += 1
else:
break
max_count = max(max_count, count)
return max_count
5. 자물쇠와 열쇠
https://school.programmers.co.kr/learn/courses/30/lessons/60059
def solution(key, lock):
m = len(key)
n = len(lock)
keys = [[[0 for _ in range(m+2*n)] for _ in range(m+2*n)] for _ in range(4)]
for i in range(m):
for j in range(m):
keys[0][n+i][n+j] = key[i][j]
keys[1][n+j][m+n-1-i] = key[i][j]
keys[2][m+n-1-i][m+n-1-j] = key[i][j]
keys[3][m+n-1-j][n+i] = key[i][j]
for k in keys:
for i in range(m+n):
for j in range(m+n):
flag = True
for ii in range(n):
for jj in range(n):
if not lock[ii][jj] ^ k[i+ii][j+jj]:
flag = False
if flag:
return True
return False
6. 순열
https://leetcode.com/problems/permutations/
class Solution:
def permute(self, nums):
def backtrack(curr):
if len(curr) == len(nums):
ans.append(curr[:])
return
for num in nums:
if num not in curr:
curr.append(num)
backtrack(curr)
curr.pop()
ans = []
backtrack([])
return ans
7. 부분집합
https://leetcode.com/problems/subsets/
class Solution:
def subsets(self, nums):
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
result = []
backtrack(0, [])
return result
Queue : FIFO( First In First Out ) - Linked List
- 선입선출, 줄서기, 프린트, 예약하기
- BFS
from collections import deque
q = deque()
q.append(1)
q.append(2)
q.append(3)
q.append(4)
q.popleft() # 1
q.popleft() # 2
q.popleft() # 3
q.popleft() # 4
Stack : LIFO(Last In First Out) - List
- 괄호 유효성 문제, 짝맞추기
- 재귀대신 stack을 사용가능(DFS)
s = []
s.append(1)
s.append(2)
s.append(3)
s.append(4)
s.pop() # 4
s.pop() # 3
s.pop() # 2
s.pop() # 1
8. 괄호 유효성 문제
https://school.programmers.co.kr/learn/courses/30/lessons/12909
Counting 방법으로 풀이
def solution(s):
count = 0
ls = list(s)
for i in range(len(s)):
p = ls.pop()
if p == ")":
count += 1
else:
count -= 1
if count < 0:
return False
if count > 0:
return False
return True
def solution(s):
answer = True
count = 0
ls = list(s)
for i in range(len(s)):
p = ls.pop()
if p == ")":
count += 1
else:
count -= 1
if count < 0:
answer = False
if count > 0:
answer = False
return answer
스택 기본 풀이
def solution(s):
stack = []
for p in s:
if p == "(":
stack.append(p)
else:
if not stack:
return False
stack.pop()
return not stack
그래프 Graph - 객체간 연결관계, node(vertex), 간선
방향(시작, 끝), 무방향(양방향) 그래프
다중(두 정점사이 여러 간선, self-loop), 단순(하나의 간선만) 그래프
가중치(각 간선에 특정 값 할당 : 다익스트라), 비가중치 그래프
순환(시작정점과 끝정점이 같은 사이클이 존재), 비순환(tree, DAG, 위상정렬) 그래프
Graph 구현 방법
- 인접행렬 - 메모리 크기로 인해 사이즈가 클 경우 잘 사용하지 않는다. ( 정점에 비해 간선이 적이 낭비가 많다 )
- 인접 리스트 - 연결된 다른 노드들의 목록을 리스트 형태로 관리
graph = {
1: [2, 3, 5],
2: [1, 4],
3: [1, 5],
4: [2, 5],
5: [1, 3, 4]
}
for next_v in graph[1]:
print(next_v)
- 암시적 그래프(grid, implicit graph) - 숨겨져 있는 그래프
그래프 순회 Traversal - 모든 노드를 방문하는 과정
- DFS
- BFS
너비 우선 탐색 구현
from collections import deque
def bfs(graph, start_v):
q = deque()
# 시작점 예약
q.append(start_v)
# 방문 표시
visited = {start_v: True}
while q:
# 방문
cur_v = q.popleft()
print(cur_v, end=' ')
# 다음 방문 예약
for next_v in graph[cur_v]:
if next_v not in visited: # dictionary key 여부 확인
visited[next_v] = True
q.append(next_v)
graph = {
0: [1, 3, 6],
1: [0, 3],
2: [3],
3: [0, 1, 2, 7],
4: [5],
5: [4, 6, 7],
6: [0, 5],
7: [3, 5],
}
bfs(graph, start_v=0)
깊이 우선 탐색
def dfs(cur_v):
# 방문
visited[cur_v] = True
print(cur_v, end=" ")
# 다음 방문
for next_v in graph[cur_v]:
if next_v not in visited:
dfs(next_v)
visited = {}
graph = {
0: [1, 3, 6],
1: [0, 3],
2: [3],
3: [0, 1, 2, 7],
4: [5],
5: [4, 6, 7],
6: [0, 5],
7: [3, 5],
}
dfs(0) # 0 1 3 2 7 5 4 6
dfs(1) # 1 0 3 2 7 5 4 6
dfs(3) # 3 0 1 6 5 4 7 2
dfs(5) # 5 4 6 0 1 3 2 7
9. Keys and Rooms
https://leetcode.com/problems/keys-and-rooms/description/
# keys and rooms - dfs 구현
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
visited = {}
def dfs(cur_v):
visited[cur_v] = True
# print(cur_v, end=" ")
for next_v in rooms[cur_v]:
if next_v not in visited:
dfs(next_v)
dfs(0)
if len(visited) == len(rooms):
return True
else:
return False
###################################
## BFS
######################################
from collections import deque
class Solution:
def canVisitAllRooms(self, rooms) -> bool:
n = len(rooms)
visited = [False] * n
def bfs(start_v):
q = deque()
q.append(start_v)
visited[start_v] = True
# print(cur_v, end=" ")
while q:
cur_v = q.popleft()
for next_v in rooms[cur_v]:
if not visited[next_v]:
q.append(next_v)
visited[next_v] = True
bfs(start_v=0)
# print(visited)
return all(visited)
s = Solution()
print(s.canVisitAllRooms(rooms = [[1],[2],[3],[]]))
히든 문제 1: 컴퓨터 네트워크
https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=python3
def solution(n, computers):
answer = 0
visited = [False] * n
def dfs(cur_v):
visited[cur_v] = True
for next_v, edge in enumerate(computers[cur_v]):
if cur_v == next_v:
continue
if (not visited[next_v]) and edge:
dfs(next_v)
for i in range(n):
if not visited[i]:
answer += 1
dfs(i)
return answer
주말에 풀어보는 히든 문제
히든 문제 2: Is Graph Bipartite
https://leetcode.com/problems/is-graph-bipartite/
DFS로 풀이
# DFS
class Solution:
def isBipartite(self, graph) -> bool:
bipart = [0] * len(graph)
def dfs(i):
if not bipart[i]:
bipart[i] = -1
for neighbor in graph[i]:
if bipart[i] == bipart[neighbor]:
return False
elif not bipart[neighbor]:
bipart[neighbor] = -1 * bipart[i]
dfs(neighbor)
return True
for i in range(len(graph)):
if not dfs(i):
return False
return True
a = Solution()
print(a.isBipartite(graph = [[1,2,3],[0,2],[0,1,3],[0,2]]))
print(a.isBipartite(graph = [[1,3],[0,2],[1,3],[0,2]]))
BFS로 풀이
# BFS
from collections import deque
class Solution:
def isBipartite(self, graph) -> bool:
bipart = [0] * len(graph)
def bfs(i):
if bipart[i]:
return True
q = deque([i])
bipart[i] = -1
while q:
i = q.popleft()
for neig in graph[i]:
if bipart[i] == bipart[neig]:
return False
elif not bipart[neig]:
q.append(neig)
bipart[neig] = -1 * bipart[i]
return True
for i in range(len(graph)):
if not bfs(i):
return False
return True
a = Solution()
print(a.isBipartite(graph = [[1,2,3],[0,2],[0,1,3],[0,2]]))
print(a.isBipartite(graph = [[1,3],[0,2],[1,3],[0,2]]))
히든 문제 3: Coin Change
https://leetcode.com/problems/coin-change/description/
DP로 풀이
# dp
import math
class Solution:
def coinChange(self, coins, amount: int) -> int:
dp = [math.inf] * (amount+1)
dp[0] = 0
for coin in coins:
for i in range(1, amount+1):
if i - coin >= 0:
if dp[i] > dp[i-coin] + 1:
dp[i] = dp[i-coin] + 1
return -1 if dp[amount] == math.inf else dp[amount]
a = Solution()
print( a.coinChange(coins = [1,2,5], amount = 11))
print( a.coinChange(coins = [2], amount = 3))
print( a.coinChange(coins = [1], amount = 0))
3일차 알고리즘 수업
암시적 그래프
- 최단거리 구할 때 BFS를 사용하자.
# 상하좌우 offset
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
# 상하좌우 확인
next_r = cur_r + dr
next_c = cur_c + dc
암시적 그래프 DFS code구현
def isValid(r, c):
return 0 <= r < row_len and 0 <= c < col_len and grid[r][c] == 1
def dfs(r, c):
visited[r][c] = True
print(r, c)
for i in range(4):
next_r = r + dr[i]
next_c = c + dc[i]
if isValid(next_r, next_c):
if not visited[next_r][next_c]:
dfs(next_r, next_c)
grid = [
[1, 1, 1, 1],
[0, 1, 0, 1],
[0, 1, 0, 1],
[1, 0, 1, 1],
]
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
dfs(0, 0)
암시적 그래프 BFS code구현
from collections import deque
def isValid(r, c):
return 0 <= r < row_len and 0 <= c < col_len and grid[r][c] == 1
def bfs(r, c):
visited[r][c] = True
q = deque()
q.append((r,c))
while q:
cur_r, cur_c = q.popleft()
print("BFS ", cur_r, cur_c)
for i in range(4):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if isValid(next_r, next_c):
if not visited[next_r][next_c]:
visited[next_r][next_c] = True
q.append((next_r, next_c))
grid = [
[1, 1, 1, 1],
[0, 1, 0, 1],
[0, 1, 0, 1],
[1, 0, 1, 1],
]
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
bfs(0, 0)
10. Number of Islands
https://leetcode.com/problems/number-of-islands/
dfs 풀이
class Solution:
def numIslands(self, grid) -> int:
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
# 상하좌우 offset
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
land_count = 0
def isValid(r, c):
return 0 <= r < row_len and 0 <= c < col_len and grid[r][c] == '1'
def dfs(r, c):
visited[r][c] = True
# print(r, c)
for i in range(4):
next_r = r + dr[i]
next_c = c + dc[i]
if isValid(next_r, next_c):
if not visited[next_r][next_c]:
dfs(next_r, next_c)
for i in range(row_len):
for j in range(col_len):
if grid[i][j] == "1":
if not visited[i][j]:
dfs(i, j)
land_count += 1
return land_count
# grid = [
# ["1","1","1","1","0"],
# ["1","1","0","1","0"],
# ["1","1","0","0","0"],
# ["0","0","0","0","0"]
# ]
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
s = Solution()
print(s.numIslands(grid))
bfs 풀이
from collections import deque
class Solution:
def numIslands(self, grid):
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
cnt = 0
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
def bfs(r, c):
q = deque()
q.append((r,c))
visited[r][c] = True
while q:
cur_r, cur_c = q.popleft()
for i in range(4):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len:
if grid[next_r][next_c] == '1':
if not visited[next_r][next_c]:
q.append((next_r,next_c))
visited[next_r][next_c] = True
for i in range(row_len):
for j in range(col_len):
if grid[i][j] == "1" and not visited[i][j]:
bfs(i,j)
cnt += 1
return cnt
grid = [
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "1", "0"],
["0", "0", "0", "1", "1"],
]
s=Solution()
print(s.numIslands(grid))
히든문제4 : 거리두기 확인하기
https://school.programmers.co.kr/learn/courses/30/lessons/81302
from collections import deque
def solution(places):
answer = []
row_len, col_len = 5, 5
# 상하좌우 offset
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]
def bfs(place):
visited = [[False] * 5 for _ in range(5)]
ps = []
for i in range(row_len):
for j in range(col_len):
if place[i][j] == 'P':
ps.append((i,j))
for (r,c) in ps:
q = deque()
q.append((r, c, 0))
visited[r][c] = True
while q:
cur_r, cur_c, cur_dist = q.popleft()
for i in range(4):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len:
if place[next_r][next_c] == 'X':
continue
if not visited[next_r][next_c]:
if cur_dist <= 1 and place[next_r][next_c] == 'P':
return 0
if place[next_r][next_c] == 'O':
visited[next_r][next_c] = True
q.append((next_r, next_c, cur_dist+1))
return 1
for place in places:
chk = bfs(place)
answer.append( chk )
return answer
places = [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"],
["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"],
["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"],
["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"],
["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]
print( solution(places) )
11. shortest path
https://leetcode.com/problems/shortest-path-in-binary-matrix/description/
from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid):
# BFS 초기세팅
q = deque()
# q.append(start_r, start_c, start_distance)
q.append((0, 0, 1))
# vististed = 초기화
row_len, col_len = len(grid), len(grid[0])
visited = [[False] * col_len for _ in range(row_len)]
dist = [[9999] * col_len for _ in range(row_len)]
dist[0][0] = 1
# 8방향 offset
dr = [0, 1, 0, -1, 1, 1, -1, -1]
dc = [1, 0, -1, 0, 1, -1, 1, -1]
while q:
# 현재 노드 방문
cur_r, cur_c, cur_dist = q.popleft()
if grid[cur_r][cur_c]:
dist[cur_r][cur_c] = -1
break
# 다음 노드 예약
for i in range(8):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len and grid[next_r][next_c] == 0:
if not visited[next_r][next_c]:
visited[next_r][next_c] = True
q.append((next_r, next_c, cur_dist+1))
if dist[next_r][next_c] > cur_dist+1:
dist[next_r][next_c] = cur_dist+1
return -1 if dist[row_len-1][col_len-1]==9999 else dist[row_len-1][col_len-1]
s=Solution()
grid = [
[0,0,0],
[1,1,0],
[1,1,0]
]
# grid = [[0,1],[1,0]]
# grid = [[1,0,0],[1,1,0],[1,1,0]]
print(s.shortestPathBinaryMatrix(grid))# 강사 풀이
from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid):
row_len, col_len = len(grid), len(grid[0])
dr = [1, 0, -1, 0, 1, 1, -1, -1]
dc = [0, 1, 0, -1, 1, -1, 1, -1]
if grid[0][0] == 1:
return -1
# BFS 초기세팅
q = deque()
q.append((0, 0, 1))
visited = [[False] * col_len for _ in range(row_len)]
while q:
cur_r, cur_c, cur_d = q.popleft()
if cur_r == row_len-1 and cur_c == col_len-1:
return cur_d
for i in range(8):
next_r = cur_r + dr[i]
next_c = cur_c + dc[i]
if 0 <= next_r < row_len and 0 <= next_c < col_len:
if grid[next_r][next_c] == 0:
if not visited[next_r][next_c]:
q.append((next_r,next_c, cur_d+1))
visited[next_r][next_c] = True
return -1
우선순위큐
- 가장 높은 우선순위를 가진 데이터 OUT 되는 자료 구조
- 완전 이진트리
Heap : 완전 이진트리(자식이 최대2개이고, 왼쪽부터 채워짐)
- min heap
- max heap
Min heap
import heapq
min_heap = [5,3,9,4,1,2,6]
heapq.heapify(min_heap)
print(min_heap) # [1, 3, 2, 4, 5, 9, 6]
print(heapq.heappop(min_heap)) # 1
print(min_heap) # [2, 3, 6, 4, 5, 9]
heapq.heappush(min_heap, 1)
print(min_heap) # [1, 3, 2, 4, 5, 9, 6]
Max Heap
import heapq
max_heap = [5,3,9,4,1,2,6]
max_heap = [i * -1 for i in max_heap]
heapq.heapify(max_heap)
print(max_heap) # [-9, -4, -6, -3, -1, -2, -5]
print(heapq.heappop(max_heap)) # -9
print(max_heap) # [-6, -4, -5, -3, -1, -2]
heapq.heappush(max_heap, -9)
print(max_heap) # [-9, -4, -6, -3, -1, -2, -5]
다익스트라
- 가중치 그래프에서 시작점과 도착점이 주어졌을 때, 최단경로를 구하는 알고리즘
# 예제코드
def dijkstra(graph, start_v, dest, n):
distances = [INF] * (n + 1)
distances[start_v] = 0
pq = [(0, start_v)]
while pq:
cur_dist, cur_v = heapq.heappop(pq)
if distances[cur_v] < cur_dist:
continue
for next_v, cost in graph[cur_v]:
next_dist = distances[cur_v] + cost
if next_dist < distances[next_v]:
distances[next_v] = next_dist
heapq.heappush(pq, (next_dist, next_v))
return distances[dest]
graph = { … }
dijkstra(graph, 1, 8, len(graph))
다익스트라 출제 경향 살펴보기
- 카카오 Tech 인턴십 - 등산코드 정하기
- Network Delay Time
느낀점:
지속적인 학습이 중요하다.
오랜만에 알고리즘 문제를 풀어보니 머리가 안돌아간다.
다시 시작해 보자!
[ 나중에 풀어볼 문제들 ]
히든문제 5 : 스타트 택시
https://www.acmicpc.net/problem/19238
Network Delay Time
https://leetcode.com/problems/network-delay-time/description/