Computer Science/Algorithm (8) 썸네일형 리스트형 <알고리즘> 퀵정렬은 병합정렬보다 항상 좋은 선택인가 1. 소개 최근에 필자는 하스켈이라는 언어를 공부하고 있다. 함수형 프로그래밍에 대한 깊은 이해를 위해서 겉핥기를 하고 있는데, 최근 정렬과 관련하여 궁금한 점이 생겨서 이렇게 정리하게 되었다. 참고로 이 포스팅에서 하스켈에 대해 깊이 알 필요는 없으며 함수형 언어라고만 생각해도 이해하는 데에는 지장이 없다. Data.List는 리스트 정렬을 위한 sort 함수를 제공한다. 이 함수는 퀵정렬을 쓰지 않는다. 대신 병합 정렬이라는 알고리즘의 효율적인 구현을 사용한다. - WikibooksHaskell - 지금까지 공부하기로는 대부분의 언어에서 정렬 함수는 퀵정렬(Quick Sort)을 활용하고 있다고 배웠다. 심지어 같은 시간복잡도를 가지는 병합정렬에 비해 일반적으로 더 빠르며, 면접 준비에서도 그렇게 대.. <알고리즘> 퀵 소트 & 힙 소트 1. 퀵 소트와 힙 소트 * 퀵 소트 - 퀵 소트(Quick Sort)는 병합 정렬(Merge Sort)와 마찬가지로 분할 정복 알고리즘을 활용한다. 그러나 병합 정렬과 달리 배열을 비균등하게 분할하여 정렬을 수행한다. - 퀵 소트는 불안정 정렬에 속한다. - 퀵 소트는 어떤 과정으로 정렬을 하는 것일까. 오름차순 정렬을 한다고 가정하자. 먼저 배열 내의 요소를 하나 선택한다. 이는 기준이 되는 원소로 피벗(pivot)이라 칭한다. 피벗을 기준으로 피벗보다 작은 원소는 피벗의 왼쪽으로 옮겨지고, 큰 원소는 피벗의 오른쪽으로 옮긴다. - 위의 과정을 한 번 거친 후, 피벗을 제외하고 왼쪽 배열과 오른쪽 배열에 대해 각각 같은방식으로 정렬한다. 부분 배열이 더 이상 분리가 불가능할 때까지 반복한다. 그러면 .. <알고리즘> 삽입정렬과 병합정렬 1. 삽입정렬과 병합정렬 * 삽입 정렬(Insetion Sort) - 선택정렬과 버블정렬과 마찬가지로 제자리 정렬(in-place sorting) 알고리즘이다. - 삽입 정렬은 마치 카드게임에서 손 안의 패를 정렬하는 것과 같다. 카드를 새로 받으면 기존에 정렬시켜둔 카드 사이에 삽입시켜 정렬시킨다. 이에 따라 동일한 값에 대해 순서가 유지되는 안정정렬방식을 보장한다. - 삽입 정렬을 알아보기 위해 10 5 7 1 3 이라는 5개의 숫자를 오름차순으로 정렬시켜보자. - 삽입 정렬은 두 번째 값부터 정렬을 시작하며, 해당 값과 그 앞의 값들과만 비교한다. - 먼저 5와 10을 비교한다. 5가 더 작으므로 10을 뒤로 이동시키고 5를 그자리에 삽입한다. 5 > 10 7 1 3 5 10 7 1 3 - 다음은 .. <알고리즘> 버블정렬과 선택정렬 1. 버블 정렬 - 버블 정렬은 두 개의 인접한 데이터를 비교하면서 서로의 위치를 교환하며 정렬해나간다. - 임의의 숫자의 나열 7 5 6 8 1 3 을 보자. - 오름차순으로 나열하기 위해 버블정렬을 한다면 가장 먼저 7과 5가 비교된다. - 7 5 6 8 1 3 => 5 7 6 8 1 3 - 7이 더 크므로 5와 위치가 교환된다. 다음은 두 번째 위치값과 세 번째 위치값이 비교된다. - 5 7 6 8 1 3 => 5 6 7 8 1 3 - 7과 6중 7이 더 크므로 위치가 교환된다. - 마찬가지로 진행하면 세 번째와 네 번째, 네 번째와 다섯 번째, 다섯 번째와 여섯 번째를 비교하면 다음과 같이 교환된다. - 5 6 7 8 1 3 => 5 6 7 8 1 3 => 5 6 7 1 8 3 => 5 6 7 1.. <알고리즘> 재귀 알고리즘 (1) 1. 재귀 알고리즘의 기본 * 재귀란 - 재귀 : 어떤 사건에서 자기 자신을 포함하고 다시 자신을 사용하여 정의되는 것. * 팩토리얼 구현 - n! 정의 ① 0! = 1 ② n > 0 이면 n! = n x (n-1)! 이 경우 n이 0이 아닌 수일 경우 ②를 실행하고 이는 또 다시 그 보다 1작은 수의 ②를 시행함을 알 수 있다. def factorial(n: int) -> int : if n > 0: return n * factorial(n - 1) else: return 1 x = int(input()) print(factorial(x)) # 5 # 120 : 매개 변수 5를 먼저 받고, 5 * factorial(4)을 계산해야한다. 이 때 이 곱셈을 위해 factorial(4)를 호출한다. 차례로 .. <알고리즘> 검색 알고리즘(2) 1. 해시법 이번 장은 검색뿐 아니라 데이터의 추가·삭제도 효율적으로 수행할 수 있는 해시법을 알아보자. * 해시법 - 데이터를 저장할 위치인 인덱스를 새로 구하는 것이다. 이를 통해 원소의 검색과 추가·삭제를 효율적으로 수행한다. 위의 배열을 11로 나눈 나머지를 정리해보자. 위에서 나온 해시값을 인덱스로 새로 배열을 해보자. - 위를 해시테이블이라 하며 새로운 원소 37을 추가하더라도 다른원소의 이동이 없는 것을 알 수 있다. 이는 기존의 배열에서 37을 추가하려면 뒤의 원소들을 모두 한칸씩 옮겨야 했던 것보다 효율적임을 알 수 있다. - 해시함수 : 위와 같이 키를 해시값으로 변환하는 과정 - 버킷(bucket) : 해시테이블에서 만들어진 원소 * 해시충돌 - 위의 예시에서 33을 추가하려면 버킷[.. <알고리즘> 검색 알고리즘 (1) 1. 검색 알고리즘이란 * 검색 : 어떤 조건을 만족하는 데이터를 찾는 행위 - 검색과 키 ex) 전공이 경제학과인 학생을 찾아라. : 위 예시의 조건은 전공이라는 항목이다. 이렇게 조건에서 주목되는 것이 '키'이다. * 배열검색 - 선형검색 : 무작위로 늘어놓은 데이터의 집합에서 검색 수행 - 이진검색 : 일정한 규칙의 데이터 집합에서 빠른 검색 수행 - 해시법 : 추가와 삭제가 자주 일어나는 데이터의 집합에서 빠른 검색을 수행. 체인법과 오픈주소법이 있음. * 검색 알고리즘의 선택 - 단순히 검색만 잘되면 좋다고 생각한다면 계산시간이 짧은 검색 알고리즘을 선택할 수 있다. - but, 검색 뿐 아니라 데이터의 추가·삭제도 수행한다면 검색이외에 작업에 들어가는 비용을 종합적으로 평가해야한다. - 따라서.. <알고리즘> 알고리즘 기초 1. 알고리즘이란 * 기초용어 먼저 두 숫자중 더 큰 숫자를 구하는 간단한 프로그램을 구현해보자. a = int(input('첫 번째 숫자를 입력하세요. :')) b = int(input('두 번째 숫자를 입력하세요. :')) large = a if b > large : large = b print(f'더 큰 숫자는 {large}입니다.') # 첫 번째 숫자를 입력하세요. : 10 # 두 번째 숫자를 입력하세요. : 25 # 더 큰 숫자는 25입니다. - 순차구조 : 위와 같이 순서대로 처리되는 구조 - 복합문 : if문과 같이 복합적으로 이루어진 구문 - 대입문 : large = a 와 같은 단순한 구문 - 조건식 : if문 바로 뒤에 따라오는 조건 - 선택구조 : 조건식으로 평가된 결과에 따라 흐름이.. 이전 1 다음
