WEEK01 - 컴퓨팅사고로의 전환 1
1주차부터 4주차까지 총 4주간에는 코드의 성능과 효율을 생각하는 프로그래머로 거듭나기 위한 준비과정으로 알고리즘과 자료구조를 스스로 공부하고 백준 문제를 파이썬을 사용하여 풀면서 컴퓨터에게 일을 시키는 방법을 터득한다.
이번 1주차에는 '정수론, 배열, 문자열, 재귀함수, 정렬, 완전탐색, 시간복잡도' 와 관련된 내용들을 공부하고 다양한 문제를 풀어보았다. 그 중에서도 이해하는데 시간이 걸렸고 그만큼 성장할 수 있었던 '재귀함수'와 '완전탐색' 문제를 정리해보려 한다.
재귀함수 - 백준 9663 n-Queen
재귀함수는 일단 기본적으로 함수 안에서 자기 자신을 호출하는 방식으로 정의되는 함수를 의미한다. 예를들어 수학에서 1부터 N까지의 곱을 N!(N 팩토리얼)로 나타낸다면, 이는 N * (N-1)! 로 나타낼 수 있다. 이를 fact(N) 으로 함수를 정의한다면, 다음과 같은 코드로 정의할 수 있을 것이다.
def fact(N) :
if N == 0 : return 1 # 재귀함수는 반드시 종결조건을 만들어주어야한다. 그렇지 않으면 무한 루프에 빠질 수 있다.
return N * fact(N-1)재귀함수는 학교다닐때 수학시간에 배운 점화식과도 같다. 위의 팩토리얼은 아래와 같은 점화식으로도 표현 가능하다.
- n이 0보다 클 때
a(n) = n * a(n-1)
- n이 0인 경우
a(1) = 1학생때에는 점화식을 일반식으로 만들어야했지만 코딩할때에는 점화식을 잘 세워주기만 하면 계산은 컴퓨터가 다 해준다. 하지만 이 점화식을 잘 세우는것이 쉽지 않다.
재귀함수의 의미를 이해했다고 생각했지만 문제에 적용하려고하니 어떻게 적용해야할지 생각이 잘 나지 않았다. 특히 n-Queen 문제의 경우에 NxN 크기의 체스판에서 N개의 퀸이 서로를 공격할 수 없도록 배치하는 방법의 수를 구해야하는데, 어떻게해야 2차원의 체스판에서 퀸들이 서로의 위치를 파악하면서 자신의 위치를 찾아갈 수 있을지 감이 오지않아 결국 알고리즘 책을 보고 이해한 뒤에야 구현을 할 수 있었다.
구현한 코드와 설명은 아래와 같다.
# import
from sys import stdin
input = stdin.readline
# 가능한 퀸의 배치수 구하는 재귀함수 구현
def queen(i) :
# 체스판의 크기 n, 가능한 배치 수 cnt, 열(column)별로 퀸을 배치한 행(row)를 기록하는 배열 c_proc
# 대각선방향(우상향 ru, 우하향 rd)으로 배치가 가능한지를 체크하는 배열 is_chked_ru/rd
global n, cnt, c_proc, is_chked_rd, is_chked_ru
# n만큼 배치가 완료되면 cnt +1
if i == n :
cnt += 1
# 배치 중인 경우
else :
for j in range(n) :
# i열 j 행에 퀸을 놓으려 할때 해당 행에 퀸이 배치되어있진 않읂지, 대각선방향으로 배치 가능한지 확인, 불가능시 다음 j로 이동
if j in c_proc or is_chked_ru[n-j+i-1] == 1 or is_chked_rd[2 * (n-1) - j - i] == 1 : continue
# 배치가능할시 배열의 i열에 j행 입력 및 해당 대각선 방향 배치불가 표시
c_proc.append(j)
is_chked_ru[n-j+i-1] = 1
is_chked_rd[2 * (n-1) - j - i] = 1
# 다음 열 재귀호출
queen(i+1)
# i열 j행에 대한 확인 완료시 다음 행 확인 위해 리스트에서 pop 및 대각선방향 원복
c_proc.pop()
is_chked_ru[n-j+i-1] = 0
is_chked_rd[2 * (n-1) - j - i] = 0
n =int(input())
c_proc = []
is_chked_ru = [0] * (2 * n - 1)
is_chked_rd = [0] * (2 * n - 1)
cnt = 0
queen(0)
print(cnt)완전탐색 - 백준 10971 외판원순회2
완전탐색이란 가능한 모든 경우의 수를 탐색하는 것을 의미한다. 그 중에서도 외판원순회 문제는 굉장히 유명한 문제라고 한다.
완전탐색을 구현할 때 재귀함수가 잘 사용될 수 있는 것 같았다. 재귀함수를 먼저 공부하고 이해한 뒤에 이 문제를 접해서 어렵지 않게 해결할 수 있었던 것 같다.
# import
from sys import stdin
input = stdin.readline
# 0에서 출발, 모든 위치 순회 후 0으로 돌아오면 최소비용(mincost) 갱신하도록 재귀함수 구현
def salesman(v) :
# 합계 sum, 최소비용 mincost, 방문했는지 확인하는 비트마스크 is_visited
global sum, mincost, is_visited
# 0으로 돌아왔고 모든 장소를 방문했을 때 mincost 갱신 (아래에서 mincost보다 sum이 큰 경우엔 추가 진행되지 않도록 선조치했음)
if v == 0 and all(is_visited) :
mincost = sum
else :
for i in range(n) :
# i 위치가 이미 방문되었는지, v에서 i로 가는 비용이 0은 아닌지,
# v에서 i로 가는 비용을 더했을 때 기존의 최소비용보다 비싸지진 않는지 확인
if (is_visited[i] == 1) or (w[v][i] == 0) or ( mincost < sum + w[v][i] ) : continue
# 문제없으면 sum에 비용 추가 및 i 위치 방문표시
sum += w[v][i]
is_visited[i] = 1
# i위치 방문으로 후속 재귀호출
salesman(i)
# i위치 방문 끝난 후 원복
sum -= w[v][i]
is_visited[i] = 0
n = int(input())
w = [list(map(int,input().split())) for _ in range(n)]
is_visited = [0] * n
mincost = pow(10,10)
sum = 0
salesman(0)
print(mincost)
정리
n-Queen 문제에서 어려움을 겪으면서 앞으로의 문제 접근 방향에 대해 한가지 생각해볼 수 있었다.
문제를 뭉텅이로 해결하려고 하지 말고, 낮은 수준으로 잘게 쪼개면서 접근 할 것.
예를 들면, x,y 좌표가 있는 2차원 문제일 때 2차원으로 생각하면 접근하기가 어렵다. 따라서 x,y 따로 1차원으로 분리할 수 있을지 생각해볼 수 있다. n-Queen의 경우, 모든 행과 열에는 퀸을 하나만 놓을 수 있기에, 일단 열 방향으로 진행하면서 하나씩 퀸을 놓음으로써 '모든 열에는 하나씩만 놓을 수 있다'를 해결할 수 있다.
