본문 바로가기

BOJ

백준 2673번 교차하지 않는 원의 현들의 최대집합 http://icpc.me/2673 2673번: 교차하지 않는 원의 현들의 최대집합 평면상에 있는 원의 둘레에 100개의 점이 일정한 간격으로 시계방향으로 번호가 1, 2, ... 100으로 붙여져 있다. 이 점들을 끝점으로 갖는 N개의 선분(원의 현)이 입력으로 주어질 때, 이들중에서 서 www.acmicpc.net 풀이 원의 현이라고 하면 되게 복잡해지고 풀기 싫어집니다. 하지만 두 현의 교차 여부만 중요하다는 점을 잘 생각해 보면 현을 수평선상의 구간으로 생각해도 문제가 없다는 것을 알 수 있습니다. 두 현의 교차하려면 각 현을 나타낸 두 구간이 겹치면서 한 구간이 다른 구간에 포함되지 않아야 합니다. 아래 그림은 예제를 구간으로 나타낸 모습입니다. 여기까지 왔으면 DP로 문제를 풀 수 있습니다. .. 더보기
백준 17106번 빙고 http://icpc.me/17106 17106번: 빙고 한 줄에 5개의 글자, 총 5줄을 출력한다. 각 줄은 순서대로 빙고판의 각 행을 나타낸다. 색칠된 칸은 "#", 색칠되지 않은 칸은 "."로 따옴표 없이 나타낸다. 예를 들어 A1, C3, C4만 색칠하려면 다음과 www.acmicpc.net 풀이 25개의 빙고 칸 각각을 색칠하거나 색칠하지 않을 수 있으므로 빙고 칸을 채우는 경우의 수는 $2^{25}$가지입니다. 모든 경우를 살펴보며 각 경우의 수마다 모든 칸이 올바르게 색칠되었는지를 체크하는 코드를 작성하면 정답을 찾을 수 있습니다. 다소 문제가 되는 칸은 B5입니다. 다른 칸들은 모두 빙고판의 상태를 통해 올바르게 색칠되었는지 알 수 있지만 이 칸은 그렇지 않습니다. B5가 참이라고 가정하고.. 더보기
백준 20051번 Zagrade http://icpc.me/20051 20051번: Zagrade It is well known that the Central Intelligence Agency is tasked with gathering, processing and analyzing national security information. It is also suspected that they own quite large collections of commonly-used computer passwords and are developing some q www.acmicpc.net 문제 인터랙티브 문제입니다. 길이가 짝수인 정수 $N$이고 여는 괄호( '(' )와 닫는 괄호( '(' )의 개수가 같은 문자열이 있을 때, ? s e 쿼리로.. 더보기
백준 1071번 소트 http://icpc.me/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 풀이 간단한 그리디 문제입니다. 사전순으로 앞선 배열을 만들어야 하기 때문에 앞에서 최대한 작은 수를 사용해야 합니다. 앞서 $i$개의 수를 최적으로 출력했다고 가정할 때 가능하다면 무조건 출력하지 않은 수 중 최솟값을 출력해야 하며, 최솟값을 출력할 수 없다면 두 번째로 작은 값을 출력해야 합니다. 최솟값을 출력할 수 없는 경우는 두 가지입니다. 1) $i$번째로 출력한 수 + 1 == 최솟값일 때 2) 출력하지 않은 수에서.. 더보기
백준 20442번 ㅋㅋ루ㅋㅋ http://icpc.me/20442 20442번: ㅋㅋ루ㅋㅋ 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다. www.acmicpc.net 풀이 투 포인터를 이용하여 풀었습니다. 왼쪽에서 $i$번째 R을 기준으로 왼쪽에 있는 K의 수를 $lk[i]$, 오른쪽에 있는 K의 수를 $rk[i]$라고 하겠습니다. 이때 $l$번째 R부터 $r$번째 R까지 사용한 ㅋㅋ루ㅋㅋ문자열의 최대 길이는 $r - l + 1 + 2\times min(lk[l], rk[r])$이 됩니다. R은 $r - l + 1$개, K는 왼쪽 오른쪽 각각 $min(lk[l], rk[r])$개씩 사용할 수 있기 때문입니다. 단순히.. 더보기
백준 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 원래 명령과 반대.. 더보기

티스토리툴바