조던을좋아하는코린이

위상 정렬이란? -그래프의 꼭짓점들을 변의 방향을 거스리지 않도록 나열하는 것을 의미한다 ( https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC ) - 쉽게 말하자면 선후 관계에 따라 정렬이 이루어진다고 보면된다. - 예를들어 대학교의 수강과목에서의 선수과목이 있다면 그 과목을 수강해야 다음과목을 들을 수있는것 처럼 말이다. - 위상정렬이 가능한 조건 = DAG ( Driect Acyclic Graph 의 약자로 사이클이 존재하지 않는 방향이 있는 그래프를 의미한다. ) 즉, 사이클이 존재한다면 위상정렬이 이루어 질 수 없다. 진입차수 - 위상정렬을 구현하고 이해하기 위해서는 진입차수에 대해서 알아야한다. - 예를들어 창의적 공학설계과목..

- 선택 정렬 - 정렬을 배우기 전 간단하게 프로그래밍 언어에서 몇개의 정렬 알고리즘 종류가 있는지 살펴보았다 다음과 같은 정렬의 종류가 있다는 것을 위키피디아를 통해서 알 수 있었다. 아직 버블,선택,삽입,병합,힙,퀵 이정도의 정렬에 대해서 배운적은 있으나 그 이하의 나머지 정렬은 처음들어본다. 앞으로 알고리즘 공부를 통해서 하나씩 배워보려고 한다. 먼저, 정렬의 가장 기본적인 선택정렬에대해서 정리를 하겠다. - 선택 정렬이란 - 주어진 배열에서 최소값을 찾고 그 값을 배열의 맨 앞에 위치한 값과 바꿔주는 것이다. " 1 10 5 8 7 6 4 3 2 9 " 을 오름차순으로 구현을 한다면 1부터 10까지 10개의 수에서 가장 작은 숫자를 먼저 찾고 해당 위치의 인덱스를 기억한 이후에 맨 앞의 값과 자리..

분리 집합은 서로소 집합이라고도 부른다. 분리 집합의 특징으로 - 전체 집합 U에 대해, U의 분리집합은 A, B는 다음을 만족한다. 1) A,B 는 U의 부분집합이다. 2) 집합 A,B는 같은 원소를 가지지 않는다. 3) A,B의 합집합이 곧 전체집합(U)이다. ( A,B에 속하지 않는 원소는 U에도 속하지 않는다 ) - 그림 (1)과 같은 경우를 제외한 나머지 (2) (3) 번의 경우는 될 수없다. - 집합이 3개 이상의 경우에도 똑같이 적용된다. - Union Find 알고리즘 - 분리 집합을 구현하는 알고리즘으로써, 트리의 형태로 표현이 된다. 배열을 이용하여 보통 구현이 된다. 다음과 같은 집합들이 존재할 때 연결정보를 입력할 때 값이 작은값을 기준으로 갱신을 한다. 따라서 그림 은 ..