yekang

4차 산업혁명의 시대의 흐름에 편승하고 싶은 자, IT 업계로의 취업을 꿈꾸는 꿈나무에게 추천하고자 합니다. 인턴하면서 파이썬을 쓰고 있는데 파이썬을 사용한 알고리즘 가이드북이라 좋았고, "코딩게임" 플랫폼을 이용해 재미있게 접근할 수 있었습니다. 사실, 가장 중요한 것은 문제 해결 능력이라고 생각하는데 제가 기존에 본 책들과는 달리 아이디어적으로 접근하는 부분이 친절해 알고리즘 입문자, 알고리즘을 학교에서 배웠지만 응용하지 못하는 학생들에게 더욱 도움이 될거라 생각합니다. 책을 정독하고 나서 TAOCP(The Art of Computer Programming)책을 학습하면 더할 나위 없이 좋고 추후 취업을 위한 코딩 테스트에 많은 도움이 될거라 생각합니다!!

4.1.1 프림알고리즘- 가장 가까운 정점들 모으기- 가장 가까운 마디를 추가하는 과정을 Y=V가 될 때까지 계속 12345678910F=공집합;Y={v1};while(사례 미해결){ Y에서 가장 가까운 V-Y에 속한 이음선을 선택; 그 마디를 Y에 추가; 그 이음선을 F에 추가; if(Y==V) 사례해결;} cs nearest[i] = vi에 가장 가까운 Y에 속한 마디의 인덱스distance[i] = vi와 nearest[i]가 인덱스인 두 마디를 연결하는 이음선의 가중치 시작할 때 Y={v1}이므로, nearest[i]는 1로 초기화하고 distance[i]는 v1과 vi를 연결하는 이음선의 가중치로 초기화한다. 프림 알고리즘문제: 최소비용 신장트리를 구하시오.입력: 정수 n>=2인 마디의 개수가 ..

Prim의 알고리즘-임의의 노드를 출발노드로 선택-출발 노드를 포함하는 트리를 점점 키워 감-매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택 왜 MST가 찾아지는가?-prim의 알고리즘의 임의의 한 단계를 생각해보자.-A를 현재까지 알고리즘이 선택한 에지의 집합이라고 하고, A를 포함하는 MST가 존재한다고 가정하자. f를 추가하고 그와 연결된 에지중에서 기존의 key 값보다 작으면 key값 갱신한다.g의 key값은 2, 파이는 = f가 된다. key값이 최소인 노드 찾기-최소 우선순위 큐를 사용-v-va에 속한 노드들을 저장-extract-min: key값인 최소인 노드를 삭제하고 반환

최소신장 트리 (MST)입력 : n개의 도시, 도시와 도시를 연결하는 (도로)비용문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 함 Generic MST 알고리즘 -어떤 MST의 부분집합 A에 대해서 A 합집합 {(u,v)}도 역시 어떤 MST의 부분 집합이 될 경우 에지 (u,v)는 A에 대해서 안전하다(safe)고 한다. - MST의 대표적 예로 kruskal algorithm과 prim algorithm이 있는데 이들의 공통적 알고리즘을 generic MST라고 한다. -Generic MST 알고리즘:1. 처음에는 A=공집합이다.2. 집합 A에 대해서 안전한 에지를 하나 찾은 후 이것을 A에 더한다.3. 에지의 개수가 n-1개가 될 때까지 2번을 반복한다. Generic-MST(G,w)A