본문 바로가기

알고리즘 온라인 저지/BOJ

 (34)
BOJ 2294번 동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net DP(= 동적 계획법)를 이용하면 해결 가능한 DP의 기본 문제다. DP에 대해 전혀 모른다면 더보기의 알고리즘 설명 포스팅을 먼저 읽어보자. 더보기 알고리즘 : 동적 계획법 (Dynamic Programming, DP) 동적 계획법 (이하 DP)은 문제를 풀 때 (단지 알고리즘 문제에 국한되지 않는다, 일상생활에서도 우리는 DP를 하고 있다.) 메모리를 추가로 사용하여 속도를 얻는 방법이다. (일상생활에서 메모리 dev-game-..
BOJ 7579번 앱 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net DP를 이용한 문제이다. 일반적으로 이러한 문제를 만나면, 확보되는 메모리를 인덱스로한다. 그렇게 해야 DP 테이블을 구한 뒤 문제에서 요구하는 인덱스의 값을 바로 출력 해 줄 수 있기 때문이다. 그런데 이 문제의 경우에는 확보할 메모리의 범위가 너무 넓다 (1 ~ 10,000,000) 비용의 범위가 (0 ~ 10,000) 인 것을 감안하면 결국 2byte 이상의 변수를 이용해야 하는데 그렇게되면 DP 테이블의 크기만 거의 20MB 가 되기 때문에 꺼려진다. (msvc..
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를 기준으로 좌우 방향으로 순감소 수열이라면 그 전체를 바이토닉 수열이라고 부른다는 것이다. 우리는 임의의 수열이 있을 때, 그중 일부만을 ..

티스토리툴바