PLOD

위상정렬위상정렬은 정렬 알고리즘의 일종이다. 이상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용 할 수 있는 알고리즘이다. 즉, 위상정렬은 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것이다. 위상 정렬 알고리즘을 사용하기 위해서는 진입 차수(degree) 부터 알아야한다. 진입차수란 특정한 노드로 들어오는 간선의 개수를 의미한다. 진입차수를 이용하여 위상정렬을 하는 방법은 다음과 같다.1. 진입차수가 0인 노드를 queue에 넣는다.2. 큐가 빌 때까지 다음의 과정을 반복한다.Ⅰ. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.Ⅱ. 새롭게 진입차수가 0이 된 노드를 queue에 넣는다.위상 정렬의 시간 복잡도는 O(V+E)이다...

정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등으로 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진탐색(binary search)가 가능해진다. 파이썬에서 버블정렬, 선택정렬 알고리즘을 사용하는 것보다 sort()함수와 sorted()함수가 O(NlogN)의 시간 복잡도를 보장해주기 때문에 더 효율적이지만, 간혹 수기로 코딩테스트를 보거나 직접 정렬 알고리즘을 아는지 물어보는 경우가 있기 때문에 알고 있는 것이 좋다1. 선택 정렬(selection sorting)컴퓨터가 데이터를 정렬할..

정렬이란 이름 , 학번 , 키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다. 정렬 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할 수 있다. 값이 작은 데이터를 앞 쪽에 놓으면 오름차순 정렬, 반대로 놓으면 내림차순 정렬이라고 한다. 정렬 알고리즘의 핵심 요소는 교환,선택,삽입이다. 대부분의 정렬 알고리즘은 이 3가지 요소를 응용한 것이다. 1. 버블 정렬 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬이라고도 한다. 먼저 자료 7을 4와 교환하고 다음에 7과 5을 교환하고 7과 1을 교환하고 7과 4을 교환한다. 첫번째 과정을 수행하면 가장 큰 원소가 끝에 배치되게 된다. 두번째로 4와 5를 비..