개발자 호소인

사이클이 없는 방향 그래프(DAG) 에서 정점을 일렬로 정렬 1. 순방향 방법 : 진입 차수가 0인 정점으로부터 출력하고 제거   2. 역방향 방법 : 진출 차수가 0인 정점으로부터 출력하고, 그 출력된 그래프를 역순으로 -> 결국에 순방향 방법과 위상은 똑같이  Big O : O( N + M )  무방향 그래프의 연결 성분에서, 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분-> 정점 하나가 삭제되더라도 또 다른 경로로 우회 가능 할 수 있게끔  단절 정점 ( Articulation Point, Cut Point ) : 연결 성분의 정점 중 하나의 정점을 삭제했을 때, 두 개 이상의 연결 성분으로 분리될 떄 삭제된 정점. 다리 간선 ( Bridge ) : 간선을 제거했을 때, 두 ..

알고리즘을 배우기 위한 준비 : performance analysis  효율성 : time complexity + space ( memory ) complexity 알고리즘이 효율적인지 측정하는 방법 1. performance analyisis : 알고리즘의 성능을 이론적으로으로 분석 -> Big O , Theta, Omega time 2. performance measurement : 실제로 알고리즘을 실행해보며 성능 측정 -> 실행 환경에 크게 의존 ( hardware, software 등 )  example) float type array ->  Big O : upperbound , 최악의 경우Big Omega : lowerbound , 최선의 경우Big Theta : O == Omega 일때, 즉..

힙 정렬 먼저 heap 에 대해 다시 알아보자. 완전 이진 트리의 일종으로, 우선순위 큐를 위하여 만들어진 자료구조이다 . 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있다. 완전한 정렬이 아닌 느슨한 정렬 상태를 가진다. 2진 트리의 경우 배열로 깔끔하게 구현이 가능한데, 마찬가지로 배열로도 2진 트리를 구현 가능하다. def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left arr[largest]: largest = left if right arr[largest]: largest = right if largest != i: arr[i], arr[largest] = arr[largest], arr[i] heapi..

힙 정렬, 코드 , 활용 문제 풀이

병합 정렬 정렬된 두 배열이 있다고 가정했을 때, 두 배열을 합쳐 하나의 정렬된 배열로 만드는 방법은 두 개의 배열 처음부터 시작하여 두개의 값 중 더 작은 값을 배열에 넣고, 다시 남은 값을 비교하는 방식으로 채워나가는 것이다. 두 배열의 원소를 N개라고 가정한다면, 각 원소는 단 한번만 이동을 하게 되므로 시간복잡도는 O(N) 이 된다. 그러나 우리가 정렬해야되는 배열은 한개다. 따라서 배열을 두개로 쪼개준다. 언제까지 ? 배열의 원소개 1개가 될 때 까지 재귀적으로 쪼개준다. 쪼갠 후 정렬을 하고, 다시 합치므로 이러한 방식을 divide and conquer 이라고 부른다. 병합정렬의 시간 복잡도는 O(nlogn) 이다. 쪼개는데에 logn, 배열을 이동하는 데에 n 만큼의 시간이 소요되기 때문이..

O(N^2) 에서 벗어난 정렬들 학습 이진탐색

원형 연결 리스트 원형 연결 리스트 또한 doublelinkedlist 와 유사하다. 하지만 다른 점이 있다면, 마지막 노드의 링크가 첫 번째 노드를 가리킨다는 것이다. 따라서 어떠한 하나의 노드에서 링크를 따라가면 모든 노드가 방문 가능하다. 따라서 tail 의 의미가 없어지고 head 값만 가지고 이용하여도 문제가 없다. 따라서 원형 연결 리스트의 장점으로는 노드의 삽입과 삭제가 단순해진다는 것이 있다. 단점으로는 노드의 삽입과 삭제시 선행 노드의 포인터가 필요하다는 점이 있다. 정렬 알고리즘 배열을 데이터 (자료구조) 에 담게 되면, 데이터를 정렬해야 할 때가 있다. 따라서 수많은 정렬 알고리즘이 개발되었으며 가장 기본적인 버블정렬부터 배워보도록 하자. 별찍기를 배운 직후 1학년 1학기때 배운 기억..

4회차에서는 3회차에서 마저 공부하지 못했던 원형 리스트와, 어려가지 정렬 알고리즘에 대하여 공부해볼 계획이다.