문제 https://www.acmicpc.net/problem/24042 24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 풀이 다익스트라를 응용한 문제입니다. 일반적인 다익스트라 문제에서는 노드 간의 거리 비용을 가중치로 둡니다. 이 문제에서는 횡단 보도를 건너기 위해 기다려야하는 총 시간을 가중치로 두는 것이 핵심입니다. 특히, 이 문제에서는 M이라는 주기 변수가 있습니다. 그래서 다음 노드로 진행하기전에 이 부분을 체크해주어야합니다. 주기 M을 고려하여 다음 노드로 이동하기 위해 기다려야 하는 시간을 계산..
분류 전체보기
문제 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 슬라이딩 윈도우 문제입니다. N의 input size가 30,000이기 때문에 for 문을 2번 돌게 되면 시간 제한 1초를 넘기게 됩니다. 관건은 초밥의 개수가 아닌 종류를 세야하는 것인데, 이는 Map 자료형을 통해 해결했습니다. map에서 key를 초밥의 종류로, value를 종류 당 개수로 지정해주고, 종류 카운트는 map.size를 통해 ..
문제 https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 풀이 슬라이딩 윈도우 기법을 활용한 문제입니다. N의 input size가 250,000이기 때문에 for문을 두 번 돌면 제한 시간인 1초가 훨씬 넘어가게 됩니다. 한 칸씩 이동하며 앞의 칸은 sum에서 빼고, 뒤의 칸은 sum에 더하는 방식으로 슬라이딩 윈도우 기법을 활용했습니다. 그리고 기간이 몇 개인지도 정해야하는데, 이것은 map 자료형을 통해 key를 sum 값으로, 그리고..
문제https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일www.acmicpc.net풀이 전형적인 크루스칼 문제입니다. 가중치 값이 소수라는 것이 조금은 특이합니다. 우선 입력받는 좌표 값을 stars 라는 ArrayList 에 입력받고, 이 값을 edgeList라는 ArrayList에서 연결했습니다. 이 때, 제공되는 좌표를 가중치(거리)로써 필요한 것에 집중하고, 두 쌍의 좌표는 하나의 인덱스(i or j)로 ArrayList에 입력을 해주었습니다. 그렇게 인덱스를 통해 서..
문제 https://www.acmicpc.net/problem/19949 19949번: 영재의 시험 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행 www.acmicpc.net 풀이 백트래킹을 이용한 문제입니다. 백트래킹 메서드에 매개변수로 찍었는데 맞은 정답의 수, 현재의 인덱스, 찍은 배열을 전달했습니다. 이 때 조건에 따라 정답의 수가 5개가 넘으면 ans++를 통해 답을 구합니다. 그리고 3개 이상 연속된 수를 고를 수는 없다는 조건에 맞게 idx가 2이상일 때는 만약 앞의 idx의 값이 두 번 연속되었다면, 그 수는 다음에서 선택할 수 없도록, ban이라는 변수..
문제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 문제의 조건에서 N의 input size가 최대 10,000 입니다. 만약 배열을 두 번 돌게 된다면 시간 복잡도 O(N^2)는 1억으로 1초가 넘어가 문제의 시간 제한 조건인 0.5초를 넘어가게 됩니다. 그래서 이 문제는 투 포인터를 통해 접근해야 합니다. 매커니즘의 순서는 다음과 같습니다. 1. 만약 sum이 M과 같다면, cnt를 증가시키고..
