알고리즘
-
[BOJ 23033, Python 3] 집에 빨리 가고 싶어!알고리즘/BOJ 2021. 10. 5. 12:58
https://www.acmicpc.net/problem/23033 23033번: 집에 빨리 가고 싶어! 첫째 줄에 역의 수 N(2 ≤ N ≤ 20,000)과 노선 M개(1 ≤ M ≤ 300,000)가 주어진다. 둘째 줄 부터 M개의 줄에 걸쳐서 4개의 정수 A, B, T, W가 주어지고 A역에서 B역으로 가는 단방향 노선이 존재하며, 소요 www.acmicpc.net 풀이 최단 시간을 구해야 하는데, A역에서 B역으로 가는데 걸리는 시간이 T이므로 다익스트라 알고리즘을 생각해볼 수 있습니다. 그리고 새로운 열차를 기다려서 타는 방법은 현재 시간이 W의 배수이면 그대로 현재 시간을 우선순위 큐에 넣어주고, 현재 시간이 W의 배수가 아니라면 (W - (현재 시간) % W)만큼 시간을 추가하여 움직이게 해주..
-
[BOJ 23034, Python 3] 조별과제 멈춰!알고리즘/BOJ 2021. 10. 5. 12:52
https://www.acmicpc.net/problem/23034 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net 풀이 일단 1개의 조로 구성되어 있으면 학생들이 연락하며 소요되는 비용의 총합은 MST로 구할 수 있습니다. 하지만 문제는 2개의 조이기 때문에 시작점의 비용이 0인 곳이 두 곳이 존재합니다. 이런 그래프가 있다고 해봅시다. 여기서 MST를 빨간색으로 칠해보면 아래와 같이 나옵니다. 노란색을 팀장으로 해서 정점 두 곳을 노란색으로 칠하겠습니다. 이렇게 팀장이 있을 때, 답은 (1 + 2..
-
[BOJ 20157, Python 3] 화살을 쏘자!알고리즘/BOJ 2021. 10. 4. 13:54
https://www.acmicpc.net/problem/20157 20157번: 화살을 쏘자! 호준이는 요즘 활 쏘기에 푹 빠져 있다. 열심히 활 쏘기를 연습하던 호준이는 쏠 때 마다 10점이 나오는 경지에 이르렀다. 이렇다 보니 한 방향으로 있는 과녁에 쏘는 것에 실증을 느낀 호준이는 www.acmicpc.net 풀이 좌표평면에서 한 방향으로 화살을 쏜다는 것은 기울기가 설정되어 있다는 뜻입니다. 그래서 제 1사분면부터 제 4사분면까지 defaultdict를 만들어주고, 각 좌표의 최대공약수를 통해 기울기를 구해주고 조건에 맞는 사분면에 넣어주면 됩니다. x = 0 혹은 y = 0일 때는 따로 변수를 둬서 구해주고, 여기에 있는 값들중 최댓값을 구해주면 됩니다. 코드 1 2 3 4 5 6 7 8 9 ..
-
[BOJ 20158, Python 3] 사장님 달려가고 있습니다알고리즘/BOJ 2021. 10. 4. 13:50
https://www.acmicpc.net/problem/20158 20158번: 사장님 달려가고 있습니다 (1,1)에서 (1,2)로 이동한다. 다시 한 번 오른쪽으로 이동할 때 (1,2)에서 (1,4)로 1초안에 달려갈 수 있다. (1,3)에서 통제 시작 시간이 2초지만 현재 2초가 되지 않았기 때문에 이동할 수 있고 (1,4)에 www.acmicpc.net 풀이 지문을 읽어보면 BFS 알고리즘인 것을 알 수 있지만, 지문 내용이 구현하기가 참 까다롭습니다. 주의 할 점 가속도 같은 방향으로 달릴 경우 가속도가 붙는데, 속도 조절이 불가능함 방향 전환을 해야 1초에 1칸씩 달릴 수 있게 됨 통제 구역 가속도가 붙은 채로 통제 구역을 이동하면 [도중에 지나가는 통제 구역의 통제 시간] > [움직이기 시작..
-
[BOJ 20159, Python 3] 동작 그만. 밑장 빼기냐?알고리즘/BOJ 2021. 10. 4. 13:38
https://www.acmicpc.net/problem/20159 20159번: 동작 그만. 밑장 빼기냐? 카드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 단, N은 짝수이다. 둘째 줄에 카드의 윗장부터 밑장까지 카드의 값 X (1 ≤ X ≤ 10,000)이 정수로 주어진다. www.acmicpc.net 대사만 들어봤지 밑장 빼기가 정확히 뭔지 몰라서 검색하다가 맨 윗장 다음장이 밑장으로 알고 풀었다가 계속 틀려버림 풀이 카드를 분배 할 때 밑장 빼기를 하면 맨 아래에 있는 카드를 줄 수 있다고 합니다. 그리고 카드를 분배한 사람(정훈이)부터 받을 수 있으니, 밑장 빼기를 하지 않으면 홀수번째로 나눠주는 카드는 정훈이가 가지고, 짝수번째로 나눠주는 카드는 상대방이 가져가는 것을 통해 짝수,..
-
[BOJ 20160, Python 3] 야구르트 아줌마 야구르트 주세요알고리즘/BOJ 2021. 10. 4. 13:24
https://www.acmicpc.net/problem/20160 20160번: 야쿠르트 아줌마 야쿠르트 주세요 첫 줄에는 정점의 개수 V(1 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 100,000)가 정수로 주어진다. 그 다음 E 줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u 와 v(1 ≤ www.acmicpc.net 풀이 문제를 보면 모든 정점에서 다익스트라 알고리즘을 돌려야할 것 같지만, 야구르트 아줌마가 첫번째 지점을 제외한 야구르트를 파는 나머지 9개 지점의 정점을 다익스트라로 돌리고, 내가 시작점에서 움직이는 다익스트라를 돌려 총 10번 다익스트라를 돌리면 됩니다. 혹은 야구르트 아줌마 정점 9개를 돌리면서 내가 시작점에서 움직이..
-
[BOJ 18128, C++] 치삼이의 징검다리 건너기알고리즘/BOJ 2021. 10. 1. 18:28
https://www.acmicpc.net/problem/18128 18128번: 치삼이의 징검다리 건너기 첫 번째 줄에 땅의 크기 N(3 ≤ N ≤ 1,000), 물 생성지 개수 W(1 ≤ W ≤ N)가 주어진다. 두 번째 줄부터 W+1줄까지 물의 생성 위치 x(행), y(열) (1 ≤ x, y ≤ N)가 주어진다. W+2줄부터 N개의 줄에 www.acmicpc.net 풀이 물 이동은 1초에 상하좌우 한 번씩 움직이므로 BFS로 만들 수 있습니다. 치삼이는 상하좌우와 대각선을 포함한 8개의 방향으로 움직일 수 있는데, 치삼이가 이동하는데 시간이 걸리지 않는다고 했으므로 치삼이가 도착할 수 있는 시간은 치삼이의 이동 경로중에 제일 늦게 식은 돌의 시간이 됩니다. 그래서 치삼이의 시간을 구하는 것은 다익스..
-
[BOJ 20667, C++] 크롬알고리즘/BOJ 2021. 9. 27. 13:25
https://www.acmicpc.net/problem/20667 20667번: 크롬 첫 줄에는 N, M, K 값이 주어진다. (N ≤ 100, M ≤ 1,000, K ≤ 100,000) N 은 총 크롬 탭 수이다. M 은 목표 CPU 사용량이다. K 은 목표 메모리 할당량이다. 다음 N 줄에는 다음과 같이 크롬 탭의 정보가 www.acmicpc.net 풀이 CPU 사용량과 메모리 사용량, 중요도 세 가지를 고려해야 하는데, 두 개는 배열의 인덱스에 저장하고, 나머지 하나는 배열의 값에 저장하면 냅색문제로 풀 수 있게 됩니다. 배열의 인덱스에 넣을 값은 CPU의 최댓값이 1,000이고, 메모리는 100,000이고, 중요도는 500이므로 CPU의 사용량과 중요도를 인덱스에 넣으면 될 것 같습니다. 배열의..