본문 바로가기

알고리즘 온라인 저지

 (48)
BOJ 2239번 스도쿠 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net DFS를 이용해 해결 가능한 문제다. 자료를 담고 있는 컨테이너의 형태가 트리, 그래프 형태가 아니더라도 깊이 우선 탐색은 사용 할 수 있다고 생각한다. (컨테이너의 형태가 다를때, 다른 이름으로 부르는 정식 명칭이 있다면 알려주시면 감사합니다.) 아이디어는 간단하다. 좌측 상단부터 시작하여 0이 들어있는 인덱스를 찾고, 해당 인덱스에 들어갈 수 있는 숫자를 오름차순으로 넣어보며 탐색을 계속 하는 것 이다. 그렇게 모든 탐색이 끝난다면 해당 순간의 스도쿠 ..
BOJ 15711번 환상의 짝꿍 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 처음에는 그냥 소수를 구하는 문제라고 생각하여 에라토스테네스의 체 를 이용하여 풀이를 시도했다. 하지만 입력의 범위가 1012 범위이기 때문에 단순히 에라토스테네스의 체를 이용한다면 메모리 초과에 걸리게 된다. 결과적으로는 골드바흐의 추측을 추가로 이용하여 문제를 해결했다. 골드바흐의 추측 - 위키백과, 우리 모두의 백과사전 골드바흐의 추측(Goldbach's conjecture)은 오래전부터 알려진 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 개의 소수(Pr..
BOJ 11057번 오르막 수 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 그렇게 어렵지 않은 DP 문제이지만, 이러한 유형의 문제를 처음 푸는 입문자에겐 조금 어려울 수 있는 문제라고 생각한다. 규칙성만 파악할 수 있다면 문제의 해결 자체는 간단하기 때문에 규칙성 파악을 우선 해보자. 임의의 숫자 다음에 올 수 있는 숫자 (= 오르막 수 를 충족할 수 있는 숫자를)는 임의의 숫자보다 크거나, 같은 숫자만 올 수 있다. 즉 앞의 숫자가 1일 경우, 뒤에 올 수 있는 숫자는 1~9 사이의 값이며 앞의 숫..
BOJ 1389번 케빈 베이컨의 6단계 법칙 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 그래프의 탐색 문제이다. 너비 우선, 깊이 우선 둘 다 가능할 것 같지만 너비 우선 탐색의 구현이 더 간단하여 BFS를 사용하였다. 문제의 예시는 좌측과 같은 형태의 그래프로 표현 가능하다. 각 간선의 비용을 1이라 가정하고, N번 노드에서 출발하여 다른 노드들로 이동하는 비용의 합이 N번 노드의 케빈 베이컨 수 가 된다. BFS를 이용해 1번 노드의 케빈 베이컨 수 를 구해보자. 1번 노드에서 1번 노드로 이동하..
BOJ 7576 토마토 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이전에 포스팅했던 미로 탐색 문제와 거의 동일한 문제이다. 큐 자료구조를 이용한 BFS를 한번 더 포스팅하고자 한다. 이번에는 날짜를 다루는 변수를 큐에 넣지 않고 진행한다. 위와 같은 2x2 행렬을 이용하며, 문제의 입력 예제 중 3번을 이용하고자 한다. 입력을 받을 때, 0의 개수를 카운팅 하여 현재 익지 않은 토마토의 개수를 가지고 있어야 -1 (= 모두 익히는 방법이 없음)을 처리할 수 있다. 이전 포스팅과 동일하게 큐를 이용하며, 왼쪽의..
BOJ 11054 가장 긴 바이토닉 부분 수열 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제를 풀기 위해서는 증가하는 부분 수열과, 감소하는 부분 수열을 각각 계산하여 합하는 것이 가장 간단해 보였다. 문제의 입력값을 위와 같이 표현할 것이다. 그림의 표는 순서대로 입력된 값들을 의미하며 표 위의 막대들은 해당 값을 가시성 좋게 높이로 표현한 것이다. 또한, 문제에서 명시된 바이토닉 부분 수열의 정의는 아래와 같다. 즉 어떤 수 k를 기준으로 좌우 방향으로 순감소 수열이라면 그 전체를 바이토닉 수열이라고 부른다는 것이다. 우리는 임의의 수열이 있을 때, 그중 일부만을 ..
BOJ 2042번 구간 합 구하기 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 본 문제는 세그먼트 트리라는 자료구조를 알고 있는가 없는가를 묻는 문제이다. 올바른 자료구조를 사용할 경우 별도의 조작 없이 바로 정답을 얻을 수 있기 때문에 세그먼트 트리의 튜토리얼 문제라고 볼 수 있다. 그렇기 때문에 트리의 개념과, 이진트리를 선행적으로 알고 있어야 한다. 추가로 배열을 이용해 이진트리를 구현했기 때문에 배열을 이용한 이진트리의 구현에 대해서도 선행적으로 알고 있으면 도움이 된다. ..
BOJ 16964 DFS 스페셜 저지 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 일반적인 DFS가 아닌, 주어진 입력이 DFS 탐색했을 때 올바른 입력인가? 를 판정하는 문제이다. 요 근래 들어가 가장 많은 시도 끝에 정답을 띄운 문제였던 것 같다. 결국 알고리즘 자체는 DFS라 간단하지만, 아이디어를 내는 것이 어려운 문제였다. 일반적으로 트리에 노드를 삽입할때, 특정한 기준을 둔다. 다시 말해 자식 노드 두 개 있을 때 더 작은 노드가 앞에오게 하거나 (= 오름차순 정렬) 더 큰 노드가 앞에 오게 하거나..

티스토리툴바