CS

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) 팩..

해시란?데이터를 저장할 인덱스를 간단한 연산을 통해 구하여 데이터의 추가, 검색, 삭제 등이 효율적으로 이루어질 수 있도록 하는 자료구조이다. 예를 들어, [1, 14, 5, 23, 25] 와 같은 데이터와 크기가 7인 해시테이블이 있을 때 다음과 같이 표현할 수 있다.이 때, 해시값은 키를 해시테이블의 크기(7)로 나눈 나머지이다.키11452325해시값10524이런 식으로 key mod 7을 연산하여 해시값을 구할 수 있고, 이렇게 도출된 해시값을 인덱스로 활용하여 해시테이블에 저장할 수 있다. (인덱스는 왼쪽에서부터 순서대로 0, 1, 2, 3, 4, 5, 6)14123 255  해시 충돌(collision)에 대하여그러나 특정 키들에 대한 해시 값이 겹치는 상황이 생길 수 있다.위의 예시에서 8이라..

이진 검색?이진 검색은 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다.위와 같은 배열에서 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..

collections 라이브러리?파이썬의 딕셔너리, 리스트, 집합, 튜플에 대한 대안을 제공하는 특수 컨테이너 데이터를 구현한 모듈이다.즉, 데이터 처리를 위한 유용한 객체를 담고 있는 라이브러리이다. deque란?deque는 collections 모듈에서 제공되는 자료형 중 하나로, double-ended queue의 약자이다.덱 이라고도 부른다.이름에서 드러나있듯이 deque는 양쪽 끝에서 빠른 삽입과 삭제가 가능하도록 설계된 자료 구조이다.이는 리스트에 비해 효율적으로 양쪽 끝에서의 삽입과 삭제를 처리할 수 있다.때문에 이는 스택과 큐의 연산을 모두 지원하는 자료구조라고 볼 수 있다. deque의 기능양방향 삽입 및 삭제- append(x): 오른쪽 끝에 요소 x를 추가한다.- appendleft(..

보호되어 있는 글입니다.

라이브러리프로그램 개발 시 활용할 수 있는 클래스와 인터페이스를 모아둔 것~.jar 파일 형식으로 표현됨라이브러리에는 클래스와 인터페이스의 바이트 코드 파일(~.class)들이 압축되어 있음특정 클래스와 인터페이스가 여러 응용 프로그램에서 쓰인다면 이를 모아서 라이브러리(jar)로 압축하여 사용라이브러리를 만드는 방법위와 같은 라이브러리를 만드는 과정1. 이클립스에서 module.info.java 파일을 포함하지 않은 새 프로젝트를 생성2. 프로젝트 안에 패키지를 생성3. 패키지에 넣고 싶은 클래스, 인터페이스 작성4. jar 파일을 저장할 dist 폴더를 프로젝트 내부에 생성5. my_lib 우클릭 → Export 클릭6. dist 폴더에 jar 파일 생성6. 해당 라이브러리를 사용할 Applicati..