공부하자

https://www.acmicpc.net/problem/6497난이도는 그렇게 높진 않았는데, 문제 자체에 함정이 몇 개 정도 있는 문제였던 것 같다. 질문 게시판에도 여럿 문제의 입력과 출력 조건에 대해 까다로워 하는 모습이 보였다. 다음은 질문게시판에 있는 한 글을 발췌한 것이다.  https://www.acmicpc.net/board/view/1453601. 제시된 예제는 테스트 케이스가 하나입니다만, 0 0이 등장하기 전에 테스트 케이스가 여러 개가 있을 수 있으므로, 각 테스트 케이스에 대한 정답을 차례차례 저장해두어야 합니다.2. 모든 정답은 '0 0'이 입력된 이후에 순차적으로 출력해야 합니다. (댓글 보고 추가: 하나씩 출력하는 것도 가능하다면 이 항목은 무시하셔도 됩니다.)=> 수정 :..

https://www.acmicpc.net/problem/1647최소 신장 트리, MST를 다루는 기본적인 문제이다.인접리스트 형태로 주어지는 그래프에 대해 MST를 생성하면 되는 문제인데, 한가지 조건이 더 붙었다. 해당 MST를 두 집합으로 나누어서 가중치의 합이 가장 적은 MST 형태를 만들어 내면 되는 것이다. 당연히 그래프를 둘로 나누고 할 필요없이 결론적으로는 MST를 생성하여 구해진 가중치의 합에서 가장 가중치가 큰 간선을 빼주면 된다.이렇게 방향성을 잡고 풀면 되는데 MST 구현에는 보통 두가지 접근 방식이 있다. 하나는 프림 알고리즘 (Prim's Algorithm) 이고, 다른 하나는 크루스칼 알고리즘 (Kruskal's Algorithm) 이다. 전자는 우선순위 큐와 방문여부를 체크하..

https://www.acmicpc.net/problem/2268세그먼트 트리의 가장 대표격이라 할 수 있는 구간합 구하기 문제이다.하지만 이 문제에서 유의해야 할 부분이 두가지가 있는데,1. (i > j일 경우에는 A[j] + A[j+1] + ... + A[i]) A가 주어졌을 때, Sum(i, j)를 구하는 것은 매우 쉬운 문제이다. 라고 나와있듯, 이 문제에서는 i > j 인 경우 말고도 i 2. 최대가 1,000,000인 경우까지 다루다 보니, 자료형을 신경써야한다. 물론 이는 세그먼트 트리 문제를 풀다보면 어지간해선 다 long long형을 쓰기 마련이지만, 필자는 그냥 아무생각 없이 int로 처음에 풀었다가 틀렸다...이 두 부분만 주의해서 풀면 나머지는 세그먼트 트리를 이용해 부분합을 구하는..

https://www.acmicpc.net/problem/2357시간초과가 나지 않게 세그먼트 트리를 사용해서 푸는 것이 핵심인 문제이다. 필자 또한 처음 풀때 별 생각없이 그냥 벡터 인덱스 접근해서 풀었다가 시간초과가 났다. 생각해보니, 입력값의 최대크기가 100,000이고 애초에 그렇게 해서 풀렸다면 골드1일 이유가 없다. 따라서 시간초과가 나지 않게 하기 위해서는 세그먼트 트리를 이용해서 풀어야한다.보통 세그먼트 트리를 이용해서 푸는 문제들은 보통 구간 합을 구하거나 구성된 트리를 업데이트 하는 그런 문제들이 많은데 (BOJ #2042같은 문제가 대표적) 이 문제는 꼭 구간합을 구하는 문제가 아니더라도 세그먼트 트리를 활용하여 트리를 탐색해야 하는 문제이다.필자는 최솟값을 저장하는 트리와 최댓값을 ..

https://www.acmicpc.net/problem/3197  BFS를 응용한 조금 난이도가 있는 문제이다. 확실히 실버나 골드 문제에 비해 플래티넘 난이도로 올라가다 보니 쉽지않았던 것 같다.필자가 해결한 방법은 이분 탐색을 이용한 풀이인데, 이 풀이의 핵심은 'N일차에 백조들이 만나지 못한다면, N일 전의 날들은 백조들이 모두 만날 수 없다는 점' 을 이용하는 것이다. 이를 이용하기 위해, 미리 얼음이 녹는 날에 대한 계산을 해야 한다. 즉, 1일차에 녹는 얼음, 2일차에 녹는 얼음 ... 이런 식으로 얼음에 번호를 부여하면 가장 마지막에 녹는 얼음을 구할 수 있고, 0일 차부터 마지막 날까지에 대해 이분 탐색을 진행할 수 있다. 테스트 케이스로 주어진 맵을 얼음이 녹는 날로 나타내면, 다음과 ..