일단 아래 코드에서 "순열" 부터 먼저 짚고 가자!
arr = [] #순회대상이 되는 리스트
visited=[] #방문흔적을 기록할 체크리스트
result=[] #현재 순열을 담을 리스트
answer=[] #모든 순열을 담을 answer리스트
def dfs(L,r):
if L == r:
# answer.append(result) //틀림
answer.append(result[:])
return #리턴문이 있어도 되고, 없어도 된다. 재귀함수의 경우 조건이 만족되면, 호출된 스택은 종료된다.
else:
for i in range(len(arr)):
if visited[i] == 0:
result[L] = arr[i]
visited[i] =1
dfs(L + 1,r)
visited[i] = 0
def solution(n,r):
global arr, visited,result
arr=[i+1 for i in range(n)]
visited = [0] * len(arr)
result=[0]*r
dfs(0,r)
return answer
print(solution(3,2))
# 실행결과
# >>> [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
일단 n과 r은 n은 1부터 n까지의 숫자를 의미하며, r은 뽑는 개수의 수를 의미한다.
n이 주어지면 1부터 n까지의 숫자가 들어간 배열 arr를 만든다.
예를 들어 n이 3이라면 1부터 3까지의 숫자가 들어간 arr = [1, 2, 3]이 만들어진다.
또한 숫자를 뽑아서 담기 위한 바구니인 result 리스트를 만든다.
n이 3이고, r이 2라면 3개중에서 2개를 뽑을 것이므로 result의 크기는 result=[0]*2가 된다.
visited는 일종의 checklist로써 방문 흔적을 남기기 위한 방명록과 같다.
visited[i]=0이면 " i인덱스에 해당하는 arr의 요소"를 아직 방문하지 않았다는 것을 의미하며,
visited[i]=1이면 "i인덱스에 해당하는 arr의 요소"를 방문했다는 것을 의미한다.
다만, DFS의 경우 foward와 back을 하기 때문에 back할때는 해당 방문했던 곳을
다시 visitied[i] =0으로 만들어준다.
아래의 보충자료를 보자
선 위에 있는 0, 1, 2는 순회대상이 되는 arr의 index를 의미함과 동시에 이미 "해당 index에 해당하는 arr의 요소를 이미 방문했음"을 의미한다. 방문을 했다면, visited[i] = 1이 된다.
결과적으로 if조건문에서 visited[i] =1인 경우에는 조건탈락이므로 중복되지 않게 arr의 요소를 탐색하게 된다.
가장 좌측 하단의 경우 위에서 아래로 내려올 때 arr[0] 인덱스는 이미 방문했기 때문에 visited[0]=1이 되므로 DFS(2)는 호출되지 않는다.
그러면 다시 back을 해서 DFS(1)로 오게 되고, 다시 arr의 index가 1인 곳을 방문하게 된다. 그리고 arr[1]의 요소를 result [1]에 대입하게 된다.
L=2에 도달했을 때 result에는 [1, 2]가 담기게 되고, 이것을 깊은 복사(deep copy)를 통해 answer리스트에 담는다.
추가 적으로 주의할 점
▶ 재귀함수의 "종료조건"에서 return 문이 있어도 되고, 없어도 된다. 재귀 함수는 호출될 때마다
새로운 호출 스택을 생성하며, 재귀 함수 내에서 base case를 만나면(탐색이 더 이상 가능하지 않을 때)
해당 호출 스택은 종료되고, 호출된 함수로 되돌아가며, 이를 반복하여 최종적으로
main(여기서는 solution함수)함수로 돌아와 프로그램이 종료된다.
따라서, return 문이 없더라도 재귀 함수는 정상적으로 종료될 수 있다.
▶ answer.append(result)이 틀리고, answer.append(result[:])가 올바른 코드인 이유
→answer.append(result)에서 result는 기존의 result리스트를 가리키는 포인터이며,
→answer.append(result)는 answer리스트에 result리스트를 추가하는 것이다.
▶ answer.append(result[:])에서 result[:]는 result리스트의 복사본을 생성한 것이다.
이 경우 answer.append(result[:])는 answer리스트에 result리스트의 복사본을 추가하는 것이기 때문에
result리스트가 변경되더라도 answer리스트는 영향을 받지 않는다.
▶ 보충자료의 하단에 그림을 보면, result에는 주소인 100번지가 저장되어 있고, 동일하게 [ 1, 3]을
가리키고 있다. 따라서 기존에 저장되어 있던 [1, 2]가 [1, 3]으로 바뀌게 되는 bad 케이스가 발생할 수 있다.
너무 짧게 설명한 것 같아서 아래의 링크를 첨부한다.
https://crackerjacks.tistory.com/14
파이썬 (Python) - 깊은 복사 (Deep Copy)
파이썬 (Python) - 깊은 복사 (Deep Copy) 알고리즘을 풀다 보면 원본배열의 보존을 위해 배열을 복사할 필요를 느낄때가 많다. 객체를 무작정 복사해서 사용하면 원본 객체가 핸들링되어 데이터가 변
crackerjacks.tistory.com
이제 "피로도"를 설명하겠다.
#for문 안에 재귀함수가 있는 경우
#answer,N 전역변수, visited 전역배열
answer = 0
N = 0
visited = []
def dfs(k, cnt, dungeons):
#2단계: 함수 안에 있는 지역변수answer를 전역변수화 시킨다. answer는 전역변수이다.
global answer
# print("k=", k, "cnt=", cnt, dungeons)
if cnt > answer: # 1단계:비교 등호를 사용하면 인터프리터가 answer가 지역변수로 간주해버린다. 그런데 answer에 할당된 값이 없다.
answer = cnt
for j in range(N):
# print(k, dungeons[j][1], cnt)
if k >= dungeons[j][0] and visited[j]==0:
visited[j] = 1 #방문하려는 곳은 1로 체크
dfs(k - dungeons[j][1], cnt + 1, dungeons)
visited[j] = 0 #back하려는 경우에는 0로 되돌려 놓는다.
def solution(k, dungeons):
global N, visited
N = len(dungeons)
visited = [0] * N
dfs(k, 0, dungeons)
return answer
k = 80
dungeons = [[80,20],[50,40],[30,10]]
print(solution(k, dungeons))▶ def(k, cnt, dungeons)안에 있는 answer변수에 global이라는 키워드를 붙여서,
함수 내에 있는 answer지역변수를 전역변수로 바꾸어준다.
▶ 이렇게 해야 def함수가 재귀호출이 반복적으로 일어나더라도, 값이 초기화 되는 일 없이 cnt값이 지속적으로
반영된다.
▶ N, visited 모두 전역변수로 만들어서 solution함수와 def함수에서 모두 사용될 수 있도록 만든다.
▶ 여기서 중요한 점은 visited와 같은 checklist와 더불어서 k>=dungeons[j][0]이 추가 되었다는 점이다!!
즉 조건이 더욱 엄격해졌다.
▶ 즉 visited 즉 checklist를 통한 중복방문 방지 + 추가 조건(k>=dungeons[j][0])이 되었다.
▶ dungeons= [ [80, 20],[50, 40],[30, 10] ]
▶ 아래의 두 가지만 기억하자!!
▶ dungeons[j][0]은 비교대상, dungeons[j][1]은 실제로 빼는 값이다.
소거되는 logic은 두 가지이다.
if k >= dungeons[j][0] and visited[j]==0:의 반대 표현인
"이미 방문"을 했거나(visited[j]==1) 또는(or) k< dungeons[j][0]이 되어 "탈락"되는 경우이다.
가장 좌측을 보면 arr의 0번 index는 이미 방문했으므로 다시 arr의 0번 index를 방문하지 않는다.
def호출X
그리고 가운데 부분의 경우 k= 40 < duns[0][0] =80 이므로 "탈락"이다. 따라서 def는 호출X
최종적으로 cnt의 최대값은 3이 되므로 answer=3이 정답이 된다.
다시 한번 강조한다.
dungeons[j][0]은 비교대상, dungeons[j][1]은 실제로 빼는 값이다.
최종적으로 요약해보면,
1. 순열을 이용한 중복 방문 방지
2. if문에서 k>=dungeons[j][0]의 추가 조건을 이용한 탈락
3. global 키워드를 사용한 함수내에서의 전역변수 사용
4. return문이 없어도 base case(더 이상 탐색할수 없는 상태)를 만나면 재귀함수는 종료
글쓴이도 이해하는데 오래걸렸다. 위에 있는 보충자료를 펜으로 그려보길 바란다.
print문을 몇번을 찍어보았는데도, 이해가 되지 않았다. 손으로 그려보길 추천한다.
반복문인 for문과 Permitation을 이용한 경우
from itertools import permutations
def solution(k, dungeons):
answer = 0
for p in permutations(dungeons, len(dungeons)):
tmp = k
cnt = 0
for need, spend in p:
if tmp >= need:
tmp -= spend
cnt += 1
answer = max(answer, cnt)
return answer
결과값(return)이 없는 함수 -존재가능
def add(a,b);
print("%d, %d의 합은 %d입니다." %(a, b, a+b))'프로그래머스(파이썬) > LV.2(파이썬)' 카테고리의 다른 글
| 주차요금계산 카카오→split(), 1차원 리스트 여러 개 변수로 받기 (0) | 2023.01.03 |
|---|---|
| [3차] 압축 → 전진 + 후진, 슬라이싱 "첫자리" 갱신 (0) | 2023.01.03 |
| H-index → 논문을 적게 발표했지만, 인용된 수가 많은 good 케이스 (0) | 2023.01.03 |
| 더 맵게 → heap★★ (0) | 2023.01.02 |
| 귤 고르기→ Counter() 함수, most_common() (0) | 2023.01.02 |