크래프톤 정글 회고: 2주차

정글 회고 목차

Week 0
Week 1
Week 2

2주차

2주차의 알고리즘들이 개인적으로 꽤나 성향에 잘 맞아서인지, 적응이 되어서인지 지난 주보다도 수월했다. 내 바램은 정글에서 강조하는 ‘컴퓨팅 사고로의 전환’이 나에게 일어난 것이길 바라지만, 지금 생각해보면 냉정하게 저 때의 나는 그냥 전보다 적응이 더 된 사람이었다.

2주차때는 우리 동기들 중 알고리즘을 가장 잘 하는 태성님과, 프론트엔드 개발자로 일한 경험이 있던 경원님과 조가 되었다. 코어타임을 제외하고는 각자 개인플레이 위주로 알고리즘 문제를 풀었기 때문에 조에 대해서는 크게 회고할 것이 없는 것 같다. 다만, 앞쪽 테이블에 있던 조가 너무 웃겨서 여섯이서 식사도 같이 하고 재밌었다.

공부 키워드로는 그래프(vertex, edge, node, arc), BFS, DFS, 위상정렬이 있었으며 여기에 더해 최소신장 트리와 다익스트라, 플로이드 와샬 알고리즘들까지도 커버했다. 알고리즘 및 키워드와는 별개로, CS:APP이 진짜 따라가기 힘들었는데, 다시 생각해봐도 확실히 비전공자 입장에서 맨땅에 헤딩하기에 친절한 책은 아닌 것 같다.

문제

트리 순회

N = int(input())

tree = {}

for _ in range(N):
    root, left, right = input().split()
    tree[root] = (left, right)

def preorder(root):
    if root != ".":
        print(root, end="")
        preorder(tree[root][0])
        preorder(tree[root][1])
        
def inorder(root):
    if root != ".":
        inorder(tree[root][0])
        print(root, end="")
        inorder(tree[root][1])

def postorder(root):
    if root != ".":
        postorder(tree[root][0])
        postorder(tree[root][1])
        print(root, end="")

preorder("A")
print()
inorder("A")
print()
postorder("A")

DFS와 BFS

import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().split())

adj = [[0] * N for _ in range(N)]
edges = []
for i in range(M):
    A,B = map(int, sys.stdin.readline().split())
    edges.append((A,B))


for edge in edges:
    adj[edge[0]-1][edge[1]-1] = 1
    adj[edge[1]-1][edge[0]-1] = 1

dfs_chk = [False] * (N+1)
bfs_chk = [False] * (N+1)
dfs_chk[0] = True
bfs_chk[0] = True

def dfs(now, arr):
    for nxt in range(len(arr)):
        if arr[now-1][nxt] and not (dfs_chk[nxt+1]):
            dfs_chk[nxt+1] = 1
            print(nxt+1, end=" ")
            dfs(nxt+1, arr)

def bfs(now, arr):
    dq = deque()
    dq.append(now-1)
    bfs_chk[now] = True
    print(now, end=" ")
    while dq:
        now = dq.popleft()
        for nxt in range(len(arr)):
            if arr[now][nxt] and not (bfs_chk[nxt+1]):           
                bfs_chk[nxt+1] = True
                print(nxt+1,end=" ")     
                dq.append(nxt)
        
dfs_chk[V] = True
print(V, end=" ")
dfs(V,adj)
print()
bfs(V, adj)

동전 2

import sys
input = sys.stdin.readline


n, k = map(int, input().split())

coins =[]

for i in range(n):
   coins.append(int(input()))

dp = [10001] * (k+1)
dp[0] = 0

for coin in coins:
   for i in range(coin, k+1):
       dp[i] = min(dp[i],dp[i-coin]+1)
if dp[k] == 10001:
   print(-1)
else:
   print(dp[k])

DP문제인데 왜 2주차에 있을까 싶었는데 문제의 주제를 보니 BFS라고 써져있다. 별도로 BFS방식으로도 풀어보아야겠다.

마치며

2주차 문제들과 키워드를 보니, 필수로 복습하고 넘어가야 할 주제들이 꽤 보여서 이는 별도로 키워드 정리와 문제풀이를 해야겠다.