programmer life guidance 101

> 힙 정렬 Heap Sort 최악의 경우 시간복잡도 O(nlogn) Sorts in place - 추가 배열 불필요 merge sort도 최악의 경우 O(nlogn)이었지만, 추가 배열이 필요햇음 이진 힙(binary heap) 자료 구조를 사용 O(nlogn)의 시간복잡도를 가지면서 merge sort처럼 추가적인 배열이 필요하지 않기 때문에 좋은 정렬 알고리즘 중 하나이다. Heap의 정의 Heap은 완전 이진 트리(complete binary tree)이면서 Heap property를 만족해야한다. 동일한 데이터를 가진 서로 다른 힙이 존재할 수 있다. 즉, 힙은 유일하지 않다.(같은 원소들을 가지는데 다른 위치에 가진다.) 힙은 일차원 배열로 표현가능하다. `A[1...n]1 루트 노드 : A[..

Quick Sort 정렬할 배열이 주어진다. 마지막 수를 기준(pivot)으로 삼는다. 기준(15)보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치(분할)한다. 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다(정렬 완료) - Algorithm 마찬가지로 quicksort도 recursion이므로 매개변수를 명시화한다. quickSort(A[], p, r) { base case; // p >= r일 때, 정렬할 데이터가 0개 또는 1개이므로 할 일 없음 if(p= x j

> 분할정복법 Divide and Conquer merge sort와 quick sort는 분할 정복 알고리즘을 사용한다 기본적으로 recursion을 사용하여 문제를 해결하는 기법이다. 아래의 세가지 단계를 거쳐서 문제를 해결한다. 분할 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 크기는 작은 사이즈의 문제지만, 문제 자체는 전체 문제와 동일한 문제들 정복 각각의 작은 문제를 순환적으로 해결 합병 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구합 Merge Sort divide : 데이터가 저장된 배열을 절반으로 나눔 recursively sort : 각각을 순환적으로 정렬 merge : 정렬된 두 개의 배열을 합쳐 전체를 정렬 주어진 배열을 계속해서 반으로 나누다 보면 결..

> 기본 정렬 알고리즘 selection, bubble, insertion sort simple, slow Bubble sort (버블정렬) Insertion sort (삽입정렬) Selection sort (선택정렬) fast Quick sort (퀵 정렬) Merge sort (병합정렬) Heap sort (힙정렬) O(n) Redix sort Selection Sort 각 루프마다 최대 원소를 찾는다 최대 원소와 맨 오른쪽 원소를 교환한다 맨 오른쪽 원소를 제외한다. 하나의 원소만 남을 때까지 위의 루프를 반복한다. pseudo code selectionSort(A[], n){ for last input[max]) max = j; } tmp = input[i]; input[i] = input[max..

> 큐(QUEUE)란? 큐의 개념 Queue의 사전적의미는 1.(무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미한다. 따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 살마의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First in First out) 방식의 자료구조를 말한다. 큐의 특징 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다. 이 때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다. 이 때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)..

> 스택(STACK)이란? 스택의 개념 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 스택의 특징 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. top에는 가장 위에있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다. 스택에서 top을 통해 삽입하는 연산을 push, top을 통한 삭제하는 연산을 pop이라고 한다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저..

KMP KMP알고리즘에 대해 간략히 설명 하자면, 지금까지 알려진 문자열 알고리즘 가운데 가장 최저의 시간복잡도를 가진 알고리즘이다. 일단, KMP알고리즘의 시간복잡도는 O(N+K) 여기서 N과 K는 비교할 문자열의 길이이다. 매칭을 하려면 최소한 비교대상과 타겟의 문자열을 한번씩 읽어봐야 할테니, 가장 최적의 시간복잡도이다. 알고리즘에 대한 기본적인 설명과 이해는 아래의 링크를 통해서 천천히 반복적으로 학습하는 것을 추천하고, 본인 역시 아래의 링크를 참고해서 학습한 내용에 이해에 필요한 설명을 추가하려 포스팅하려고 한다. https://m.blog.naver.com/kks227/220917078260 [ 백준 1786 ] 찾기(JAVA) 문제 링크: https://www.acmicpc.net/prob..

> 알고리즘의 분석 알고리즘의 자원(resource) 사용량을 분석 자원이란 실행시간, 메모리, 저장장치, 통신 등 여기서는 실행시간의 분석에 대해서 다룬다. 시간복잡도 실행시간은 실행환경에 따라 달라짐 하드웨어, 운영체제, 언어, 컴파일러 등 실행시간을 측정하는 대신 연산의 실행 횟수를 카운트 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 데이터의 크기가 같더라고 실제 데이터에 따라서 달라짐 최악의 경우 시간복잡도(worst-case analysis) 평균 시간복잡도(average-case analysis) 점근적(Asymptotic) 분석 점근적 표기법을 사용 데이터의 개수 n → ∞ 일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법 Θ-표기, Ο-표기 등을 사용..

> Recursion의 기본 개념과 예제3 Desigining Recursion 순환적 알고리즘의 설계 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다 모든 case는 결국 base case로 수렴해야 한다 ex - 가장 단순한 경우 if(...){ // basecase } else { // recursion } 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라!! 순차탐색 이 함수의 미션은 data[0]에서 data[n-1]사이에서 target을 검색하는 것이다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉, 0은 암시적 매개변수이다. int search(int[] data, int n, int target){ for(int..

> Recursion의 기본 개념과 예제2 Recursive Thinking - 순환적 사고 Recursion은 수학함수 계산에만 유용한가? 수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다. 문자열의 길이 계산 순서대로 앞에서부터 하나씩 카운트 또는, 총 문자열의 길이는 첫 번째 문자를 뺀, 전체 문자열의 길이 +1(첫번째 문자)이다. if the string is empty // base case return 0; else return 1 plus the length of the string that excludes the first character; public static int length(String str){ if(str.equals("")) return 0; el..

> Recursion의 기본 개념과 예제 Recursion 우리말로 순환 또는 재귀함수라고 한다. 즉, 자기 자신을 호출하는 함수, 메소드를 뜻한다. void func(){ ... func(); ... } ex1 - 무한루프 public class Code01{ public static void main(String[] args){ func(); } private static void func(){ System.out.println("hello.."); func(); } } ex2 - 항상 무한루프에 빠질까? recursion이 적절한 구조를 가지고 있다면, 항상 무한루프에 빠지는 것은 아니다. Base Case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. Recursive ..

> DFS(Depth-First Search, 깊이우선탐색) 이진트리의 순회 방법인 inorder, preorder, postorder 순회방법이 DFS의 이진트리 버전에 해당한다. lever order는 BFS의 이진트리 순회 버전이다. 깊이우선탐색(DFS) 출발점 s에서 시작한다. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다. 2번을 계속 반복한다. 노드 8에 도달했을 때처럼 인접한 노드들중 invisited 노드가 존재하지 않는다면, unvisited인 이웃 노드가 존재하지 않는 동안 계속해서 직전 노드로 되돌아간다. 다시 2번을 계속 반복한다. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다. 다음과 같은 흐름으로 깊이우선순..

> BFS(Breadth-First Search, 너비우선탐색) 그래프 순회 순회(traversal) 그래프의 모든 노드들을 방문하는 일 대표적 두 가지 방법 BFS (Breadth-First Search, 너비우선순회) DFS (Depth-First Search, 깊이우선순회) 너비우선탐색(BFS) BFS 알고리즘은 다음 순서로 노드들을 방문 L0 = {s}, 여기서 s는 출발 노드 L1 = L0의 모든 이웃 노드들 L2 = L1의 이웃들 중 L0에 속하지 않는 노드들 ... Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 한마디로 그래프에서 노드들을 동심원의 형태로 순회하는 방법 큐를 이용한 너비우선탐색 출발노드를 check하고 시작한다. 큐에 스타트 노드(1번노드)를 삽입한다. whil..

> Graph Algorithm - 개념과 표현 Graph (무방향) 그래프 G = (V, E) V : 노드 혹은 정점(vertex) E : 노드쌍을 연결하는 Edge 혹은 Link Object들 간의 이진관계를 표현 n = |V|, m = |E| 방향 그래프와 가중치 그래프 방향그래프(Directed Graph) G = (V, E) Edge (u, v)는 u로부터 v로의 방향을 가짐 가중치 그래프 Edge마다 가중치(weight)가 존재 그래프의 표현 인접행렬(adjacency matrix) 인접리스트(adjacency list) 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결 리스트 저장 공간 : O(n + m) 어떤 노드 v에 인접한 모든 노드 찾기 : O(degree(v)) ..

> Hashing - 02 좋은 해시 함수란? 현실에서는 키들이 랜덤하지 않음 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해시 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해시함수값이 불규칙적이 되도록 하는게 바람직하다. 해시함수값이 키의 특정 부분에 의해서만 결정되지 않아야 함 해시 함수 Division 기법 h(k) = k mod m 예: m = 20 and k = 91 ==> h(k) = 11 장점: 한번의 mod연산으로 계산, 따라서 빠름 단점: 어떤 m값에 대해서는 해시 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음, 가령 m = 2^p 이면 키의 하위 p비트가 해시 함수값이 됨 Multiplication 기법 ..