Study Blog

버블 정렬이란?- 이웃한 두 원소의 대소 관계를 비교하고, 교환을 반복하는 알고리즘(=단순 교환 정렬)- 액체 속의 공기 방울이 가벼워서 위로 보글보글 올라오는 모습에 착안해서 붙인 이름 오름차순 정렬하는 버블 정렬의 첫 번째 패스 진행 과정은 다음과 같다.1) 오른쪽 끝에 있는 두 원소 9와 8에 주목한다.2) 9와 8의 위치를 교환한다.3) 다음 원소인 1과 8에 주목한다.4) 1과 8의 위치는 교환하지 않는다. 원소 수가 n인 배열에서 n - 1번 비교 & 교환을 하면 가장 작은 원소인 1이 맨 앞으로 이동한다. 이러한 과정을 패스라고 한다. 위와 같이 패스를 한 번 수행할 때마다 정렬할 대상은 1개씩 줄어든다. 그러므로 두 번째 패스의 비교 횟수는 첫 번째 패스보다 1번 적은 n - 2번이다. 패..

정렬이란? - 이름, 학번, 학점 등의 특정 키를 기준으로 대소 관계에 따라 데이터의 집합을 일정한 순서로 바꾸어서 늘어놓는 작업이다. - 값이 작은 데이터부터 앞쪽에 늘어놓는 것: 오름차순(ascending order) 예) a = [1, 2, 3, 4, 5] - 값이 큰 데이터부터 앞쪽에 늘어놓는 것: 내림차순(descending order) 예) a = [5, 4, 3, 2, 1] - 정렬 알고리즘은 시간 복잡도에 따라 성능이 좌우되고, 성능이 좋은 알고리즘일수록 구현 방법이 어려워진다. 정렬 알고리즘의 시간복잡도 - O(n²): 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬(최악 O(n²), 최선O(n log n)) - O(n log n): 병합 정렬, 퀵 정렬, 힙 정렬 - O(n): 도수 정렬..

8퀸 문제란? - 재귀 알고리즘을 설명할 때 자주 나오는 예제로, 19세기 수학자인 '카를 F. 가우스'가 오답을 발표한 것으로 유명. 8퀸 문제의 조건 - 8개의 퀸이 서로 공격하여 잡을 수 없도록 8 x 8 체스판에 배치하라. 이 문제는 총 92가지 해결 방법을 얻을 수 있고, 아래 그림은 92가지 해결 방법 중 한가지이다. 이 문제를 해결하는 데 사용하는 문제 풀이 방법은 분기작업(branching, 차례대로 가지가 뻗어 나가듯이 배치 조합을 열거하는 방법)과 분할 정복법(분할 해결법, divide and conquer, 큰 문제를 작은 문제로 분할하고, 작은 문제 풀이법을 결합하여 전체 풀이법을 얻는 방법)을 이용하여 해결할 수 있다. 한 가지 주의할 점은 문제를 분할할 때 작은 풀이법에서 원래의..

하노이의 탑이란? - 작은 원반이 위에, 큰 원반이 아래에 위치하는 규칙을 지키며 기둥 3개를 이용해서 원반을 옮김. 하노이의 탑 조건 (1) 크기가 모두 다른 원반이 첫 번째 기둥에 쌓여 있는 상태로 시작(작은 원반이 위에, 큰 원반이 아래에 위치) (2) 이 상태에서 모든 원반을 세 번째 기둥에 최소 횟수로 옮김 (3) 원반은 1개씩 옮길 수 있으며, 큰 원반은 작은 원반 위에 쌓을 수 없음 그룹으로 묶어서 옮기기 - 원반이 3개일 때 - 원반이 2개일 때 - 원반이 4개일 때 원반을 옮기는 과정을 코드로 구현 def move(no: int, x: int, y: int) -> None: # 원반 no개를 x기둥에서 y기둥으로 옮김 if no > 1: move(no - 1, x, 6 - x - y) p..

순수한 재귀란? - 재귀 호출을 여러 번 실행하는 함수 def recur(n: int) -> int: if n > 0: recur(n - 1) print(n) recur(n - 2) x = int(input("정숫값을 입력하세요.: ")) recur(x) 실행 결과 정숫값을 입력하세요.: 4 1 2 3 1 4 1 2 - 순수한 재귀는 위와 같이 실행 과정이 복잡. 매개변수를 4가 아닌 3이나 5라면 어떤 결과를 출력할 지 간단히는 알 수 없음. 하향식 분석과 상향식 분석 위 코드를 하향식 분석(Top-down)방법과 상향식 분석(Bottom-up)방법으로 분석해보자. recur(4)의 실행 과정은 다음과 같다. 1. recur(3)을 실행한다. 2. 4를 출력한다. 3. recur(2)를 실행한다. 위 ..