나쿠리 개발 메모장

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

개요 유니온 파인드(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 배열을 만들었다. 계속..