KoreanFoodie's Study

Heap sort python code implementation Heap sort 파이썬 코드를 작성해 보자. 힙 정렬(Heap Sort) 힙은 2진 트리인데, Min-heap(최소값이 루트 노드에 있음. 부모 노드가 자식 노드보다 작아야 함.)과 Max-heap(최대값이 루트 노드에 있음. 부모 노드가 자식 노드보다 커야 함.) 위키 피디아의 설명을 참고해 보자. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다. 가장 큰 수(루트에 위치)..

Quick sort python code implementation 퀵소트(Quicksort)를 파이썬 코드로 구현해 보자. 퀵 소트(Quick sort) 퀵 소트는 배열을 파티션을 이용해서 반으로 나누고, 다시 이전 배열을 반으로 나눈 방식을 재귀적으로 적용한다. 파티션은 일반적으로, 제일 끝 배열의 원소를 pivot으로 잡고, 해당 pivot값보다 작은 값은 왼쪽으로 몰아 넣고, 큰 값은 오른쪽으로 몰아넣는다. 이 과정을 재귀적으로 반복하면, 각 파티션마다 O(n) 타임이 걸리고, 총 파티션은 평균적으로 O(logn) 타임이 걸리므로, 총 시간은 O(nlogn)이 걸리는 것을 알 수 있다. 위키피디아의 설명을 참고해 보자. 파티션은 다음과 같이 작동한다. 수도 코드를 살펴보자. function par..

Merge sort python code implementation merge sort 파이썬 코드를 작성해 보자. 병합 정렬(Merge Sort) 위키피디아의 설명을 참고해 보자. 병합 정렬은 다음과 같이 작동한다. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 병합 정렬의 핵심은, 문제를 푸는 방법론을 사이즈를 반으로 쪼갠 녀석에 적용해서 정렬을 완료한 후, 정렬이 완료된 반쪽짜리 2개를 다시 합침으로써 정렬을 마친다는 것이다. 즉, merge_sort함수는 2개의 merge..

Bubble sort python code implementation. 버블 정렬을 파이썬 코드로 구현해 보자. 버블 정렬 (Bubble Sort) 위키피디아의 정의를 참고해 보자. : 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 예시를 통해 버블 정렬이 어떻게 동작하는지 알아보자. 버블 정렬은 매우 단순한데, 그냥 처음부터 2개씩 짝을 지어 값을 비교한 후, 작은 녀석은 앞으로, 큰 녀석은 뒤로 보내면 된다. (55, 07)은 (07, 55)로, (55, 78)은 그대로, (78, 12)는 (12..

Insertion sort python code implemetation 삽입 정렬을 파이썬 코드로 구현해 보자. 삽입 정렬 (Insertion sort) 위키피디아에 나온 정의를 참고해 보자. 선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n^2) 만큼의 시간이 걸린다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이..

selection sort python code 선택정렬을 파이썬 코드로 구현해 보자. 선택정렬(Selection sort 기본 설명) 위키피디아에 있는 정의를 참고해 보자. 선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n^2) 만큼의 시간이 걸린다. 선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 그림으로 표..

These are OCaml Library module "List" implementation. Useful when we handle list data type in OCaml. let rec length l = match l with | [] -> 0 | _::t -> 1 + length t (* tail-recursive version of length *) let length' l = let rec f l result = match l with | [] -> result | _::t -> f t (result+1) in f l 0 let hd l = match l with | [] -> raise (Failure "hd") | h::_ -> h let tl l = match l with | [] ..

예제들을 OCaml로 구현해 보자. OCaml quicksort code (* pick the first element as a pivot *) (* ascending order *) let rec qsort comp l = match l with | [] -> [] | p::t -> let (l1,l2) = List.partition (fun x -> comp x p print_int x;print_string " ") l; print_newline(); print_endline "result of qsort : "; List.iter (fun x -> print_int x;print_string " ") (qsort compare l); print_newline() OCaml Stack code 모듈..

이전 게시글에 이어 OCaml에서 꼭 알아야 할 중요한 개념들에 대해 더 알아보도록 하자. 주요 개념들 : Pair, Tuple, List, Currying, Inductive type, match-with 구문, Polymorphic type, try-with-raise, module system, reference. OCaml Pair Pair는 두 개의 값을 한번에 묶는 데 활용된다. 정의는 (x, y)같은 식으로 할 수 있으며, 타입은 a * b형태로 표기된다. Pair의 각 항을 조회하는데 fst와 snd함수를 사용할 수 있다. let p:(int * string) = (1, "a") let i = fst p (* int, 1 *) let s = snd p (* string, "a" *) let..

OCaml 언어 : Ocaml은 여러가지 사용법을 가지는 상위 (high-level)언어이다. 절차형(imperative), 객체지향(object oriented), 함수형(functional) 등의 프로그래밍을 모두 지원한다. Java처럼, 자동으로 메모리를 관리해 주는 Garbage collector가 존재한다. 타입 시스템이 내장되어 매우 안정적으로 사용할 수 있다. 절차형 VS 값 중심형 절차형 언어는 기게에게 순서대로 명령을 전달한다. 함수형 언어의 경우, 값 중심으로 기계에게 식의 계산을 시키는 식으로 동작한다. OCaml 기초 - 값 정의 정수 값 let i = 1 문자열 값 let s = "hello world" Boolean 값 let b = true unit let _ = print_e..