교대최소제곱법
[코테준비] 순열, 조합, 백트래킹 본문
기본적으로 순열, 조합 문제는 DFS 재귀함수를 이용해서 해결
순열 조합 모두 "없으면 넣고 dfs()" 구조는 똑같지만
조합의 경우 start를 고려해줘야 하는 차이가 있었음
-> s에 넣고 빼고를 반복하면서 모든 경우의 수를 돌린다
+ 왜 백트래킹 문제인가?
s의 개수가 M이상이 되면 그 다음 경우의 수는 파악할 필요가 없기 때문에 백트래킹 문제인 것
순열
# 15649번
n,m = list(map(int,input().split()))
s = []
def dfs():
if len(s)==m:
print(' '.join(map(str,s)))
return
for i in range(1,n+1):
if i not in s:
s.append(i)
dfs()
s.pop()
dfs()
조합
# 15650번
n,m = list(map(int,input().split()))
s = []
def dfs(start):
if len(s)==m:
print(' '.join(map(str,s)))
return
for i in range(start,n+1):
if i not in s:
s.append(i)
dfs(i+1)
s.pop()
dfs(1)
+ 23.10.08
조합을 활용한 문제의 경우 재귀함수를 통해 표현할 수도 있다.
def wall(반복 횟수):
if 반복 횟수 == 3:
bfs() # 조합이 완성되면 계산 후 종료
return
for 로우 i in range(N):
for 컬럼 j in range(M):
if 맵[i][j] == 0:
맵[i][j] = 1
wall(반복 횟수 + 1) # 재귀함수를 통해 조합을 표현
맵[i][j] = 0
+ 23.10.11
삼성 코테는 조합 라이브러리 사용 가능하다 그냥 라이브러리 쓰자
from itertools import combinations
array = [2, 4, 6]
list(combinations(array, 2)) # [(2,4),(2,6),(4,6)]
'코딩테스트' 카테고리의 다른 글
[백준 파이썬 11404번 플로이드] 플로이드 워셜 알고리즘 (0) | 2023.09.12 |
---|---|
[코테준비] 메모리 초과 해결 (0) | 2023.09.11 |
[코테준비] 분할정복, DP, 그리디 (0) | 2023.09.09 |
[코테준비] 다익스트라 알고리즘, 벨만-포드 알고리즘 (0) | 2023.09.09 |
[코테준비] DFS (0) | 2023.09.09 |