타겟 넘버
https://programmers.co.kr/learn/courses/30/lessons/43165
내 풀이 - 통과
def func(numbers, target, t):
if len(numbers) == 0:
if t == target:
return 1
return 0
ans = 0
ans += func(numbers[1:], target, t+numbers[0])
ans += func(numbers[1:], target, t-numbers[0])
return ans
def solution(numbers, target):
answer = 0
answer = func(numbers, target, 0)
return answernumbers 숫자들을 0 인덱스부터 하나씩
t 에 더하는 방법 & 빼는 방법 두가지의 경우로 재귀 돌림
네트워크
https://programmers.co.kr/learn/courses/30/lessons/43162
내 풀이 - 통과
visited = []
def func(dic, com, net):
global visited
if visited[com]:
return
visited[com] = 1
for i in range(len(net)):
if visited[net[i]] == 0:
func(dic, net[i], dic[net[i]])
def solution(n, computers):
global visited
answer = 0
visited = [0] * n
dic = {i:[] for i in range(n)}
for i in range(len(computers)):
for j in range(i+1, len(computers[i])):
if i != j and computers[i][j]:
dic[i].append(j)
dic[j].append(i)
for i in range(n):
if visited[i] == 0:
func(dic, i, dic[i])
answer += 1
return answer우선 dic 에 각 컴퓨터마다 연결되는 컴퓨터들 저장
0 ~ n-1 까지의 각 컴퓨터마다 재귀로 연결된 네트워크를 세줌
이 때, 이미 하나의 네트워크에 연결된 컴퓨터들은 visited 값을 1 로 설정
단어 변환
https://programmers.co.kr/learn/courses/30/lessons/43163
내 풀이 - 통과
def func(begin, target, words, cnt):
if begin == target:
return cnt
if len(words) == 0:
return 0
ans = float('inf')
for i in range(len(begin)):
for j in range(len(words)):
if begin[:i]+begin[i+1:] == words[j][:i]+words[j][i+1:]:
ans = min(ans, func(words[j], target, words[:j]+words[j+1:], cnt+1))
return ans
def solution(begin, target, words):
answer = 0
if target not in words:
return 0
answer = func(begin, target, words, 0)
if answer == float('inf'):
return 0
return answer우선 target 이 words 에 존재하지 않으면 return 0
재귀 돌려서 최솟값을 찾아줌
begin 의 각 문자들 하나씩 없앤 것과
words 값의 각 문자들 하나씩 없앤 것이 같은지 확인
=> 한 글자만 차이가 나는 문자는 다음 재귀로
사용한 단어도 words 에서 제외
여행경로
https://programmers.co.kr/learn/courses/30/lessons/43164
내 풀이 - 통과
def func(dic, now, path, length):
if length == 0:
return [path]
if len(dic[now]) == 0:
return []
ans = []
for i in range(len(dic[now])):
p = dic[now].pop(0)
ans += func(dic, p, path+[p], length-1)
dic[now].append(p)
return ans
def solution(tickets):
answer = []
dic = {}
for a, b in tickets:
if a in dic:
dic[a].append(b)
else:
dic[a] = [b]
if b not in dic:
dic[b] = []
answer = func(dic, "ICN", ["ICN"], len(tickets))
answer.sort()
return answer[0]dic 에 출발지를 기준으로 도착지들 모두 저장
재귀의 시작은 ICN 부터
지금 출발지와 연결된 도착지는 다음 재귀로 넘길 때 제거 하고 넘김
=> pop & append
모든 항공권을 사용해야 하므로 len(tickets)-1 로 0 이 되는지 확인
모든 경로들은 answer 에 저장해서
알파벳 순으로 정렬 후 가장 첫번째 값 return
마지막에 정렬하지 않고
dic 에 저장된 값들을 정렬해준 후, 재귀 돌려도 가능
