알고리즘/백준
-
[백준] 1753 : 최단경로 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 23:46
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 풀이 전 설계 방향 그래프 탐색 문제이며 시작점에서 다른 모든 정점으로의 최단 경로를 구해야 합니다. 정점의 개수가 20,000개 이고 간선의 개수가 300,000이다 보니 완전 탐색은 불가능하고 정점과의 거리를 갱신시키는 다익스트라 알고리즘을 그대로 적용하면 될 것 같습니다. 정점의 개수가 많기 때문에 인접행렬보다는 인접 리스트를 이용합니다. 또는 fr..
-
[백준] 1238번 : 파티 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 23:46
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해석 N명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다. 마을 사이에는 총 M개의 단방향 도루들이 있고, i번째 길을 지나는데 T(i)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 이때 최단거리를 원하며 도로들은 단방향이다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은? 문제 풀이..
-
[백준] 18222 : 투에-모스 문자열 - 자바(JAVA)알고리즘/백준 2022. 3. 17. 00:01
https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 문제 해석 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 문자열 X는 다음과 같은 과정으로 만들어진다. 1. X는 맨 처음에 0으로 시작한다. 2. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. 3. X의 뒤에 X'을 붙인 문자열을 X로 다시 정의한다. 4. 2~3의 과정을 무한히 반복한다. 입력 첫 번째 줄에 자연수 k (1 ≤ k ≤ 10^18..
-
[백준] 10163 : 색종이 - 자바(JAVA)알고리즘/백준 2022. 3. 16. 00:01
https://www.acmicpc.net/problem/10163 10163번: 색종이 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓여진다. 이때 색종이가 비스듬하게 놓이는 경우는 없다. 즉, 모든 색종이의 변은 서로 평행하거나, 서로 수직이거나 둘 www.acmicpc.net 문제 해석 평면에 색깔이 서로 다른 직사각형 모양의 색종이 N장이 하나씩 차례로 놓인다. 색종이는 비스듬하게 놓이는 경우는 없습니다. 위의 그림에서 4번 색종이를 하나 더 놓았을 때 3번 색종이는 완전히 가려서 보이지 않게 됩니다. 다음과 같이 N장의 색종이가 주어진 위치에 차례로 놓일 경우, 각 색종이가 보이는 부분 면적을 구하는 프로그램을 작성하세요. 문제 풀이 전 설계 https://junuuu...
-
[백준] 2563 : 색종이 - 자바(JAVA)알고리즘/백준 2022. 3. 15. 00:01
https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 문제 해석 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 변과 도화지의 변이 평행하도록 붙입니다. 여러 장의 색종이를 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.(종이가 겹치게 붙을 수 있습니다.) 입력 첫째 줄에 색종이의 수가 주어집니다. 이어 둘째 줄부터 한 줄..
-
[백준] 1158번 : 요세푸스 문제 - 자바(JAVA)알고리즘/백준 2022. 3. 14. 00:01
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 해석 문제는 사람의 수 N과 제거할 순번인 K를 입력받습니다. 초기 시작 자료구조는 다음과 같습니다 1, 2, 3, 4, ......, N 여기서부터 순서대로 K번째를 제거합니다. N=5라 가정하여 초기 시작 자료구조는 1, 2, 3, 4, 5 이며 K=2라고 가정해보겠습니다. 초기 시작 1, 2, 3, 4, 5 2번째수인 2제거 step 1 : 1, 3, 4, 5 굵은글씨 3부터 2번째수인 4제거 step 2 : 1,3,5 굵은글씨 5부터 2번째수인 1제거 step 3 : 3,4 ..
-
[백준] 1275번 : 커피숍2 - 자바(JAVA)알고리즘/백준 2022. 3. 13. 16:41
https://www.acmicpc.net/problem/1275 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 문제 해석 N개의 정수를 가지고 게임을 한다. 우리는 심판 역을 맡았기 때문에 질문에 대한 답들을 미리 알아야 한다. 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다. 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어집니다. 셋째 줄부터 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합을 구하라, a번째 수를 b로 바꾸어라 라는 뜻의 데이터가 주어..
-
[백준] 7562 : 나이트의 이동 - 자바(JAVA)알고리즘/백준 2022. 3. 9. 00:01
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제해석 나이트는 다음그림과 같이 이동할 수 있습니다. 나이트가 이동하려는 칸이 주어질때 나이트는 몇 번 움직여서 목적지로 이동할 수 있을까요? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어집니다. 각 테스트 케이스는 3줄로 이루어져 있습니다. 1. 체스판의 한 변의 길이 l 이 주어집니다. (체스판의 크기는 l x l 입니다) 2. 나이트가 현재 있는 칸이 주어집니다. 3. 나이트가 이동하..