1. 아이디어
>> 루트노드가 1인 정보가 주어져있다.
>> 그 외의 나머지는 연결관계만 주어져있다.
>> 이 경우 부모노드를 어떻게 파악하면 좋을까?
>> 우선 연결관계부터 만들어보자.
2. 시간복잡도
>>
3. 자료구조
(2) 예제 입력, 예제 출력
- 예제 입력 1 -
7166335412447
- 예제 출력 1 -
461314
- 예제 입력 2 -
121213243536474859510611612
- 예제 출력 2 -
11233445566
(3) 코드
import sys
sys.setrecursionlimit(10**9)
n = int(input())
# 트리
tree = [[] for _ inrange(n+1)]
# 부모 노드 저장
relation = [0for _ inrange(n+1)]
for _ inrange(n-1):
a, b = map(int, input().split())
tree[a].append(b)
tree[b].append(a)
defdfs(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 inrange(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# => 52import sys
si = sys.stdin.readline
n = int(si())
a = [[0for _ inrange(10)] for __ inrange(10)]
for _ inrange(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:
forleninrange(-7, 8):
nr = row + dr * len
nc = col + dc * lenif1 <= nr <= 8and1 <= nc <= 8:
a[nr][nc] = 1
ans = 0for i inrange(1, 9):
for j inrange(1, 9):
if a[i][j] == 0:
ans += 1print(ans)
# Q2.# 6 121# 1 2# 1 3# 3 4# 3 6# 3 5import sys
si = sys.stdin.readline
n, k = map(int, si().split())
children = [[] for _ inrange(n + 1)]
hasParent = [0for _ inrange(n + 1)]
for _ inrange(n - 1):
par, child = map(int, si().split())
children[par].append(child)
hasParent[child] = 1
value = [0for _ inrange(n + 1)]
defDFS(x):# x의 모든 자식들에 대해 value 계산해주기ifnot children[x]: # x 밖에 없는 상황
value[x] = 1returnfor child in children[x]:
DFS(child)
value[x] += value[child]
for i inrange(1, n + 1):
ifnot hasParent[i]:
DFS(i)
total_value_sum = sum(value)
multiply = k // total_value_sum
for i inrange(1, n + 1):
print(value[i] * multiply, end=' ')
# Q3.# 4 4# 2 1 2 1 3 4 4 3# 1 2 3 4# => 4import 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 _ inrange(n + 1)]
for i inrange(n * 2):
smell = a[i]
if place[smell][0] == -1:
place[smell][0] = i
else:
place[smell][1] = i
defget_dist(x, y):# x번 위치에서 y번 위치로 가는 최단거리 계산if x > y:
x, y = y, x
returnmin(y - x, n * 2 - (y - x))
# 배열 정의
dy = [[INF, INF] for _ inrange(m + 1)]
dy[0][0], dy[0][1] = get_dist(0, place[smells[0]][0]), get_dist(0, place[smells[0]][1])
for i inrange(1, m):
prev = smells[i - 1] # 직전에 맡은 향 번호
cur = smells[i] # 이번에 맡은 향 번호for cur_k inrange(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 = [0for _ inrange(n + 1)]
for i inrange(1, n + 1):
for j inrange(i, n + 1, i):
b[j] += a[i]
for i inrange(1, n + 1):
print(b[i], end=' ')
defsolution(clothes):# 1. 옷을 종류별로 구분하기
hash_map = {}
for clothe, typein clothes:
hash_map[type] = hash_map.get(type, 0) + 1# 2. 입지 않는 경우를 추가하여 모든 조합 계산하기
answer = 1fortypein 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 실패defsolution(phone_book):
phone_book.sort()
for num inrange(0, len(phone_book)):
for target inrange(num+1, len(phone_book)):
target_num = phone_book[target]
if phone_book[num] == target_num[0:len(phone_book[num])]:
returnFalsereturnTrue
# startswith() 를 활용하면 이중for문없이 해결할 수 있다.defsolution(phone_book):
phone_book.sort()
for num inrange(0, len(phone_book)-1):
if phone_book[num+1].startswith(phone_book[num]):
returnFalsereturnTrue
# startswith() 와 zip() 을 활용한 풀이defsolution(phoneBook):
phoneBook.sort()
print(phoneBook)
print(phoneBook[1:])
print(list(zip(phoneBook, phoneBook[1:])))
for p1, p2 inzip(phoneBook, phoneBook[1:]):
if p2.startswith(p1):
returnFalsereturnTrue
1. 아이디어
>> 정렬 후 비교해서>> 다른 경우가 생기는 경우를 return 한다.
2. 시간복잡도
>>
3. 자료구조
>>
(2) 코드
# 풀이1 : 리스트 정렬defsolution(participant, completion):
p = sorted(participant)
c = sorted(completion)
for i inrange(0, len(completion)):
if p[i] != c[i]:
return p[i]
return p[-1]
# 풀이2 : hash 이용defsolution(participant, completion):
hashDict = {}
sumHash = 0# 1. Hash : Participant의 dictionary 만들기# 2. Participant의 sum(hash) 구하기for part in participant:
hashDict[hash(part)] = part
print(hashDict)
sumHash += hash(part)
# 3. completion의 sum(hash) 빼기for comp in completion:
sumHash -= hash(comp)
# 4. 남은 값이 완주하지 못한 선수의 hash 값이 된다return hashDict[sumHash]
1. 아이디어
>> 특정 3칸을 차지하면 나머지 칸에서 ㄱ or ㄴ 형태로 3칸을 차지하는 모든 경우를 체크해서
>> 문제에서 요구하는 사항에 맞는 최댓값을 갱신시킨다.
>> 특정 3칸을 이동하고 다시 반복
>> 특정 3칸 ㄱ or ㄴ 형태를 어떻게 입력시킬 것인지?
>> ┌, ┐, └, ┘ 각 4가지 모양을 기준으로 위의 로직을 반복한다.
2. 시간복잡도
>>
3. 자료구조
>>
(2) 예제 입력, 예제 출력
- 예제 입력 1 -
3 3
32 83 75
24 96 56
71 88 12
- 예제 출력 1 -
632
- 예제 입력 2 -
1 1
7
- 예제 출력 2 -
0
(3) 코드
# (0,0)부터 시작# 시작점을 방문안했으면# 부메랑 블럭이 범위 안에 있고, 방문안했으면 --> 강도 계산# 시작점을 방문했으면# 시작점 = 한칸 옆deffirst(y, x):return woods[y][x-1] + 2*woods[y][x] + woods[y-1][x]
defsecond(y, x):return woods[y][x-1] + 2*woods[y][x] + woods[y+1][x]
defthird(y, x):return woods[y+1][x] + 2*woods[y][x] + woods[y][x+1]
deffourth(y, x):return woods[y-1][x] + 2*woods[y][x] + woods[y][x+1]
defsolve(y, x, strength):global N, M, answer
if x == M:
x = 0
y += 1if y == N:
answer = max(answer, strength)
returnifnot visited[y][x]:
if y - 1 >= 0and x - 1 >= 0andnot visited[y][x-1] andnot visited[y-1][x]:
visited[y][x] = visited[y][x-1] = visited[y-1][x] = True
this_strength = strength + first(y, x)
solve(y, x+1, this_strength)
visited[y][x] = visited[y][x-1] = visited[y-1][x] = Falseif y + 1 < N and x - 1 >= 0andnot visited[y+1][x] andnot visited[y][x-1]:
visited[y][x] = visited[y][x-1] = visited[y+1][x] = True
this_strength = strength + second(y, x)
solve(y, x+1, this_strength)
visited[y][x] = visited[y][x-1] = visited[y+1][x] = Falseif y + 1 < N and x + 1 < M andnot visited[y+1][x] andnot visited[y][x+1]:
visited[y][x] = visited[y][x+1] = visited[y+1][x] = True
this_strength = strength + third(y, x)
solve(y, x+1, this_strength)
visited[y][x] = visited[y][x+1] = visited[y+1][x] = Falseif y - 1 >= 0and x + 1 < M andnot visited[y-1][x] andnot visited[y][x+1]:
visited[y][x] = visited[y][x+1] = visited[y-1][x] = True
this_strength = strength + fourth(y, x)
solve(y, x+1, this_strength)
visited[y][x] = visited[y][x+1] = visited[y-1][x] = False
solve(y, x+1, strength)
N, M = map(int, input().split())
woods = [list(map(int, input().split())) for _ inrange(N)]
visited = [[False] * M for _ inrange(N)]
answer = 0
solve(0, 0, 0)
print(answer)
(4) 정리
아이디어는 맞았으나 구현을 제대로 못해 해답을 찾아본 문제입니다. 구체적으로 visited 등에 ┌, ┐, └, ┘등 각 모양을 체크 후 재귀를 구현하는걸 세세히 코드화시키지 못하였습니다. 구현력 기르는 연습을 계속해야할 듯 합니다.
1. 아이디어
>> 예제 입력과 예제 출력을 보고 뭔말인지 도저히 모르겠음
>> 문제 이해 함
>> 문제 조건에 맞는 1번째로 가장 작은수는 0>>2번째로 가장 작은 수는 1>>3번째로 가장 작은 수는 2>> ...
>>10번째로 가장 작은 수는 9>>11번째로 가장 작은 수는 10>>12번째로 가장 작은 수는 20>> 그래서 어떻게 풀건데?
>> 마지막 값 > 현재 값 경우, 재귀 진행하여 감소하는 수를 만들어 준다.
>> 감소하는 수를 정렬한다.
2. 시간복잡도
>>
3. 자료구조
>>
(2) 예제 입력, 예제 출력
- 예제 입력 1 -
sample
- 예제 출력 1 -
sample
(3) 코드
n = input()
arr = list()
result = list()
defdfs():iflen(arr) > 0:
result.append(int("".join(map(str, arr))))
for i inrange(0, 10):
iflen(arr) == 0or arr[-1] > i: # 마지막 값이 더 큰 경우
arr.append(i)
print(arr)
dfs()
arr.pop()
try:
dfs()
result.sort()
print(result[n - 1])
except:
print(-1)
