반복과 재귀
-
해결할 문제를 고려해서 반복이나 재귀의 방법을 선택
-
일반적으로, 재귀적 알고리즘은 반복 알고리즘보다 더 많은 메모리와 연산을 필요로 함
-
입력 값 n이 커질수록 재귀 알고리즘은 반복에 비해 비효율적일 수 있다
완전 검색
- 많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것
- 전형적으로 순열(permutation), 조합(combination), 그리고 부분집합(subsets)과 같은 조합적 문제들과 연관됨
Brute-force 탐색
- 대부분의 문제에 적용 가능
- 상대적으로 빠른 시간에 설계 가능
- 자료의 크기가 작은 경우 유용
sequential search
- 자료들서 원하는 값을 찾기 위해 첫 번째 자료부터 탐색
순열(Permutation)
- 서로 다른 것들 중 몇개를 뽑아 나열
- N개의 요소들에 대해서 N!개의 순열들이 존재함
-> 입력이 크면 시간복잡도가 폭발적으로 증가
단순하게 순열 생성
- 동일한 숫자가 포함되지 않는 순열을 아래와 같이 구현 가능
재귀호출을 통한 순열 생성
def perm(i,k):
'''
param
i : 값을 결정할 인덱스
k : 결정할 개수
'''
if i == k :
print(*p)
else:
for j in range(i,k): # 자신부터 오른쪽 원소들과 교환
p[i], p[j] = p[j], p[i]
perm(i+1,k)
p[i], p[j] = p[j], p[i]
p = [1,2,3]
perm(0,3)
'''
결과
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
'''- 사전순으로 출력하는 버전
def perm(i,k):
if i == k:
print(*p)
else:
for j in range(k): # 첨부터 끝까지
if used[j] == 0: # 사용하지 않은 자리면
p[i] = A[j]
used[j] = 1 # 사용
perm(i+1, k)
used[j] = 0 # j번 자리 숫자를 다른 자리에서 쓸 수 있게
A = [1,2,3]
p = [0] * 3
used = [0]*3
perm(0,3)
'''
결과
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
'''