공부하자

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

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

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 재귀함수 호출을 통해 해결해야 하는 문제이다. 처음엔 주어진 전체 넓이 N을 탐색하다가 조건에 맞지 않으면 재귀적 호출을 통해 4등분된 넓이들을 조건에 맞는 모양이 나올때까지 탐색해야한다. 만들어진 코드 자체는 간단하게 보여도, 매커니즘을 떠올리는것이 좀 어려웠다. 특히 재귀함수에 전달할 인자들을 설정하고 범위를 지정해주는것에 많은 시간을 할애했던 것 같다. 재귀함수 문..

https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 우선순위 큐를 활용하여 구현하면 되는 문제이다. 우선순위 큐에 대한 자세한 설명은 필자가 이전에 정리해둔 내용이 있으니 참고하도록 하자. https://jhoon-study.tistory.com/75 [C++] STL priority_queue 사용법 priority queue C++ STL 컨테이너 중 하나로, 내부적으로 힙 자료구조로 구현된 우선순위 큐를 보다 편하게 사용할..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 자체는 간단한 문제이지만, 문제를 보자마자 딱 떠오른 그 방법으로 풀면 무조건 시간초과에 걸리는 문제이다. 보자마자 딱 떠오른 방법이란, 일단 주어지는 배열을 입력받고, 이후에 입력되는 인자들로 하여금 배열에 접근하여 부분 합을 생으로 구하는 방법일텐데,,, 문제 자체의 시간 제한이 1초인데 비해 해당 매커니즘의 wosrt-case가 100억이다... M번 반복되는 반..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 인접리스트 형태로 주어진 그래프에서 Depth가 4 이상인 정점이 존재하는지 판별하는 문제이다. 이를 해결하려면 DFS 탐색에 이어 백트래킹 기법을 활용하여 해결해야한다. 백트래킹 Back Tracking 이란? 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다. 따라서, DFS 방식으로 정점들을 순차적으로 탐색하며 non-promising한 정점들은 제외시키고 백트래킹 기법을 사용하여 제외하기 이전의 시퀀스로 다시 돌아가서 promising한..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net DFS 활용해 얼마나 그래프를 능숙하게 탐색할 수 있는지 물어보는 문제인 것 같다. 문제 자체는 굉장히 간단하다. 입력을 통해 인접리스트 형태로 그래프를 주고, 삭제할 노드를 하나 제시해준다. 그러면 해당 노드를 삭제한 후, 남은 리프노드(더 이상 밑에 자식이 없는 자식노드) 의 개수를 세주면 된다. 코드의 매커니즘은 크게 3단계로 구성된다. 1. 주어진 입력에 따라 인접리스트 형태로 그래프..

https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 감정이입이 되는 문제다. 행렬 형식으로 주어지는 그래프에 대해 도연이의 위치를 시작점으로 BFS로 탐색하여 행렬 전체에서 P의 갯수를 찾으면 되는 문제이다. 이때 주의할 점은, O라고 해서 탐색을 하지않고 넘어가는것이 아니라, X를 제외한 모두를 탐색을 하긴 하지만 P일 경우에만 cnt를 올려주어야 한다. int BFS(int x, int y) { queue Q; Q.push(make..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 골드3 정도 난이도의 DFS + DP를 활용한 문제이다. 처음에는 BFS로 접근을 했다가 여러 경로를 모두 탐색해야 하기에 visited 배열을 사용할 수 없음을 깨닫고 DFS로 방향을 틀었다가 시간초과가 나서 DFS에 DP를 접목시킨 방법으로 풀었다... 상당히 험난한 과정을 거쳤다. 애초에 행렬의 최대 사이즈가 500x500인 250,000이고, 방향 4개를 전부 탐색해야 하는데다가 그것도 ..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 인접 리스트로 주어진 그래프를 보고 이분 그래프인지 아닌지 판별하면 된다. 이분 그래프에 대한 자세한 내용은 필자가 따로 정리해두었으니 해당 게시물 참조하면 된다. ⤵️ https://jhoon-study.tistory.com/89 [자료구조] 이분 그래프 Bipartite Graph 이분 그래프란? 인접한 정점끼리 서로 다른 두가지 집합으로만 나눈 그래프를 의미한다. 위 그림과 같이 모든 정점이..