본문 바로가기

전체 글

백준 4195번 친구 네트워크 http://icpc.me/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 Union-find와 map STL을 사용해 풀었습니다. 사용자가 문자열 이름이 아닌 번호로 주어졌다고 가정합시다. 이러한 경우에는 Union-find로 각 사용자와 친구 네트워크의 크기를 관리하며 쉽게 풀 수 있습니다. union-find 트리를 나타낼 배열과 각 사용자의 친구 네트워크의 크기를 나타낼 배열이 필요합니다. 두 사용자가 친구 관계를 맺으면 union연산을 통해 두 사용자가 속해 있는 친구 네트워.. 더보기
백준 1422번 숫자의 신 http://icpc.me/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보 www.acmicpc.net 풀이 뒤에서 설명할 비교 연산을 편하게 하기 위해 n개의 수를 문자열 자료형으로 받습니다. k개의 수 중 가장 길이가 길고 큰 수를 최대한 많이 반복하는 것이 이득입니다. 따라서 길이순(길이가 같다면 크기순)으로 정렬하여 n - k번 반복할 수를 먼저 선택하고, 정답을 나타낼 벡터에 선택한 수를 n - k번 넣고 k개의 수를 모두 하나씩 넣습니다. 이후 선택한 n개의 수로 가장 큰 수를 만들 수 있도.. 더보기
백준 13306번 트리 https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 풀이 마지막에 받은 쿼리부터 역순으로 실행하는 것이 풀이의 핵심입니다. 트리의 간선을 끊는 동작은 처리하기 어렵지만, 두 정점을 잇는 연산은 유니온 파인드를 통해 쉽게 할 수 있기 때문입니다. 따라서 트리에서 간선을 하나씩 끊는 것이 아니라 모든 정점이 연결되지 않은 상태에서 쿼리를 역순으로 보며 각 쿼리에 대해 다음과 같이 실행합니다. 쿼리 1 : 0 b 원래 명령과 반대.. 더보기
백준 20052번 괄호 문자열? https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 풀이 유니온 파인드를 이용한 풀이와 세그먼트 트리를 이용한 풀이가 있습니다. 유니온 파인드 풀이는 제가 구상했고, 세그먼트 트리 풀이는 다른 분의 도움을 받았습니다. 풀이 1(유니온 파인드 이용) 이 풀이의 핵심은 유니온 파인드를 이용해 이어져 있는 괄호쌍을 하나로 묶어 관리하는 것입니다. 입력받은 괄호 문자열을 탐색하며 이어져 있는 괄호쌍을 묶는 작업을 마치면 아래 그림처럼 괄호 문.. 더보기
백준 1781번 컵라면 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라� www.acmicpc.net 문제 설명 문제가 N개 주어지며, 각각의 문제마다 데드라인과 받을 수 있는 컵라면 수가 있습니다. 문제를 데드라인 안에 해결하면 컵라면을 받을 수 있습니다. 모든 문제의 데드라인은 N 이하이며, 푸는데는 1만큼의 시간이 필요합니다. 이때 받을 수 있는 컵라면의 최대 수를 구하는 문제입니다. 풀이 데드라인을 이미 넘긴 문제는 풀 필요가 없으므로, 풀어야 할 문제를 골라야 합니다. 데드라인 순서대로 문제를 .. 더보기
백준 17298번 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 설명 길이가 $N$인 수열 A가 주어집니다. A의 i번째 원소 $A_i$의 오큰수는 자신보다 오른쪽에 있고 큰 수 중 가장 가까운 수입니다. 수열의 모든 원소의 오큰수를 찾아 출력하는 문제입니다. 풀이 각 원소의 오큰수를 찾을 때마다 오른쪽 원소를 모두 탐색하면 $O(N^2)$로 시간초과일 것입니다. 스택을 이용하면 $O(N)$만에 모든 원소의 오큰수를 찾을 수 있습니다. 수열 A의 오른쪽에서부터 원소를 .. 더보기
Codeforces Raif Round 1 (Div. 1 + Div. 2) A~C번 풀이 중간고사가 4일 남았는데 참가했습니다. 대회 중 A~C번을 풀었습니다. 중간고사ㅠㅠㅠㅠㅠ A번 - Box is Pull 문제 Problem - A - Codeforces codeforces.com 문제 설명 $(x_1, y_1)$의 박스를 $(x_2, y_2)$로 끌고 가려 합니다. 박스와 인접해 있을 때 박스를 끌면 박스는 내가 있던 위치로 이동하고, 나는 박스 반대편으로 한 칸 이동합니다. 박스를 끌지 않고도 한 번에 한 칸씩 움직일 수 있으며, 내 처음 위치는 마음대로 정할 수 있습니다. 이때 박스를 $(x_1, y_1)$에서 $(x_2, y_2)$로 옮기기 위해 필요한 최소 이동 횟수를 구하는 문제입니다. 풀이 만약 출발지와 목적지의 x좌표가 같다면 y좌표의 차이가 이동 횟수가 됩니다. 마찬가지로.. 더보기
백준 2436번 공약수 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 두 정수 $A$, $B$가 주어질 때 $A$가 최대공약수, $B$가 최소공배수인 두 수를 찾는 문제입니다. 풀이 조건에 맞는 두 수를 $N$, $M$이라고 하면 $N, M$의 최대공약수는 $A$, 최소공배수는 $B$이므로 $A\times i = N, A\times j = M$ (단, $i, j$는 서로소) $N\times k = B, M\times l = B$ (단, $k, l$은 서로소) $N,.. 더보기

티스토리툴바