알고리즘 스터디 - 구현 2문제 풀이(feat. Python)

이번에 취업 스터디를 만들면서 모든 기업이 그렇듯이 코테 통과가 우선이고 여기서 수많은 사람들이 탈락하기에 중점을 알고리즘 문제 풀이 습관에 두었다.

또한, CS 및 이력서 점검도 사실 전에 스터디를 해보는 결과 한번 외우고 세팅이 되면 어렵지 않은 부분이라 초점을 알고리즘으로 두어 이코테에 나온 문제 유형 분포에 따라서 과제도 세팅을 하였다. 오늘의 주제는 구현으로 실버1, 골드4 단계별로 문제를 풀고 익숙해지기로 했다.

백준 20207번 : 달력 - 실버 1

n = int(input())

calender = [0] * 366

for _ in range(n):
    s, e = map(int, input().split())

    for index in range(s, e+1):
        calender[index] += 1

x_len = 0
y_len = 0

answer = 0

for i in range(366):
    if calender[i] != 0:
        x_len = max(x_len, calender[i])
        y_len += 1
    else:
        answer += x_len * y_len
        x_len = 0
        y_len = 0


answer += x_len * y_len
print(answer)

백준 22856번 : 트리 순회 - 골드 4

문제를 풀었는데 계속 46%에서 틀렸다고 떠서 다른 사람들거를 보며 따라 치며 가져오게 되었다ㅠㅠ

import sys
sys.setrecursionlimit(10**7)
 
left = dict()
right = dict()
 
N = int(input())
parent = [0] * (N+1)
node_count = 0
for _ in range(N):
    a, b, c = map(int, input().split())
    left[a] = b
    right[a] = c
 
    if b != -1:
        parent[b] = a
        node_count += 1
    if c != -1:
        parent[c] = a
        node_count += 1
 
# 마지막 노드 구하는 파트
last_node = 0
def traverse(node):
    global last_node
    if node == -1:
        return
    traverse(left[node])
    last_node = node
    traverse(right[node])
 
traverse(1)
edge_count = node_count * 2
movement = 0
# 마지막 노드까지 이동 경로의 거리 구함
while last_node != 1:
    movement += 1
    last_node = parent[last_node]
print(edge_count - movement)

• 구현 문제는 주어진 논리 구조에 따라서 알고리즘을 스스로 만들어가는 능력을 평가하는 것으로 실버 1 문제가 바로 이 것에 해당한다. 그리고 골드 4문제 같은 경우는 기존에 다른 알고리즘+알고리즘 구현을 요구하는 것임을 알 수 있었다.