메모장

개요 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 골드4 난이도 문제다. 풀이 노드간 연결 여부를 확인하는 문제다. BFS를 통해 풀 수도 있겠지만 이번에는 유니온 파인드(disjoint-set)를 이용했다. 같은 경로의 경우 같은 루트 노드를 갖고 있으므로 이를 비교하면 된다. 기본적인 유니온 파인드로 구현이 가능했다. 코드 #include #include using namespace std; constexpr int N_LIMIT = 2..

개요 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 골드2 난이도 문제다. 풀이 문자열과 분리 집합의 형태를 보아하니 유니온 파인드와 map 자료구조로 해결할 수 있을 것 같다고 판단했다. map[current].id = parent 의 형식으로 데이터를 저장했다. 친구 네트워크가 연결될 때마다 루트 노드의 cnt를 연결된 네트워크의 친구의 수 만큼 증가시켰고, cnt가 낮은 네트워크를 높은 네트워크에 넣도록 했다. 그 후 루트 노..

개요 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 골드4 난이도 문제다. 풀이 유니온 파인드 그 자체인 문제다. 유니온 파인드에 필요한 Initialize, FInd, Union 기능을 구현하면 된다. Find 함수에서 경로 압축 최적화를 통해 연산 시간을 줄였다.(Path Compression) Union 함수에서는 레벨이 낮은 트리가 높은 트리에 들어갈 수 있도록 최적화 했다.(Union-by-ran..

개요 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 골드4 난이도 문제다. 풀이 문제를 보고 딱 큐가 떠올랐다. 머리가 늘어나고 꼬리가 사라지는 선입선출 구조! 이동하며 머리가 한 칸 늘어난다.(queue에 push) 이동한 곳에 아무것도 없는 경우 꼬리를 줄이고(queue를 pop) 사과가 있을 경우에는 그대로 진행한다. 만약 뱀 자기 자신이나 벽이 있으면 게임 오버 처리를 해준다. 방향은 1차원 배열을 따로 만들어서 index를 time으로 사용..

개요 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 골드5 난이도 문제다. 풀이 투 포인터로 풀어낼 수 있다. 배열을 정렬 후 양끝에서 각 포인터를 시작한다. 두 포인터의 합이 K보다 큰 경우 큰 쪽 포인터를 작은 쪽으로 이동시키고, 반대로 작은 경우 작은 쪽 포인터를 움직인다. K와 두 포인터 합의 절댓값을 비교한다. 기존 가장 가까운 합보다 더 가까우면 카운트를 1로 만들고 가장 가까운 값을 바꾸어준다. 가장 가까운 값과 동일한 경우 카운트..

개요 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 골드4 난이도 문제다. 풀이 투 포인터를 이용하면 간단하게 풀 수 있다. N sum) front++; else if (A[i] sync_with_stdio(0); cin >> N; for (int i = 0; i > A[i]; sort(A, A + N); TwoPointers(); cout

개요 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 골드2 난이도 문제다. 풀이 배열 4개에서 합이 0인 경우의 수를 구해야 한다. nsync_with_stdio(0); cin >> n; AB.reserve(n * n); CD.reserve(n * n); for (int i = 0; i > A[i] >> B[i] >> C[i] >> D[i]; for (int i = 0; i < n; i++) { f..

개요 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 골드3 난이도 문제다. 풀이 2467번 용액 위 문제와 유사하지만 한 번 더 생각해야 하는 문제다. 3개의 용액을 합성해서 0에 가까운 경우를 구해야 한다. 투 포인터는 O(N)의 시간복잡도를 가진다. 따라서 앞에서부터 모든 원소를 기준으로 한 번씩 잡고, 해당 윈소 이후를 기준으로 양 끝에 투 포인터를 일일이 돌려준다면 O(N^2)가 나올 것이다. N abs(sum))..

개요 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]만 해주면 된다. 이게 슬라이딩 윈도우였다..