메모장

개요 유니온 파인드(Union-Find)는 서로소 집합(Disjoint Set) 자료구조를 표현하는 알고리즘이다. Disjoint Set은 상호 배타적인(공통 원소가 없는) 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 본문 유니온 파인드 구현 유니온 파인드는 크게 세가지 연산으로 구성된다. 초기화 : N 개의 원소를 각각의 집합으로 초기화 Union : 두 개의 원소가 속한 각각의 집합을 하나로 합침 Find : 원소가 속한 집합을 반환 유니온 파인드는 배열 구현과 트리 구현으로 나뉘는데, 주로 트리 구현을 이용한다.(트리가 더 빠르다) 배열 구현 배열 기반 구현은 매우 간단하다. 초기화 : Arr[i] = i 와 같이 원소를 각자의 집합에 초기화시킨다. Union : 모든..

개요 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 골드5 난이도 문제다. 풀이 특성값의 합이 0에 가까운 두 용액을 찾아야 한다. 용액의 특성값을 정렬한 후 투 포인터를 사용해 풀었다. front(가장 작은 값)과 end(가장 큰 값) 일 비교한다. 0보다 클 경우 end-1 하여 감소시키고 0보다 클 경우 front+1을 해주어 증가시킨다. 위를 반복하며 0과 가장 가까운 조합을 찾아낸다. 여러 답중 아무거나 출력해도 되므로 그냥 출..

개요 https://www.acmicpc.net/problem/10025 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 실버3 난이도 문제다. 풀이 백곰 앨버트가 가장 많은 얼음을 취할 수 있는 최적의 위치를 찾아야 한다. 브루트포스로 접근해서 한 번 틀렸다. 생각해 보니 다 계산할 필요가 없었다. 현재 위치에서 취하는 얼음의 범위가 ice[n] ~ ice[m]라고 가정하자. 다음 범위는 ice[n+1] ~ ice[m+1]일 것이다. 다 계산할 필요 없이 현재 범위에서 -[n] + [m+1]만 해주면 된다. 이게 슬라이딩 윈도우였다..

개요 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 실버2 난이도 문제다. 풀이 2를 곱하기, 1을 가장 오른쪽에 추가하기 두 가지의 선택지가 있다. 어느 선택지가 먼저일지 알 수 없으므로 모든 경우의 수를 따져봐야 한다고 판단했다. 그래서 BFS를 사용했다. n * 10 + 1과 n *2를 큐에 넣으며 BFS 하면 된다. n의 int형 overflow 때문에 한 번 틀렸다. long long으로 해결했다. 코드 #include #include using namespace std; struct Node { long long n; int cnt; }; long long..

개요 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 골드4 탐색 문제다. 풀이 1697번 숨바꼭질 위 문제와 거의 유사하고, 차이점으로 가장 빠른 방법의 수를 추가로 출력해주어야 한다. 가장 빠른 경로가 탐색이 됐을 때, ans 변수에 시간(cnt)을 저장한다. 만약 도착지에 도착했을 때 걸린 시간과 ans의 시간이 일치할 경우 경우의 수(ansCnt)를 증가시킨다. 시간이 ans를 넘은 경우의 수는 co..

개요 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 골드4 탐색문제다. 풀이 13549번 숨바꼭질 3 위 문제와 유사하지만, 가장 빠른 경로도 함께 출력해야하는 차이점이 있다. 처음에는 원소(구조체)마다 queue route를 추가해서 원소마다 루트를 계속 추가시키고, 도착했을때 해당 원소의 route를 출력시키는 식으로 구현했다. 결과는 시간 초과,, 이전 위치를 저장하는 parent 배열을 만들었다. 계속..

개요 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 골드5 탐색 문제다. 풀이 1697번 숨바꼭질 위 문제와 거의 유사하지만 순간이동을 할때 시간이 증가하지 않는 다는 차이점이 있다. 똑같이 BFS로 풀었지만, 순간이동을 먼저 큐에 넣어주어 경우의 수를 먼저 탐색할 수 있도록 했다. 코드 #include #include using namespace std; constexpr int LIMIT = 100000;..

개요 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 실버1 탐색 문제다. 풀이 수빈이가 동생을 찾는 가장 빠른 시간을 찾는 문제이기 때문에 BFS를 사용했다. 코드 #include #include using namespace std; constexpr int LIMIT = 100000; struct Info { int x; int cnt; }; int N, K; bool visited[LIMIT + 2]; int a..

개요 두 포인터(Two Pointers) 혹은 슬라이딩 윈도우(Sliding Window)라고 부른다. 1차원 배열에서 2개의 포인터를 조작하며 값을 얻는 기법이다. 본문 예를 들어 1차원 배열에서 구간 합의 경우의 수를 찾는 문제가 있다고 하자. 위와 같이 브루트포스로 경우의 수를 찾게 된다면 O(N^2)가 될 것이다. N의 범위가 10만을 넘기기만 해도 시간 초과가 나버리게 된다. 이럴 때 필요한게 두 포인터다. 두 포인터(Two Pointers) front와 back 처럼 두 개의 포인트를 잡고 시작한다. 현재 합이 20보다 작으므로 b를 뒤로 움직여 부분합을 증가시킨다. 합이 20보다 커질 때 까지 b 포인터를 뒤로 움직인다. 20이 된 경우의 수가 있다면 count를 증가시킨다. 위처럼 합이 2..

개요 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 골드급 DFS + DP 문제다. 풀이 처음에는 재귀를 활용한 DFS로 접근했다. 모든 구간에서 DFS로 탐색했고, 최대값을 구했다. visited 배열에 판다가 이동한 값의 최대 값을 기록하며 가지치기 해줬다. (다음 칸이 현재 칸보다 높은 값일 경우 continue) 하지만 결과는 시간 초과 행렬 기반 DFS는 O(V^2)다. 500*500을 25,000이라고 착각해서,,,, 2..