본문 바로가기

백준

(14)
[Baekjoon] 1260 - DFS와 BFS (C++) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 그래프 탐색 알고리즘의 가장 기본이라고 할 수 있는 DFS(depth-first search)와 BFS(breadth-first search)를 단순히 구현만 하면 되는 간단한 문제입니다. 그래프의 경우 입력으로 들어오는 정점의 개수가 최대 1,000개로 그리 크지 않기 때문에 인접 행..
[Baekjoon] 10844 - 쉬운 계단 수 (C++) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 여러 문제를 풀다 보니 이제 슬슬 DP(dynamic programming)에 익숙해지는 것 같습니다. 이번 문제도 DP를 이용한 문제입니다. 처음에는 N에 따라서 계단 수의 개수 규칙을 바로 찾으려고 했지만, 2차원 배열을 사용해 전체 개수가 아닌 각 첫째 자릿수의 개수를 찾는 방식으로 쉽게 풀 수 있었습니다. 먼저 예를 들어 볼까요? N이 1인 경우에서 3인 경우까지 직접 모든 경우의 수를 나열해 보겠습니다. N = 1 N = 2 N = 3 1 10, 12 101, 121, 123 2 21, 23 210, ..
[Baekjoon] 1759 - 암호 만들기 (C++) https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 알고리즘 분류는 백트래킹(backtracking)으로 되어 있지만, 입력으로 들어오는 데이터의 크기가 그렇게 크지 않기 때문에 완전 탐색(brute-force search)이나 그냥 모든 경우의 수를 DFS(depth-first search) 방법으로 다 확인하면서 해도 쉽게 해결할 수 있습니다. 하지만 그냥 문제 취지에 맞게 백트래킹을 이용해 풀어 보았습니다. 방법은 간단합니다. 먼저 입력으로 들어오..
[Baekjoon] 11053 - 가장 긴 증가하는 부분 수열 (C++) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 처음엔 꽤나 고민했던 문제였지만, DP(dynamic programming) 태그가 붙은 것을 보고 간단히 구현해서 풀 수 있었습니다. 이런 문제를 풀면서 느낀 게 DP 기법을 이용하면 복잡해 보이는 문제도 제법 간단한 코드로 구현할 수 있는 것 같더라고요. 생각보다 강력한 기법인 것 같습니다. 아직..
[Baekjoon] 14503 - 로봇 청소기 (C++) https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음 www.acmicpc.net 생각보다 크게 어려웠던 문제는 아니었습니다. 로봇 청소기의 작동 조건이 문제에 명확하게 나와있었기 때문에 이를 그대로 코딩으로 구..
[Baekjoon] 14502 - 연구소 (C++) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 벽이 세워질 수 있는 모든 경우의 수를 고려하여 풀었습니다. 매번 벽을 세운 뒤에 바이러스를 확산시킨 후, 빈 공간을 계산하는 방식으로 풀..