본문 바로가기

PS

백준 20052번 괄호 문자열? https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 풀이 유니온 파인드를 이용한 풀이와 세그먼트 트리를 이용한 풀이가 있습니다. 유니온 파인드 풀이는 제가 구상했고, 세그먼트 트리 풀이는 다른 분의 도움을 받았습니다. 풀이 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,.. 더보기
Codeforces Round #672 (Div. 2) A~C1번 풀이 얼마 전 Codeforces Round #672 (Div. 2)에 참가했습니다. 처음으로 문제를 3개나 풀어서 행복했습니다. 그래서 대회 중 풀었던 A번, B번, C1번의 풀이를 써 보려 합니다. A번 - Cubes Sorting 문제 Problem - A - Codeforces codeforces.com 문제 설명 $N$개의 정육면체가 한 줄로 놓여 있을 때, 부피가 큰 순으로 정렬한다고 합니다. 단, 두 인접한 정육면체를 교환하는 작업만 할 수 있습니다. 각 정육면체의 부피가 주어질 때, 정렬을 위해 필요한 최소 교환 횟수가 $\frac{N\times (N-1)}{2}$회 미만이라면 YES, 아니면 NO를 출력하는 문제입니다. 풀이 두 인접한 원소만 교환하여 정렬하는 알고리즘으로는 버블 정렬이 있습니.. 더보기
백준 2981번 검문 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간�� www.acmicpc.net 풀이 N개의 수 중 i번째 수를 $a_i$라고, 구하고자 하는 값을 $M$이라고 하겠습니다. N개의 수는 $M$으로 나눈 나머지가 모두 같아야 하므로 이때의 나머지를 $k$라고 하면 $1\leq i\leq N$인 모든 $i$에 대해 $a_i - k$는 $M$의 배수입니다. 따라서 N개의 수 중 어떤 두 수를 잡더라도 두 수의 차는 $M$의 배수가 됩니다. 즉, $1\leq i, j\leq N$인 모든 $i, .. 더보기
백준 10888번 두 섬간의 이동 https://www.acmicpc.net/problem/10888 10888번: 두 섬간의 이동 1에서 N까지 번호가 붙은 N개의 섬이 일렬로 쭉 늘어서 있다. 이 섬들 간에는 아직 다리가 없어서 배로만 이동을 해야 했기에 매우 불편했다. 그렇기에 정부에서는 이 섬들에 다리를 연결하고자 � www.acmicpc.net 무려 열두 번 틀린 문제입니다. 그렇다고 어려운 문제는 아닙니다.. 풀이 방법 임의의 A개의 섬이 A-1개의 다리를 통해 모두 연결되어 있다면, 이 A개의 섬에 대해 연결된 쌍의 개수와 최소 다리 개수의 합을 구할 수 있습니다. 1. 쌍의 개수 A×(A-1) / 2 = 쌍의 개수입니다. 2. 최소 다리 개수의 합 섬 A개가 모두 연결되어 있을 때, 다리 1개를 거쳐 연결되어 있는 쌍의 개.. 더보기
백준 2660번 회장 뽑기 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 각 회원을 정점으로, 친구사이를 가중치가 1인 간선으로 생각하면 회원의 점수는 그 회원과 가장 멀리 떨어진 정점과의 거리가 됩니다. 이를 구하려면 모든 회원 간의 관계 (모든 정점 사이의 거리) 를 알아야 하므로 플로이드-와샬 알고리즘을 적용하였습니다. 정점의 수가 N일 때 O(N^3)인 알고리즘이지만 회원의 수 (정점의 수) 가 최대 50이므로 사용할 수 있습니다. 코드 1234567891.. 더보기

티스토리툴바