Passwd

삽입 정렬 (Insertion Sort) 자료의 모든 요소를 이미 정렬된 부분과 비교하여, 자신의 위치를 찾아 삽입하는 방식의 정렬이다. 두 번째 자료부터 시작하여, 그 앞의 자료와 비교하여 삽입할 위치를 지정한 후, 삽입 위치 이후의 자료는 하나씩 뒤로 옮기고, 삽입 위치에 자료를 삽입하여 정렬한다. 아래의 그립으로 쉽게 이해할 수 있다. 계산 복잡도는 선택 정렬과 동일하게 $$ \mbox{O}(n^2) $$ 코드 코드로 표현하면 아래 함수와 같다. def insertion_sort(list): for i in range(1, len(list)): for j in range(0, i): if list[i] > list[j]: list.insert(j, list.pop(i)) return list 참고 ..

정렬 자료를 크기 순서에 맞춰 일렬로 나열하는 것 가나다 순 또는 알파벳 순으로 나열한 사전이 좋은 예시 중 하나다. 정렬 종류 선택 정렬 (Selection Sort) 삽입 정렬 (Insertion Sort) 병합 정렬 (Merge Sort) 퀵 정렬 (Quick Sort) 거품 정렬 (Bubble Sort) 선택 정렬 제자리 정렬 알고리즘의 하나 가장 작은 값을 선택하여 자리를 교체하는 방식을 반복하여 진행한다. 코드 def selection_sort(list): for i in range(0, len(list) - 1): for j in range(i + 1, len(list)): if list[i] > list[j]: list[i], list[j] = list[j], list[i] # swap r..

탐색 여러 개의 자료 중에서 원하는 것을 찾아내는 것 정렬 주어진 자료를 순서에 맞춰 나열하는 것 순차 탐색 sequential search 리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색한다. 선형 탐색(linear search)이라고도 부른다. 코드 def sequential(num, list): for i in range(0, len(list)): if num == list[i]: return i return -1 계산 복잡도는 최악의 경우 O(n)이다. 자료를 일일이 비교하지 않고 좀 더 효율적으로 탐색을 하기 위해서는 자료를 정렬할 필요성이 있다. 참고 문서 https://thebook.io/006935/part03/ch07/

하노이의 탑(Tower of Hanoi) 원반 옮기기 퍼즐 크기가 다른 원반 n개와 원반을 끼울 수 있는 기둥 3개가 존재한다. 어떻게 하면 원반 n개를 Start 기둥에서 Goal 기둥으로 옮길 수 있는가? 제약 사항은 아래와 같다. 원반은 한 번에 한 개 씩만 옮길 수 있다. 각 기둥 맨 위의 원반은 다른 기둥의 맨 위로만 움직일 수 있다. 옮기는 과정에서 큰 원반을 작은 원반 위에 올릴 수는 없다. 풀이 방법 - 원반이 한개인 경우 - 원반이 n개인 경우 즉, 원반이 1개일 때가 종료 조건인 재귀 함수로 하노이의 탑 알고리즘을 구현할 수 있다. 코드 구현 def hanoi(n, from_p, to_p, aux_p): # 매개변수 n은 원반 수, from_p는 출발 기둥, to_p는 도착 기둥, au..

최대공약수 최대공약수 Greatest Common Disiver, GCD 두 개 이상의 정수의 공통 약수 중 가장 큰 값 방법 1. 정수 중 작은 값부터 1씩 감소시키면서 약수인 값을 찾는다. 2. 유클리드 알고리즘 a와 b의 최대공약수는 b를 a로 나눈 나머지의 최대공약수와 같다. gcd(a, b) = gcd(b, a%b) 어떤 수와 0의 최대공약수는 자기 자신이다. gcd(n, 0) = n 두 번째 성질이 재귀 호출의 종료조건이 된다. 유클리드 알고리즘 코드 def gcd(a, b): if b == 0: return a return gcd(b, a % b) 피보나치 수열 Fibonacci numbers 제 1항을 0, 제 2항을 1로 두고, 그 이후의 항부터는 바로 앞의 두 수를 더한 수로 정의한다...

재귀 호출 recursion. 함수가 자기 자신을 다시 호출하는 것 계속 반복하다가 RecursionError가 발생하지 않도록 특정 조건이 되면 종료되도록 설계해야 한다. 이것을 종료조건이라고 한다. 종료조건이 없으면 Stack Overflow가 발생하기도 한다. return문을 이용해 종료조건의 결과값부터 반환된다. 재귀 호출을 이용한 팩토리얼 계산 일반적인 형태 def func(입력 값): if 입력 값이 충분히 작으면: # 종료 조건 return 결괏값 ... func(더 작은 입력 값) # 더 작은 값으로 자기 자신을 호출 ... return 결괏값 참고문서 https://thebook.io/006935/ https://dojang.io/mod/page/view.php?id=585

여러 사람의 이름이 저장된 리스트에서 동명이인의 이름 집합을 반환하는 문제이다. 집합; Set 리스트와 같이 정보를 여러 개 넣어서 보관하는 자료구조 같은 자료가 중복되어 저장되지 않고, 자료의 순서에 의미가 없다. 선언 및 사용 # 선언 s = set() # 값 추가 s.add(VAL) # 값 삭제 s.discard(VAL) # 집합 비우기 s.clear() # 집합의 길이 len(s) # 값의 존재 유무 확인 val in s # 값이 집합에 존재하면 True val not in s # 값이 집합에 없으면 True 자료의 순서에 의미가 없으므로 집합 {val1, val2}와 집합 {val2, val1}은 동일하다. + 두 개의 중첩 반복문 내에서 비교하는 알고리즘의 계산 복잡도는 n-1까지의 합과 같다..

과감하게 문제 풀이는 생략한다. 리스트(List) 정보 여러 개를 하나로 묶어 저장하고 관리하는 자료구조 중 하나 쉼표로 구분한 값을 대괄호로 묶어서 선언한다. 선언 및 접근 방법 # 선언 list_num = [17, 92, 18, 33, 58, 7, 33, 42] # n번째 값에 접근. 인덱스는 0부터 시작한다 list_num[n] # 리스트의 맨 끝값에 접근 list_nume[-1] 함수 # 리스트의 길이(자료 수) 반환 len{list_num) # 리스트의 끝에 값 추가 list_num.append(num) # 리스트의 특정 위치에 값 추가 list_num.insert(i, num) # i번째 위치의 값을 리스트에서 제거하면서 값 반환 # 위치를 지정하지 않으면 맨 끝 값 제거와 동시에 값 반환 l..

알고리즘 어떤 문제를 풀기 위한 절차나 방법 주어진 입력을 출력으로 만드는 과정을 구체적으로 명료하게 표현한 것 1부터 n까지의 합을 구하는 알고리즘 방법 1 값을 1씩 증가시키면서 덧셈 연산 방법 2 가우스 등차수열의 합 공식 활용 $$ S_n = \frac{n*(n+1)}{2} $$ 알고리즘 분석 주어진 문제를 푸는 여러 가지 방법 중 어떤 방법이 더 좋은지 판단할 때 필요하며, 분석에는 복잡한 수학 이론이 필요한 경우가 많다. 입력 크기가 알고리즘의 수행 성능에 영향을 미치는 경우가 많으므로, 입력 크기가 매우 큰 경우에 대해 따져보는 것이 중요하다. 계산 복잡도(Complexity) O() 표기법(Big O)을 가장 많이 사용한다. 알고리즘의 대략적인 성능을 표시하며 필요한 계산 횟수와 입력 크기..