컴퓨터 지식64
[알고리즘] Minimal Spanning Tree 와 그리디 알고리즘
그리디 알고리즘 해결 방식으로 MST(Minimal Spanning Tree) 를 구해낼 수 있다. Minimal Spanning Tree(최소신장트리) 란? 한국말로하면 최소신장트리 로 그래프를 연결하는 가장 최적의 트리라 생각하면 된다. 모든 정점들을 포함해야하며, 사이클을 포함하면 안된다.(공간을 만들면 안됨) 가장 중요한 것은, 모든 간선의 가중치가 최소가 되는 트리를 Minimal Spanning Tree 라고 한다. 안전한 엣지(Safe edge)란? 안전한 엣지란, 우리가 MST를 구하는 과정에서, 현재 선택할 수 있는 엣지를 뜻한다. 예를들어 우리가 MST 를 구하고 있는 중인 어떤 상황일 때, A 엣지를 선택해서 MST를 만드는 경우도 있고 B 엣지를 선택해서 MST를 만들 수 있지만, ..
[DB] 비트리와 비트맵 인덱스의 장단점
키의 갱신 비용 B-Tree 인덱스구조 : 데이터를 삽입, 삭제할 때 키를 알맞는 곳에 끼워 넣어주면 되기 때문에 비교적 간편하다. Bitmap 인덱스구조 : 모든 비트맵 인덱스들에 갱신작업을 해주어야 하므로 힘들다. 사용하기 좋은곳 B-Tree 인덱스구조 : 컬럼의 값 종류가 다양한 곳에 좋다. Bitmap 인덱스구조 : 컬럼의 값 종류가 적은 곳에 좋다. ( Ex. 성별 : 남/여 , 국가 : 국민 / 외국인 ) - 값 종류가 다양해지면 그에 따른 bitmap 이 무수히 늘어나게된다. 다중 쿼리문 B-Tree 인덱스구조 : 다양한 컬럼이 이용되는 쿼리문에는 비효율적이다. Bitmap 인덱스구조 : 다양한 컬럼이 이용되는 쿼리문에 좋다. - 그저 비트맵끼리 OR / AND 이런거 해버리면 되기 때문이다.
[알고리즘] 허프만 코드와 그리디 알고리즘 / Huffman code and greedy algorithm
문자열의 코드화 우리가 인터넷 상에서 쓰는 한글, abcd 알파벳. 컴퓨터는 우리처럼 글자 자체로 보지 않고, 결국 2진수 0과 1의 모음으로 이해를 한다! a는 01 로 약속, b는 10 으로 약속하면 ab라는 문자는 컴퓨터 내에 0110 으로 저장이되고 100110 이란 코드를 받아들이면 컴퓨터는 아, 이것은 bab 이구나 로 해석하는 것이다. 우리가 쓰는 문자를 컴퓨터 내에 저장한다고 할 때, 이 약속된 코드의 비트수가 적을 수록 (010101 이런게 짧을수록) 메모리적으로 이득일 것이다! 그렇다면 어떻게하면 문자열을 효율적으로 코드화를 할 수 있을까? Fixed-length codeword / Variable-length codeword abcdef 를 코드화하여 2진법으로 표현할때에는 아래와 같..
[알고리즘] Quick sort는 왜 빠를까? (3) : 비교 실행의 개수 계산
비교의 수 가 곧 시간이다 전 게시물까지 내린 결론은 퀵 소트의 실행 시간은 서로 다른 두 원소가 얼마나 직접적으로 비교가 되느냐에 직결된다는 것이었다. 퀵 소트의 피벗은 랜덤으로 결정된다고 가정하였으므로, 랜덤 피벗에 따라 서로 다른 두 원소가 얼마나 비교되는지가 결정된다! 비교될 확률 i~j 까지 원소들 Z_ij 가 있을 때 원소 , z_i 와 z_j 가 비교될 확률을 구해보자. 만약 피벗이 i < p < j 인 p로 설정이 된다면, i 와 j 는 p 랑만 비교가 된 후 서로 다른 두 하위문제로 넘어가는 경우이다. 따라서 피벗이 i 혹은 j 로 설정 돼었을 때 X_ij = 1 이다. 따라서 Pr{z_i is compared to zj} = 2 / j-i+1 (i~j 까지의 개수) 이다. 최종 비교시간..
[알고리즘] Greedy strategy / 그리디 알고리즘 전략, 구성
그리디 알고리즘 구성하기 1. 문제의 최적의 부분구조를 만든다. (문제를 잘 이해하고 어떻게 해결할지 구성하라는 의미이다.) 2. 재귀적으로 해결책을 도출한다. 3. 재귀 내부의 어느 단계이든, 최적의 선택 중 하나는 반드시 greedy choice 임을 증명한다. 4. greedy choice 를 했을 때, 하나의 부분문제만 남는 것을 보인다. (계속해서 greedy choice를 해야되기 때문에) 5. 그리디 알고리즘을 완성시킨다. 6. 재귀적인 알고리즘을 iterative 하게 변환한다. * 재귀적인 알고리즘 -> iterative 알고리즘 과정을 거치는 이유는 생각하는데에 있어서 편하기 때문이지 바로 알고리즘을 구현할 수 있다면 굳이 거치지 않아도 된다. 출처 : 고려대학교 정순영 교수님 알고리즘..
[알고리즘] Activity-selection-problem / 그리디 알고리즘
Activity-selection-problem이란? Expo 전시회에 놀러간 당신. Expo에는 여러 activity(활동) 들이 있다. activity들은 각각 시작시간과 종료시간이 다르고, 먼길 걸어 온 전시회이므로 당신은 최대한 많은 활동들을 즐기고 돌아가고 싶다. activity들의 정보(activity의 시작 시간, 종료 시간) 를 보고 최대 몇개의 활동을 할 수 있을지 어떻게 구할까?? Input : activity 집합 의 시작 시간, 종료 시간. (s_i, f_i) *조건 : 종료 시간은 오름차순 정렬이 되어 있다! (정렬 안되어있으면 직접 정렬하면 됨) 예시) 예를들어 3번째 activity 는 0분에 시작하여 6분에 끝난다. ( 시간은 분이라고 치자) 활동들을 즐기는 방법은 다양하다...