풀이 사이트: 프로그래머스 고득점 Kit!
# 완전 탐색
📝 피로도 (lv 2) - https://school.programmers.co.kr/learn/courses/30/lessons/87946
* 체감 난이도 : ⭐️⭐️⭐️ - -
- 체감 난이도가 별 3개나 되는 건 완전 탐색을 굉장히 오랜만에 풀어서이다.
- 현재 방문 가능한 모든 던전을 무작위 순서로 방문해보는 모든 경우의 수를 알아야했다.
- 재귀함수를 이용해서 방문체크를 하면서 현재 피로도 상태에서 중복되지 않는 던전을 모두 방문하는 방식으로 코드를 짰더니 백트래킹 형태가 되었다.
- 그래서 게시판에서 사람들의 코드를 확인해보니, 까맣게 잊고 있던 완전 탐색을 위해 백트래킹을 활용하기도 한다는 점이 떠올랐다.
- 풀고나니 백트래킹 느낌이라 이후로도 기억이 한 번에 나길 바라는 마음에서 3개로 채택했다.
def solution(k, dungeons):
answer = -1
visit = [0] * len(dungeons)
answer = find(visit, dungeons, 0, k)
return answer
def find(visit, dungeons, n, energe):
temp = n
temp = max(n, temp)
for i in range(len(visit)):
if visit[i] == 0 and energe >= dungeons[i][0]:
visit[i] = 1
temp = max(temp, find(visit, dungeons, n+1, energe-dungeons[i][1]))
visit[i] = 0
return temp
📝 전력망을 둘로 나누기 (lv 2) - https://school.programmers.co.kr/learn/courses/30/lessons/86971
* 체감 난이도 : ⭐️⭐️- - -
- 트리를 둘로 분리 되었을 때, 두 서브 트리의 차이가 가장 작은 엣지를 알기 위해선 모든 서브 트리의 크기를 알아야한다.
- 모든 서브트리의 크기를 알아내기 위해서, 재귀 함수와 방문체크를 이용했다.
- 재귀 함수를 통해 리프노드까지 내려간 후 다시 루트노드까지 올라오면서, 현재 노드의 모든 서브노드의 크기를 더하는 방식으로 구현했다.
- 진행 중 현재 노드가 루트인 서브 트리의 크기가 구해지면, 현재 노드를 기준으로 자른다고 가정했을 때 생성되는 두 서브 트리 크기의 차이를 계산해서 가장 값이 작은 결과를 answer로 채택했다.
temp_answer = 101
def solution(n, wires):
answer = -1
arr = [[0] * (n+1) for _ in range(n+1)]
for i in range(len(wires)):
arr[wires[i][0]][wires[i][1]] = 1
arr[wires[i][1]][wires[i][0]] = 1
visit = [0] * (n+1)
visit[1] = 1
find(arr, visit, 1, n)
answer = temp_answer
return answer
def find(arr, visit, n, target):
temp = 1
global csb
for i in range(len(visit)):
if visit[i] == 0 and arr[n][i] == 1:
visit[i] = 1
temp += find(arr, visit, i, target)
temp_answer = min(temp_answer, abs(target - temp - temp))
return temp