java

[JAVA] 백준 1766 : 문제집

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 해결방법 위상 정렬의 대표적인 문제 중에 하나이다. 근래 위상정렬 문제를 꾸준히 풀어보고 있는데, 풀 때마다 헷갈려서 정리를 한 번 해두려고 한다. 일단 위상정렬은 Topological Sort 라고 부르며, 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말하면 순서가 정해져있는 것들을 순서대로 나열하는 건데, 수학 2를 하기 전에 수학 1을 먼저 배워야 하고 그전에 기초수학을 배워야 하는..

[JAVA] 백준 1162 : 도로포장

문제 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 해결방법 1번에서 N번까지 가는 최소 시간을 출력하는 문제인데, 추가적으로 도로포장이라는 조건이 주어져있다. 포장이 가능한 횟수는 K로 주어지고, 포장을 하게 되면 해당 도시를 잇는 도로를 통과하는 시간이 0이 된다. 그래서 기본 다익스트라에 추가적으로 포장횟수를 기록해야 한다. 원래 배열은 dijk[해당 도시까지 최솟값] 을 나타낸다고 하면 이번 문제에서는 dijk[해당 도시까지 최솟값][포장 횟수] 를 사용한 2차원 ..

[JAVA] 백준 1963 : 소수 경로

문제 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 해결방법 문제를 읽어보면 가능한 비밀번호는 1000 ~ 9999 사이의 숫자이다. 그렇기 때문에 에라토스테네스의 채를 이용해서 9999까지의 소수를 찾아내고 현재 비밀번호에서 각 자리수를 하나씩 변경하며 그 수가 소수라면 다음으로 또 한자리는 변경하는 방식으로 목표 비밀번호까지 최소한의 횟수를 찾는 문제이다. 순서를 정리하면 1. 9999까지 소수를 찾는다. 2. 각 자리수를 변경하며 목표 비밀번호를 찾는데, 거쳐가는 비밀번호도 모두 소수인지 확인해야한다. 추가적으..

[JAVA] 백준 12781 : PIZZA ALVOLOC

문제 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 해결 방법 CCW (Counter-ColockWise) 라는 알고리즘을 쓰는 문제인데, 처음 보는 알고리즘이라 기록해둘 겸 글을 작성하게 되었다. CCW는 '평면에 놓여진 세 점의 방향 관계를 구하는 알고리즘' 인데 CCW 식을 사용해서 양수가 나오면 이 그림과 같이 시계 반대 방향으로 향하는 방향 관계를 가지고 있다고 하고, 음수가 나온다면 이와 같이 시계 방향으로의 관계를 가지고 있다고 알 수 있다. 그러면 0이 나오는 경우는 뭘까? 그때는 세 점의 관계가 평행 즉, ..

[JAVA] 백준 1922 : 네트워크 연결

문제 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 풀이방법 한 정점에서 모든 정점을 연결하는데에 드는 비용을 최소로 하는 문제이다. 크루스칼과 프림을 사용할 수 있는데, 프림을 안써본지 오래되어서 프림으로 코드를 구성해보았다. 인접리스트로 양방향 연결을 먼저 해준다음 임의의 시작점에서 출발시키면된다. 프림은 방문배열과 각 정점의 최소비용을 저장할 정점 크기만큼의 1차원 배열을 사용한다. 최소비용을 저장할 배열은 최대값으로 초기화해준다. 필자는 우선순위큐를 활용한 프림을 구성하였는데, 그렇기 때문에 비용에 따라 오름차순 정렬을 통해 비용이 적은 것 부터 탐색하도록하였다. 임의의 시작 정점을 정하였..