본문 바로가기

알고리즘51

BOJ 1753 - 최단경로 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 접근 방법 최단 경로를 구하는 알고리즘 중, 학부 수업에서 배운 다익스트라를 사용하기로 했다. 다익스트라에 대한 내용은 추후 따로 포스팅을 해야겠다. 간단하게 원리는 다음과 같다. 1. 모든 정점에 최단경로 d를 저장한다. (초기화는 무한으로) 2. priority_queue에 최단 경로 d를 기준으로 오름차순이 되게 한다. 3. pq에서 뽑은 정점을 가지고,.. 2024. 2. 20.
[그리디 #16] BOJ 19598 - 최소 회의실 개수 https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 계속된 실패.. 비슷한 문제인 회의실 배정 문제에선 끝나는 시간을 기준으로 정렬하여 진행하였다. 이와는 다른 방법을 생각해보다 회의 시간이 짧은 것을 기준으로 해보면 어떨까라고 생각했다. 이를 이용해 어떻게든 해보려고 했는데 실패하고, 안되는 이유를 찾아보았다. 아무리 끝나는 회의 시간이 짧더라도 끝나는 시간이 짧을 수록 이득을 볼 수 있기 때문에 이는 틀린 아이디어이다. 접근 방법 회의가.. 2024. 2. 19.
[그리디 #15] BOJ 1700 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 1차 시도 너무 간단하게 생각했다. 뒷 부분 중 가장적게 사용되는 것을 뽑는 것으로 진행해버렸다. 당연히 반례가 존재한다. 3 15 3 2 1 2 1 2 1 2 1 3 3 3 3 3 3 위 반례에서 3과 2를 꼽고나서 1이 나왔을 때, 3이 2보다 많이 사용되므로 2를 뽑게된다.. 정답 "가장 나중에 사용되는 것을 우선적으로 뽑자!" 라는 것을 다시 생각해보았다. 나중에 사용된다는 것이 현재 꼽아.. 2024. 2. 16.
[그리디 #14] BOJ 16953 - A -> B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A ㅁ 인 경우에 정답을 피해갈 수 있다. 여기서 착안한 것이 b를 기준으로 해보자는 것. b를 기준으로 끝이 1이면 띄어 버리면 된다. 근데 여기서도 문제가 존재한다. 예를 들어 11 33을 보자. 정답은 당연히 -1이다. 그러나 33/2를 하면 소수부분이 날라가기 때문에, 2로 나누어 떨어질때만 /2 를 하도록 설정 정리하자면. 1) if(b%10 == 1) { b/=10 } 2) else if(b%2 == 0) { b/=2.. 2024. 2. 14.
[그리디 #13] BOJ 13164 - 행복 유치원 https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들 www.acmicpc.net 1차 시도 예제를 토대로 알고리즘을 설계했다. 1. 가장 큰 것을 하나로 만듬 2. 두 개씩 묶는 것이 무조건 이득 위 알고리즘에는 크나큰 실수가 있다. 5 2 1 5 6 7 8 라는 반례가 존재한다. 조의 개수 K가 커지면 위의 알고리즘이 성립하지만, K가 적은 수일 경우 적용되지 않을 수 있다. { 1 } , { 5 6 7 8 } -> 정답: 4 { 1 5 6 7 } ,.. 2024. 2. 14.
[그리디 #12] BOJ 20365 - 블로그2 https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 1차 시도 예제에 있는 문장을 보고 어그로(?)에 끌려 이상하게 접근을 했다. 하지만, 1~7번 문제를 파란색, 3번을 빨간색, 5번을 빨간색, 8번을 빨간색으로 순서대로 칠한다면 작업 횟수는 4번으로 가장 적다. 위 문장에서 먼저 파란색으로 칠한 다는 것 때문에, 무조건 밑 바탕을 칠하고 가야한다고 생각했다. 따라서, 다음과 같은 알고리즘을 설계함. 1. 가장 많은 색을 바탕으로 깔고 들어간다.. 2024. 2. 13.

티스토리툴바