😂1주차 알고리즘😂
오늘 개발일지는 1주차에 배웠던 알고리즘에 대해 작성하려 한다.
- 정렬
- 백트래킹
- 재귀함수
정렬은 이미 한번 정리한 적이 있기 때문에 링크로 남긴다.
1. 재귀함수
재귀 함수에는 순열과 조합을 구할 때도 활용 가능하며, 이분 탐색,DFS 등 다양하게 사용되고 있다.
나는 재귀함수의 개념은 알았지만 활용하고 연계된 알고리즘을 잘 몰랐어서 그와 관련된 내용을 정리할 예정이다.
1-1. 팩토리얼
재귀함수의 대표적인 예이다. 백준 링크
간단하게 코드를 살펴보자면,
def factorial(n):
if n==0:
return 1
return n*factorial(n-1)
n=int(input())
print(factorial(n))정의된 factorial 함수 안에 factorial이 한번 더 사용된 것을 볼 수 있다. 이게 바로 재귀함수 이다.
1-2. 하노이 탑
재귀함수에서 기본적으로 알아야할 예시 중 하나이다. 백준 링크
import sys
def hanoi(n,x,y):
if n>1:
hanoi(n-1,x,6-x-y)
print(f'{x} {y}')
if n>1:
hanoi(n-1,6-x-y,y)
n=int(sys.stdin.readline())
print(2**n-1)
if n<=20:
hanoi(n,1,3)하노이 이해하는 데도 오랜 시간이 걸렸다... 여기서 n은 원반의 갯수, x는 현재 막대기, y는 최종 목표하는 막대기이다.
1-3. N-Queen
재귀함수에서 가장 어려운 문제로 꼽히는 문제 중 하나이다. 백준 링크
import sys
n=int(sys.stdin.readline())
cnt=0
pos= [0]*n #각 열에 배치한 퀸의 위치
flag_a = [False]*n #각 행에 퀸을 배치했는지 체크
flag_b = [False]*(n*2-1) #대각선 방향으로 퀸을 배치했는지 체크
flag_c = [False]*(n*2-1) #대각선 방향으로 퀸을 배치했는지 체크
list1=[]
def set(i):
for j in range(n):
cnt=0
if not flag_a[j] and not flag_b[i+j] and not flag_c[i-j+(n-1)]:
pos[i]=j
if i==n-1:
#put()
cnt+=1
list1.append(cnt)
else:
flag_a[j]= flag_b[i+j] = flag_c[i-j+(n-1)] = True
set(i+1)
flag_a[j] = flag_b[i+j] = flag_c[i-j+(n-1)]=False
set(0)
print(sum(list1))
스스로 해결은 절대 못했고 "Do it 파이썬으로 시작하는 알고리즘" 책을 참고해서 코드를 작성하였다.
1-4. 1,2,3 더하기
매주마다 보는 알고리즘 테스트에서 나왔던 재귀 함수문제이다. 재귀를 정확하게 이해하지 못하고 응용하지 못한 나는 당연하게도 못풀었다...
백준 링크
import sys
def plus(n):
if n==1:
return 1
if n==2:
return 2
if n==3:
return 4
return plus(n-3)+ plus(n-2)+ plus(n-1)
T=int(sys.stdin.readline())
result=[]
for i in range(T):
n=int(sys.stdin.readline())
result.append(plus(n))
for j in result:
print(j)
이 방법은 같은 반 팀원이 알려준 방법이다. Top-down 방식으로 완벽한 재귀함수 방식으로 문제를 풀었다. 계단 오르기 문제랑 같은 방식을 사용한다고 한다.
2. 백트래킹
-
해를 찾아가는 도중 결과 값이 도출될 것 같지 않으면 과정을 중단하고 되돌아 가는 과정
-
완전 탐색 방법 중 하나인 깊이 우선 탐색(DFS)를 진행하면서 조건을 확인하고 해당 노드가 유망하지 않으면 탐색하지 않는 것이다.
-> 반복문의 횟수를 줄일 수 있으므로 효율적이다. -
백트래킹 기법의 유망성 판단
- 유망하다(promising) : 해가 될 가능성이 있으면 유망하다라고 한다.
- 가지치기(pruning) : 유망하지 않은 노드에 가지 않는 것을 말한다.
2-1. N-Queen
앞서 나왔던 N-Queen이다. 이 문제는 백트래킹 알고리즘에 해당한다.
2-2. N과 M
이 문제는 백트래킹의 기본 문제에 해당한다. 기본적인 구조를 알면 쉽게 풀 수 있는 문제이다. 하지만 나는 못풀었지..
특히 백트래킹과 재귀를 정확히 하고 싶다면 N과M 시리즈를 풀어봐야 한다.
백준 링크
import sys
n,m=map(int,sys.stdin.readline().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()2-3. 부분 수열의 합
이 문제도 백트래킹이다. 매주마다 보는 알고리즘 테스트에서 나왔던 문제인데 브루트포스 알고리즘이 사용된다고 한다. 하지만 나는 백트래킹으로 공부했지
import sys
n,s = map(int,sys.stdin.readline().split())
list1=list(map(int,sys.stdin.readline().split()))
cnt=0
def dfs(idx,result):
global cnt
if sum(result)==s and len(result)!=0:
cnt+=1
for i in range(idx,n):
result.append(list1[i])
dfs(i+1,result)
result.pop()
dfs(0,[])
print(cnt)N과 M에서 쓰인 알고리즘과 거의 유사하지만 정확히 이해하지 않으면 응용해서 쓸 수 없는 문제이다.
3. 결론‼
- 재귀함수는 자기 자신을 호출하는 함수이다.
- 모든 재귀함수는 이론적으로 For문이나 While문으로 구현이 가능하나 사용자의 가독성을 위해서 사용한다.
- 백트래킹은 재귀 알고리즘의 일종으로 반복의 횟수를 줄여 효율적으로 만든 알고리즘이다.
Ref)
https://chanhuiseok.github.io/posts/algo-23/
https://velog.io/@newon-seoul/%EB%AC%B8%EA%B3%BC%EC%83%9D%EC%9D%B4-%EC%A0%81%EC%96%B4%EB%B3%B4%EB%8A%94-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-%EC%9E%AC%EA%B7%80%EC%99%80-DFS-%EB%A5%BC-%EA%B3%81%EB%93%A4%EC%9D%B8
