위상정렬2 백준 게임 개발 www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어.. 2021. 3. 29. 위상정렬 위상정렬은 정렬 알고리즘의 종류이다. 위상정렬이란 '방향그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열' 하는 것이다. 쉽게 비유를 하자면 '대학교 커리큘럼'을 예로들수있다. 예를들어 모 대학교의 컴공과는 인공지능과목을 자료구조를 선수강한 뒤에 신청할수있도록 하였다. 이처럼 그래프상에서 선후관계가있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 순서를 계산할수있다. 위상정렬의 알고리즘 순서는 다음과 같다. 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌때 까지 다음의 과정을 반복한다. 1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 여기서 진입 차수란, 특정노드로 들어오는 간선의 개수와 같다. #.. 2021. 2. 26. 이전 1 다음