파이썬72 알고리즘 - 재귀 알고리즘(3) 8퀸 문제 여기서 말하는 퀸은 체스 말 중 하나인 Queen입니다. 퀸은 체스판에서 가로, 세로, 대각선으로 움직일 수 있는데 8퀸 문제는 8개의 퀸이 서로 공격했을 때, 잡을 수 없게 배치하는 문제입니다. 8퀸 문제도 하노이 탑과 마찬가지로 경우를 나누어 생각해보겠습니다. 1. 열에서 겹치지 않게, 2. 행에서 겹치지 않게, 3. 대각선으로 겹치지 않게입니다. 1. 열에서 겹치지 않게 pos = [0] * 8 # 각 열에서 퀸의 위치를 출력, pos[index] = x 일 때, index는 현재 열, x는 행 def put() -> None: # 각 열에 배치한 퀸의 위치를 출력 for i in range(8): print(f'{pos[i]:2}', end='') print() def set(i: in.. 2020. 11. 19. 백준 - 17478번 문제 https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 코드 def first(cnt): if cnt > 1: first(cnt - 1) print('____' * (cnt - 1) + '"재귀함수가 뭔가요?"') print('____' * (cnt - 1) + '"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.') print('____' * (cnt - 1) + '마을 사람들은 모두 그 선인에게 수많은 질문을.. 2020. 11. 18. 백준 - 1914번 문제 https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 코드 def move(N, x, y): if N > 1: move(N-1, x, 6-x-y) print(str(x) + ' ' + str(y)) if N > 1: move(N-1, 6-x-y, y) N = int(input()) print(2 ** N - 1)# 횟수 if N 2020. 11. 18. 알고리즘 - 재귀 알고리즘(2) 재귀 알고리즘 중 대표적인 하노이 탑을 보겠습니다. 일단 3개의 원반을 1번 기둥에서 3번 기둥으로 옮긴다고 했을 때 순서는 1번 원반을 1기둥에서 3기둥으로 2번 원반을 1기둥에서 2기둥으로 1번 원반을 3기둥에서 2기둥으로 3번 원반을 1기둥에서 3기둥으로 1번 원반을 2기둥에서 1기둥으로 2번 원반을 2기둥에서 3기둥으로 1번 원반을 1기둥에서 3기둥으로 이렇게 총 7번 옮깁니다. 이걸 크게 3개로 묶어서 생각하면 1,2번 원반을 1기둥에서 2기둥으로 3번 원반을 1기둥에서 3기둥으로 1,2번 원반을 3기둥으로 옮기는 것으로 생각할 수 있습니다. 아래는 위 생각을 코드로 만든 것입니다. def move(no, x, y): if no > 1: move(no - 1, x, 6 - x - y) print.. 2020. 11. 18. 이전 1 2 3 4 5 6 7 ··· 18 다음
