알고리즘 공부 (7) 썸네일형 리스트형 Topology Sort (위상정렬) Topology Sort(위상정렬)이란 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 기능 특징 시간 복잡도 (노드 수 : V, 엣지 수 : E) 노드 간 순서를 결정 사이클이 없어야 한다. O(V+E) 위상정렬은 항상 유일한 값을 가지며 정렬이 되지 않는다. 또한 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없다. 따라서 위상정렬을 정의할 수없으므로 해당 부분을 염두해야한다. 위상정렬의 원리 1. indegree는 자기 자신을 가리키는 edge의 개수이다. 해당 부분에서 자기 자신을 가리키는 부분을 보면 된다. 인접 리스트를 A라고 하고 다음과 같이 인접 리스트에 기반을 둔 진입 차수 리스트를 만들면 다음과 같다. 1 2 3 4 5 6 0 1 2 1 2 1 첫 행은 노드를 의.. Union , Find 백준에서 나온 문제 중에서 최소 신장트리를 이용한 문제가 있었다. 해당 알고리즘이 필요하기 위해서 선제적으로 알아야할 개념인 서로소 집합 자료구조에 대해서 알아보고자 한다. 그리디 알고리즘이라고 할 수 있는 Kruscal Algorithm과 Stack, Queue를 활용해야하는 위상정렬 알고리즘이 그래프 알고리즘의 종류이다 우선 Edge와 Node로 이루어져 있는 그래프 데이터들은 다익스트라 알고리즘과 같은 '최단 경로 알고리즘'과 stack과 재귀함수를 사용하여 DFS,BFS 활용할 때 주로 이루었다. 따라서 '서로 다른 객체가 연결되어 있다'는 이야기를 들었다면 반사적으로 그래프 데이터를 활용한 알고리즘이 떠오른다. 메모리 측면에서 인접형렬이 저장한 정보는 많다. 따라서 노드간에 연결되지 않은 정보도.. [알고리즘] Heap sort (힙정렬) Heap Binary Tree 일종이다. Priority Queue를 위하여 만들어진 데이터구조이다 간단하게 말해서 최대값과 최솟값을 효율적으로 추출할 수 있도록 하는 방법 Max heap 개념 (Min heap은 이와 반대) 1. max heap 삽입 heap에 새로운 element가 들어오면, 새 노드를 heap의 마지막 노드에 이어서 삽입 새로운 노드를 부모 노드들과 교환을 통해서 힙을 정렬 다음의 일련의 과정을 거쳐서 새로운 노드가 8이 들어올 경우 바꿔주며 정렬을 시작한다 2. max heap 삭제 최대 힙에서 최대값은 루트 노드로 이를 삭제한다 삭제된 루트 노드에 마지막 노드를 가져온다 1번에서 나온 방법과 같이 heap을 구성한다 heap sort는 시간복잡도가 상당히 효율적인 편이다. 따라.. Dijkstra Algorithm (다익스트라 알고리즘) Dijkstra Algorithm 먼저 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘입니다 (Greedy 기반으로 최적의 경로를 탐색) ※ Greedy란 탐욕 알고리즘으로 매번 주어진 상황에서 가장 최적의 경로를 선택함으로써 만들어가는 탐색 방법입니다. 다익스트라 알고리즘은 학부 알고리즘 수업에서 반드시 다루는 알고리즘이며 네트워크 같은 곳에서도 종종 쓰이기 때문에 이름과 그 목적만큼은 유명합니다. 참고로 길찾기 알고리즘의 대표적인 예시로 A*(astar) 알고리즘이 있습니다. 대표적으로 네비게이션에서의 길찾기처럼 100% 정확한 최단거리를 내지 않아도 되고, 또 정점의 개수가 너무 많아 현실적으로 다익스트라 알고리즘을 활용하기 힘들경우에 사용되는 근사 알고리.. Greedy Algorithm (1931 : 회의실 배정) Greedy Algorithm (그리디 알고리즘)이란? Greedy 는 '탐욕스러운, 욕심이 많은' 이란 뜻입니다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법입니다. 탐욕 알고리즘은 최적해를 구하는데 사용되는 근사적인 방법입니다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장이 없습니다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들입니다. 탐욕 알고리즘 문제를 해결하는 방법 1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택합니다. 2... 자주하는 실수 정리 실수를 안할 수 없지만 내가하거나 남이하는 실수에서 배움을 얻어 유사한 실수를 저지르지 않는 것이 중요합니다. 프로그래밍 대회에서 흔히 저지르는 실수들을 정리해보면서 저에게도 각인시킬려고 합니다. 산술 오버플로 계산과정에서 변수의 표현 범위를 벗어나는 값을 사용하는 산술 오버플로 배열 범위 밖 원소 접근 C/C++은 배열의 원소에 접근 시 인덱스가 배열 범위 안에있는지 확인을 따로 안합니다. 따라서 버그를 찾기에 매우 힘든 오류입니다. 그나마 런타임 스택 등을 통해 프로그램이 런타임 오류를 내며 종료하는 경우에는 배열 범위 밖에 접근했다는 사실을 알 수도 있지만, 오류가 나지 않으면서 오답을 내는 경우도 있습니다. int array[10], t; 이때 변수 array와 t가 메모리 상에 연속해서 위치하고.. 알고리즘 공부 시작 프로그래밍이 뭔지도 모르는 상태로 대학에 입학 후에 군대를 다녀와서까지 포인터라고 하면 ppt에 쓰는 포인터밖에 모르는 상태로 작년의 대학생활을 하였습니다. 그러다보니 공부해보고 싶은 분야가 생기게 됐습니다. 알고리즘 공부가 필요하다고 생각이 들었지만 하고싶은 날만하고 안하는 날이 대부분인게 마음에 안들어 여기에 혼자 공부하면서 종종 올려야 내것이 될거란 생각이 들었습니다. 주변 선배님중에서 알고리즘 잘하시는 분께서 구종만 책인 책 시리즈를 추천해주셨고 남은 대학생활동안 이 책과 온라인에 있는 자료들을 통해서 공부를 차근차근 해볼려고합니다. 부족하지만 저의 것이 되는 공부를 해보도록 노력하겠습니다. 이전 1 다음
