본문 바로가기

BOJ

백준 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의 오른쪽에서부터 원소를 .. 더보기
백준 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,.. 더보기
백준 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.. 더보기
백준 1655번 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 N개의 정수를 입력받아 1번째, 2번째, ... N번째 정수까지만 보았을 때 각각의 중앙값들을 출력하는 문제입니다. 풀이 단순히 배열을 사용하여 입력받을 때마다 배열을 정렬한다면 O(N^2)이므로 시간초과일 것입니다. 힙을 이용하여 O(NlogN)으로 해결할 수 있습니다. 지금까지 입력받은 수 중 절반의 작은 수들은 최대 힙에, 나머지 절반의 큰 수들은 최소 힙에 저장합니다... 더보기

티스토리툴바