분류 전체보기

위상정렬은 순서가 정해져 있는 작업을 수행할 때 차례대로 수행할 수 있도록 도와주는 정렬 알고리즘의 일종입니다. 위상정렬의 수행과정은 크게 3가지로 나눌 수 있습니다. 1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음 2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제 3. 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다. -출처 위키백과 말로만 들으면 약간 어렵게 느껴질 수 있습니다. 그림과 함께 설명하겠습니다. 자기 자신을 가리키는 변이 없는 꼭짓점은 (5,7,3)으로 찾을 수 있습니다. 5를 가지고 2단계를 수행하면 5->11 이 변을 삭제하는 것입니다. 그리고 7을 가지고 2단계를 실행시키면 7->11, 7->8 두 개의 변이 삭제 ..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 이 문제는 전형적인 그리디 알고리즘 문제다. 그리디 알고리즘은 선택의 순간마다 당장의 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 최적값을 구하는데 사용되는 방법이다. 문제에서는 수를 적절히 묶어 최대 값이 나오게 하는 것이 최적 값이다. 보통 이런 문제는 첫째 줄에 수열의 크기가 주어진다. 둘째 줄부터는 n개의 수가 주어진다. 우리는 이 문제를 풀때 몇 가지 상황을 ..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 이 문제는 이렇게 쉽다고?? 이런 생각이 들었던 문제 같다. 첫째 줄에 카드의 개수가 주어진다. 둘째 줄부터는 카드가 주어진다. ex) 카드가 10,20,40 이렇게 주어지면 (10 + 20) + (30 + 40) 이렇게 계산을 한다. 이것을 보고 카드를 오름차순으로 정렬을 하고 리스트를 하나 만든 뒤, 더한 값을 리스트에 추가할 생각을 했다. 1 2 3 4 heap = [] num..

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 전형적인 강의실 문제다. 시작하는 시간과 끝나는 시간이 주어지고 최소의 강의실 개수를 구하는 문제는 매우 흔하게 볼 수 있다. 그러므로 풀는 방법을 마스터 하는 것도 괜찮다고 생각한다. 코딩 문제는 국어 문제가 아니다. 우리가 작가의 의도를 파악할 필요도 없고 왜 이런 문제를 냈을까 이런 생각도 할 필요가 없다. 우리는 단지 기계처럼 필요한 정보만 쏙! 습득해야 한다. 우선 첫째 줄에 회의..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 이 문제는 골드 치고는 생각보다 쉬웠던 문제 같다..! 우선 그리디 알고리즘과 우선순위 큐 문제를 자주 푸셨던 분은 쉽게 푸실 수 있는 문제다. 그리디 알고리즘은 추후에 정리해서 올리도록 하겠다. 우선순위 큐 문제는 밑에 링크를 보고 오시면 이해가 쉽게 됩니다. https://solution-is-here.tistory.com/114 백준(S2) 11279번: 최대 힙(파이썬, Python3)및 heapq 설명 https://www.acmicp..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 파이썬으로 heap문제를 풀려면 heapq라는 모듈을 알아야 한다. https://solution-is-here.tistory.com/114 백준(S2) 11279번: 최대 힙(파이썬, Python3)및 heapq 설명 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다..