1. 아이디어
>> 문제에서 주어진 방문순서는 중위 순회이다.
>> 레벨과 방문순서가 주어진다.
>> 주어진 것으로 트리의 정보를 구해야 한다.
>> 어떻게 구하지..?
>> 중위순회를 반대로 실행해야 한다.
>> level 활용하기
>> 중위순회 입력된 리스트 가운데가 항상 root 노드임을 활용하기
>> 중위 순회로 입력된 리스트를 왼쪽 부분 트리, 오른쪽 부분 트리로 쪼갤 줄 알아야한다.
2. 시간복잡도
>>
3. 자료구조
>>
import sys
sys.setrecursionlimit(10**9)
n = int(input())
# 트리
tree = [[] for _ in range(n+1)]
# 부모 노드 저장
relation = [0 for _ in range(n+1)]
for _ in range(n-1):
a, b = map(int, input().split())
tree[a].append(b)
tree[b].append(a)
def dfs(start, tree, relation):
# 연결된 노드들부터 relation[i] 의 부모가 없으면 부모 설정해주고 dfs를 돌린다.
for node in tree[start]:
if relation[node] == 0:
# node에게 너 여기서 출발했다고 표시해주는 느낌
relation[node] = start
dfs(node, tree, relation)
dfs(1, tree, relation)
for i in range(2, n+1):
print(relation[i])
기본적으로 제공 동의 등 항목체크하고 노트북 화면 공유, 노트북 캠 연결, 신분증 촬영 후 제출, 핸드폰 카메라 연결 등의 사전작업을 미리 체험해보게 됩니다. (테스트 당일날도 다시 똑같이 진행해야 됨)
또한 듀얼모니터 사용이 안되어 노트북화면 1대로만 시험을 치뤘습니다. ★
그리고 촬영 중에 다른 외부인이 비춰지면 안되고 독립된 공간에서 치뤄야 한다는 조항도 있어서 집에서 치뤘습니다.
4. 본 테스트
3시간 동안 4문제를 풀도록 출제됩니다.
문제1 유형 : DFS 방식으로 풀었습니다.
문제2 유형 : 트리 + DP
root에서 시작해서 dfs 를 활용한다.
dfs(x)
: x를 root로 하는 rooted tree에서 x의 모든 자식들의 값 계산해주는 함수
이렇게 함수 정의를 잘해주면 dfs에서 바로 계산이 가능하다.
많이 나오는 예시이므로 암기할 것 ★
트리 + DP 의 가장 쉬운 버전이라고 생각하시면 됩니다. ★
함수의 역할 자체를 잘 정의해주면 이걸 호출하는 것 만으로도 자식들의 결과를 자신의 결과에 쓸 수 있기 때문에 작은 문제의 결과로 큰 문제의 값을 빠르게 계산할 수 있죠.
문제3 유형 : DP
문제4 유형 : 단순 구현
5. 소감
트리와 DP 유형의 문제를 평소 풀지 않았던 터라 생각하는 로직은 맞았으나 코드로 구현하기 어려웠습니다.
그래서 문제1과 문제4만 풀어서 제출했으며 문제2와 문제3은 풀지못하였습니다.
또한 IDE에서 프로그래머스로 옮기는 과정에서 오타가 생겨 테스트 케이스를 돌릴 때 에러가 계속 발생했는데 에러 발생 여부만 알려주고 어느 줄에 발생했는지도 안알려줘서 해결하는데 시간낭비를 좀 많이 하였습니다.(※ 주의)
어느정도 연습했던 분이라면 3솔까지는 무난하게 하시지 않았을까 하는 생각이 듭니다.
6. 코드
# Q1.
# C3
# => 52
import sys
si = sys.stdin.readline
n = int(si())
a = [[0 for _ in range(10)] for __ in range(10)]
for _ in range(n):
coord = si().strip() # 병사의 좌표, D7 => 4행 7열
row = ord(coord[0]) - ord('A') + 1
col = int(coord[1])
dirs = [[-1, -1], [1, -1]]
for dr, dc in dirs:
for len in range(-7, 8):
nr = row + dr * len
nc = col + dc * len
if 1 <= nr <= 8 and 1 <= nc <= 8:
a[nr][nc] = 1
ans = 0
for i in range(1, 9):
for j in range(1, 9):
if a[i][j] == 0:
ans += 1
print(ans)
# Q2.
# 6 121
# 1 2
# 1 3
# 3 4
# 3 6
# 3 5
import sys
si = sys.stdin.readline
n, k = map(int, si().split())
children = [[] for _ in range(n + 1)]
hasParent = [0 for _ in range(n + 1)]
for _ in range(n - 1):
par, child = map(int, si().split())
children[par].append(child)
hasParent[child] = 1
value = [0 for _ in range(n + 1)]
def DFS(x):
# x의 모든 자식들에 대해 value 계산해주기
if not children[x]: # x 밖에 없는 상황
value[x] = 1
return
for child in children[x]:
DFS(child)
value[x] += value[child]
for i in range(1, n + 1):
if not hasParent[i]:
DFS(i)
total_value_sum = sum(value)
multiply = k // total_value_sum
for i in range(1, n + 1):
print(value[i] * multiply, end=' ')
# Q3.
# 4 4
# 2 1 2 1 3 4 4 3
# 1 2 3 4
# => 4
import sys
INF = 1000000009
si = sys.stdin.readline
n, m = map(int, si().split())
a = list(map(int, si().split()))
smells = list(map(int, si().split()))
# 각 향기마다 A랑 B위치 기억해두기
place = [[-1, -1] for _ in range(n + 1)]
for i in range(n * 2):
smell = a[i]
if place[smell][0] == -1:
place[smell][0] = i
else:
place[smell][1] = i
def get_dist(x, y):
# x번 위치에서 y번 위치로 가는 최단거리 계산
if x > y:
x, y = y, x
return min(y - x, n * 2 - (y - x))
# 배열 정의
dy = [[INF, INF] for _ in range(m + 1)]
dy[0][0], dy[0][1] = get_dist(0, place[smells[0]][0]), get_dist(0, place[smells[0]][1])
for i in range(1, m):
prev = smells[i - 1] # 직전에 맡은 향 번호
cur = smells[i] # 이번에 맡은 향 번호
for cur_k in range(2):
# dy[i][cur_k] 을 계산해줄 차례
curPosition = place[cur][cur_k]
prevA, prevB = place[prev][0], place[prev][1]
dy[i][cur_k] = min(dy[i - 1][0] + get_dist(prevA, curPosition), # 직전에 A번 위치 선택
dy[i - 1][1] + get_dist(prevB, curPosition)) # 직전에 B번 위치 선택
print(min(dy[m - 1]))
# Q4.
import sys
si = sys.stdin.readline
n = int(si())
a = [0] + list(map(int, si().split()))
b = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(i, n + 1, i):
b[j] += a[i]
for i in range(1, n + 1):
print(b[i], end=' ')
def solution(clothes):
# 1. 옷을 종류별로 구분하기
hash_map = {}
for clothe, type in clothes:
hash_map[type] = hash_map.get(type, 0) + 1
# 2. 입지 않는 경우를 추가하여 모든 조합 계산하기
answer = 1
for type in hash_map:
answer *= (hash_map[type] + 1)
# 3. 아무종류의 옷도 입지 않는 경우 제외하기
return answer - 1
(3) 정리
처음에 {type : [옷1, 옷2, 옷3]} 등으로 만들어야 하나 고민했으나 문제에서는 조건에 맞는 결과 값만 원하기 때문에 그럴 필요가 없음을 알게되었습니다.
위 코드처럼 list의 값 여러개를 여러변수에 동시에 할당하는 것을 unpacking이라 하는데 유용하게 쓸 수 있도록 연습해야할 것 같습니다. 또한 get() 함수 사용법 또한 익혀놔야겠습니다.
1. 아이디어
>> 반복문 돌면서 기준이되는 폰넘버를 다른 폰넘버가 앞자리부터 가지고 있는지 확인해본다.
>> slicing 활용!
2. 시간복잡도
>>
3. 자료구조
>>
(2) 코드
# 효율성 테스트 3,4 실패
def solution(phone_book):
phone_book.sort()
for num in range(0, len(phone_book)):
for target in range(num+1, len(phone_book)):
target_num = phone_book[target]
if phone_book[num] == target_num[0:len(phone_book[num])]:
return False
return True
# startswith() 를 활용하면 이중for문없이 해결할 수 있다.
def solution(phone_book):
phone_book.sort()
for num in range(0, len(phone_book)-1):
if phone_book[num+1].startswith(phone_book[num]):
return False
return True
# startswith() 와 zip() 을 활용한 풀이
def solution(phoneBook):
phoneBook.sort()
print(phoneBook)
print(phoneBook[1:])
print(list(zip(phoneBook, phoneBook[1:])))
for p1, p2 in zip(phoneBook, phoneBook[1:]):
if p2.startswith(p1):
return False
return True
