https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 구간이 정해져있어서 누적합이나 슬라이딩 윈도우로 풀면 용이한 문제이다. 쉬운 문제인데, 갱신 부분에서 variable을 잘못 썼다..ㅠ 흑흑 제발 이상한 실수 좀 하지 말자.. #include #include using namespace std; int main() { int n, x; cin >> n >> x; vector visitors(n); for(int i = 0;i < n;i++..

https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제의 완벽한 탐색이라는 게 있는데, 그건 최소 횟수로 돌을 가져온다는 뜻이다. 이 문제는 크게 2가지 풀이 방식이 있다. 1. 홀/짝 구분 2. 다이나믹 프로그래밍 압도적으로 1번이 편리하지만, 학습을 위해 2가지 방식 모두 시도하였다. 1번 풀이 각자 1개 또는 3개를 가져갈 수 있으므로 4n개 기준으로 케이스를 나눌 수 있다. 4n, 4n + 2의 경우 반드시 창영이가 승리하고, 4n + 1, 4n + 3의 경우 반드시 상근이가 승리한다. 이러한 경우를 고려해 홀수의 경우 상근이, 짝수의 경우 창영이가 승리한다는..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 제목 그대로 최소 힙을 구현하면 쉽게 풀 수 있는 문제이다. minheap을 구현하기 위해 STL의 priority_queue를 활용한다. 하지만 기본적으로 max heap이기 때문에 greater를 활용해야 한다. #include #include #include using namespace std; priority_queue q; int main() { ios_base::sy..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 처음에 문제 초반만 보면 최소 스패닝 트리 등 탐색을 해야하나 싶지만 그렇지 않다. 각 도시의 연결성만 확인하면 되므로 유니온 파인드 알고리즘을 사용하였다. 이 때 parent 갱신을 주의하면 무난하게 풀 수 있는 문제이다. #include using namespace std; int city[201][201]; int parents[201]; int Find(int idx) { if(idx ==..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 보자마자 투포인터로 인식은 했으나 양 포인터를 어떻게 움직일지에 대해 조금 더 고민했던 문제이다. 물론 틀릴 정도로는 어렵지 않다. 휴리스틱하게 생각해봐도 떠올리기 쉬운 기준이다. 두 용액의 합이 최대한 0에 가까워야하므로, 왼쪽, 오른쪽 포인터를 비교했을 때 0으로부터 먼 포인터를 안쪽으로 이동시킨다. #include #include #include using namespace std; i..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 크게 2가지 방식으로 문제를 풀어보았다. 첫 번째는 최소 길이를 구하는 만큼 다익스트라 알고리즘으로, 두 번째는 문제의 목적에 더 부합하는 풀이 방식인 다이나믹 프로그래밍으로 풀었다. 다익스트라의 경우 약간의 변형이 필요하다. 이웃한 점은 서로 인접, 연결되어있다는 가정 하에 한 차례 갱신이 더 필요하다. #include #include #include using namespace st..