[알고리즘] Minimal Spanning Tree 와 그리디 알고리즘
그리디 알고리즘 해결 방식으로 MST(Minimal Spanning Tree) 를 구해낼 수 있다. Minimal Spanning Tree(최소신장트리) 란? 한국말로하면 최소신장트리 로 그래프를 연결하는 가장 최적의 트리라 생각하면 된다. 모든 정점들을 포함해야하며, 사이클을 포함하면 안된다.(공간을 만들면 안됨) 가장 중요한 것은, 모든 간선의 가중치가 최소가 되는 트리를 Minimal Spanning Tree 라고 한다. 안전한 엣지(Safe edge)란? 안전한 엣지란, 우리가 MST를 구하는 과정에서, 현재 선택할 수 있는 엣지를 뜻한다. 예를들어 우리가 MST 를 구하고 있는 중인 어떤 상황일 때, A 엣지를 선택해서 MST를 만드는 경우도 있고 B 엣지를 선택해서 MST를 만들 수 있지만, ..
2019. 11. 19.
[알고리즘] 허프만 코드와 그리디 알고리즘 / 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진법으로 표현할때에는 아래와 같..
2019. 11. 14.
[알고리즘] 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 까지의 개수) 이다. 최종 비교시간..
2019. 11. 13.
[알고리즘] Greedy strategy / 그리디 알고리즘 전략, 구성
그리디 알고리즘 구성하기 1. 문제의 최적의 부분구조를 만든다. (문제를 잘 이해하고 어떻게 해결할지 구성하라는 의미이다.) 2. 재귀적으로 해결책을 도출한다. 3. 재귀 내부의 어느 단계이든, 최적의 선택 중 하나는 반드시 greedy choice 임을 증명한다. 4. greedy choice 를 했을 때, 하나의 부분문제만 남는 것을 보인다. (계속해서 greedy choice를 해야되기 때문에) 5. 그리디 알고리즘을 완성시킨다. 6. 재귀적인 알고리즘을 iterative 하게 변환한다. * 재귀적인 알고리즘 -> iterative 알고리즘 과정을 거치는 이유는 생각하는데에 있어서 편하기 때문이지 바로 알고리즘을 구현할 수 있다면 굳이 거치지 않아도 된다. 출처 : 고려대학교 정순영 교수님 알고리즘..
2019. 11. 12.
[알고리즘] Activity-selection-problem / 그리디 알고리즘
Activity-selection-problem이란? Expo 전시회에 놀러간 당신. Expo에는 여러 activity(활동) 들이 있다. activity들은 각각 시작시간과 종료시간이 다르고, 먼길 걸어 온 전시회이므로 당신은 최대한 많은 활동들을 즐기고 돌아가고 싶다. activity들의 정보(activity의 시작 시간, 종료 시간) 를 보고 최대 몇개의 활동을 할 수 있을지 어떻게 구할까?? Input : activity 집합 의 시작 시간, 종료 시간. (s_i, f_i) *조건 : 종료 시간은 오름차순 정렬이 되어 있다! (정렬 안되어있으면 직접 정렬하면 됨) 예시) 예를들어 3번째 activity 는 0분에 시작하여 6분에 끝난다. ( 시간은 분이라고 치자) 활동들을 즐기는 방법은 다양하다...
2019. 11. 12.
[알고리즘] Greedy Algorithm 이란?
왜 Greedy일까? // Greedy = 욕심부리는, 탐욕스러운 // 필자는 Greedy 가 전체 문제에 대해 생각하기 귀찮고, 게으르기 때문에 현재 상황에 대한 답만을 구해서 최종 결과를 도출하는 알고리즘 이라고 생각하고 암기하고 있다 (현재만 생각하는 욕심을 부린다는 의미이다.) 그리디 알고리즘은 현재 놓여진 상태에서의 최적의 답만을 찾는다. Locally 한 최적의 답만을 찾기 때문에 항상 Global Solution (전체문제의 답) 을 찾아준다고 확신할 수는 없다. 하지만, 우리는 현재 상황만 생각하면 되기 때문에 속도면에서는 빠르게 해결 할 수 있다. 예제) 위 그래프에서 goal까지의 최저비용 거리를 구해보자. 1) start 에서 출발. start 에서 가장 낮은 비용은 b 로 가는 3 ..
2019. 11. 7.
[알고리즘] Minimal Spanning Tree 와 그리디 알고리즘
그리디 알고리즘 해결 방식으로 MST(Minimal Spanning Tree) 를 구해낼 수 있다. Minimal Spanning Tree(최소신장트리) 란? 한국말로하면 최소신장트리 로 그래프를 연결하는 가장 최적의 트리라 생각하면 된다. 모든 정점들을 포함해야하며, 사이클을 포함하면 안된다.(공간을 만들면 안됨) 가장 중요한 것은, 모든 간선의 가중치가 최소가 되는 트리를 Minimal Spanning Tree 라고 한다. 안전한 엣지(Safe edge)란? 안전한 엣지란, 우리가 MST를 구하는 과정에서, 현재 선택할 수 있는 엣지를 뜻한다. 예를들어 우리가 MST 를 구하고 있는 중인 어떤 상황일 때, A 엣지를 선택해서 MST를 만드는 경우도 있고 B 엣지를 선택해서 MST를 만들 수 있지만, ..
[알고리즘] 허프만 코드와 그리디 알고리즘 / 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분에 끝난다. ( 시간은 분이라고 치자) 활동들을 즐기는 방법은 다양하다...
[알고리즘] Greedy Algorithm 이란?
왜 Greedy일까? // Greedy = 욕심부리는, 탐욕스러운 // 필자는 Greedy 가 전체 문제에 대해 생각하기 귀찮고, 게으르기 때문에 현재 상황에 대한 답만을 구해서 최종 결과를 도출하는 알고리즘 이라고 생각하고 암기하고 있다 (현재만 생각하는 욕심을 부린다는 의미이다.) 그리디 알고리즘은 현재 놓여진 상태에서의 최적의 답만을 찾는다. Locally 한 최적의 답만을 찾기 때문에 항상 Global Solution (전체문제의 답) 을 찾아준다고 확신할 수는 없다. 하지만, 우리는 현재 상황만 생각하면 되기 때문에 속도면에서는 빠르게 해결 할 수 있다. 예제) 위 그래프에서 goal까지의 최저비용 거리를 구해보자. 1) start 에서 출발. start 에서 가장 낮은 비용은 b 로 가는 3 ..