![]()
8퀸 문제체스판에 각 8개의 퀸이 서로 공격하여 잡을 수 없도록 8 * 8 체스판에 배치하는 문제 위 조건을 만족하기 위해서는 아래의 규칙들을 만족해야 한다. 규칙1: 각 열에 퀸을 1개만 배치한다.규칙2: 각 행에 퀸을 1개만 배치한다. 그러나 이 규칙들만으로 답을 찾는 것은 쉽지 않다.따라서 이 때 분기 작업으로 문제를 해결해야 한다.분기 작업이란 가지가 뻗어 나가듯이 배치 조합을 열거하는 것을 의미한다. 이 때, 만약 i열의 j번째 행에 퀸이 놓여져 있다면, 배열 pos[i]를 j로 설정한다. # 각 열에 퀸을 1개 배치하는 조합을 재귀적으로 나열하기pos = [0] * 8def put() -> None: """각 열에 배치한 퀸의 위치를 출력""" for i in range(8): ..
![]()
하노이의 탑작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키면서 기둥 3개를 이용해서 원반을 옮기는 문제이다.원반이 n개인 하노이탑 문제는 원반이 n-1개인 하노이탑 문제를 사용하여 재귀적으로 풀이할 수 있다.원반이 3개인 하노이 탑은 위와 같다.그리고, 이 과정에서 작은 원반 2개를 묶어서 생각할 수 있는데, 이 처럼 원반이 n개인 하노이탑 문제를 재귀적으로 풀이할 수 있다. 구현(기둥이 3개일 때)# 하노이의 탑 구현하기def move(no: int, x: int, y: int) -> None: """원반 no개를 x 기둥에서 y 기둥으로 옮김""" if no > 1: move(no - 1, x, 6 - x - y) print(f'원반 [{no}]을(를) {x}..
![]()
참고 문헌https://www.easyspub.co.kr/20_Menu/BookView/381/PUB https://www.easyspub.co.kr/20_Menu/BookView/381/PUB www.easyspub.co.kr 재귀 알고리즘에 대하여어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의하는 것 예시) 팩토리얼 n!의 정의0! = 1n > 0이면 n! = n × (n - 1)!def factorial(n: int) -> int: if n > 0: return n * factorial(n - 1) else: return 1위 팩토리얼 구현에서 보면, 함수 정의 자체에서 다시 자기 자신을 불러와 함수를 정의하는 것을 확인할 수 있다.cf) 팩..
![]()
이진 검색?이진 검색은 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다.위와 같은 배열에서 89를 검색한다고 가정한다.이 배열의 가운데 값은 77이다.이 때 89는 77보다 크므로, 오름차순인 이 배열에서 89는 77보다 뒤에 있음을 확인할 수 있다.따라서 77 이전의 요소는 탐색할 필요가 없다.뒷 부분에서 가운데 값은 98이다.89는 98보다 작으므로, 98 뒷 요소는 탐색할 필요가 없다.다시, 중앙의 원소인 89에 주목한다.이는 키 값과 일치하므로, 검색을 종료한다. +) 89가 중앙 원소인 이유?89의 인덱스: 692의 인덱스: 789와 92의 중간 인덱스 계산: (6 + 7) // 2 = 6 과정을 좀 더 상세하게 보자.arr[mid] == key이면 검색이 성공한 것! arr[m..
![]()
선형 검색?선형의 배열에서 검색하는 경우, 원하는 키 값을 가진 원소를 찾을 때 까지 맨 앞부터 스캔하여 차례차례 검색하는 알고리즘이다. 아래와 같이 앞에서부터 값을 비교하면서 검색을 진행한다.이 때, 만약 2가 아니라 8을 검색하려고 하였다면 검색이 실패하게 된다. 선형 검색의 종료 조건은 다음과 같다.검색할 값과 일치하는 원소를 찾은 경우 (성공)검색할 값을 찾지 못하고 배열의 맨 끝에 도달한 경우 (실패) 선형 검색의 구현 with 파이썬def linearSearch(arr, key): i = 0 while True: if i == len(arr): return -1 if arr[i] == key: return i ..
![]()
DFS 알고리즘?그래프 탐색 알고리즘 중 하나로, 특정 정점에서 시작하여 도달 가능한 정점까지 최대한 깊게 탐색한 후, 더 이상 뻗어 나아갈 수 없을 때 다시 가장 최근의 갈림길로 되돌아와 다른 경로를 탐색하는 방식이다.이 알고리즘은 스택을 사용하여 구현할 수 있고, 재귀 호출을 통해서도 구현할 수 있다.이 알고리즘을 통해 그래프의 모든 정점을 방문할 수 있다. 파이썬을 이용한 구현# 그래프 클래스class Graph: def __init__(self, vertices): self.V = vertices # 정점의 수 self.graph = {v: [] for v in range(vertices)} # 간선 딕셔너리 self.time = 0 # 탐색 시간(dis..
