나쿠리 개발 메모장

개요 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 골드5 난이도 문제다. 풀이 가중치 그래프 문제로 기본적인 다익스트라 알고리즘 문제 유형이다. V> N >> M; for (int i = 0; i > a >> b >> c; graph[a].push_back({ b, c }); graph[b].push_back({ a, c }); } Dijkstra(); cout

개요 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 골드4 난이도 문제다. 풀이 유니온 파인드로 해결할 수 있다. 진실을 아는 사람의 parent를 -1로 초기화하고, 이를 루트 노드로 사용했다. 파티에 2명이상 있는 경우 Union 연산으로 합쳐주었다. 진실을 아는 사람과 같은 파티에 참석한 사람은 모두 진실을 아는 사람이 된다. (해당 파티에서 진실을 듣기 때문) 때문에 파티들의 첫 번째 손님의 루트 노드를 Find하며 거짓말 할 수 있는 파티인지 ..

개요 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))..