문제 풀이/Baekjoon Online Judge
-
[다이나믹 프로그래밍] Dynamic programming문제 풀이/Baekjoon Online Judge 2021. 1. 27. 21:17
1. 다이나믹 프로그래밍이란? 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고, 이를 재귀 호출 알고리즘으로 구현하면 지나친 중복이 발생할 수 있기 때문에 재귀적 중복을 해결하는 방법이다. 간단하게 말하면 작은 문제들의 값을 저장하여 재사용하는 것이다. 다이나믹 프로그래밍이라는 표기를 보면 큰 연관이 없어보이는데, 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 기억하며 풀기로 번역하였다고 한다. 2. 다이나믹 프로그래밍의 예 다이나믹 프로그래밍의 예로는 피보나치 수열이 있다. 피보나치 수는 다음과 같이 정의할 수 있다. f(n) = f(n - 1) + f(n - 2) f(1) = f(2) = 1 n의 피보나치 수에는 n - 1과 n - 2의 피보나치 수를 포함하는 것을 알..
-
[Baekjoon Online Judge] 10798번: 세로읽기문제 풀이/Baekjoon Online Judge 2021. 1. 24. 21:52
10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 요구사항 A A B C D D a f z z 0 9 1 2 1 a 8 E W g 6 P 5 h 3 k x - 한 줄의 단어는 글자들을 빈칸 없이 연속으로 나열해서 최대 15개의 글자들로 이루어진다. - 만들어진 다섯 개의 글자 개수는 서로 다를 수 있다. - 다섯 개의 단어를 세로로 읽는다. - 위 입력을 예시로 들면 Aa0aPAf985Bz1EhCz2W3D1gkD6x 이다. 입력 - 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들..
-
[Baekjoon Online Judge] 10610번: 30문제 풀이/Baekjoon Online Judge 2021. 1. 24. 21:41
10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 요구사항 - 양수 N이 주어진다. - 양수 N에 포함되어 있는 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만든다. 입력 N을 입력받는다. N는 최대 10의 5제곱의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. 30의 배수가 되기 위해서는 각 자리수의 합이 3으로 나누어 떨어져야 하고, 적어도 하나의 0이 포함되어야 한다. 30의 곱을 확인해보면..
-
[Baekjoon Online Judge] 4949번: 균형잡힌 세상문제 풀이/Baekjoon Online Judge 2021. 1. 23. 14:54
4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 요구사항 - 어떤 문자열이 주어졌을 때, 괄호들이 균형이 잘 맞춰져 있는지 판단하는 프로그램 - 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. - 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. - 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다. - 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다...
-
[Baekjoon Online Judge] 1764번: 듣보잡문제 풀이/Baekjoon Online Judge 2021. 1. 20. 20:54
1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 요구사항 - 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어진다. - 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성한다. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자..
-
[Baekjoon Online Judge] 2468번: 안전 영역문제 풀이/Baekjoon Online Judge 2021. 1. 20. 20:17
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 요구사항 - 어떤 지역의 높이를 파악한다. - 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개 만들어 지는 지를 조사한다. - 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다. - 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산한다. - 단, 아무 지역도 물에 잠기지 않을 수도 있다. 높이가 0 이하 일 때 입력 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 ..
-
[Baekjoon Online Judge] 4963번: 섬의 개수문제 풀이/Baekjoon Online Judge 2021. 1. 19. 17:50
4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 요구사항 - 정사각형으로 이루어진 섬과 바다 지도가 주어진다. - 한 정사각현과 가로, 세로, 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. - 1은 땅이고, 0은 바다이다. - 섬의 개수를 세어 출력한다. 입력 - 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. - w와 h는 50보다 작거나 같은 양의 정수이다. - 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅..
-
[Baekjoon Online Judge] 14502번: 연구소문제 풀이/Baekjoon Online Judge 2021. 1. 19. 17:46
14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 요구사항 - 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. - 연구소는 크기가 N x M인 직사각형으로 나타낼 수 있다. - 연구소는 빈 칸, 벽으로 이루어져 있다. 벽은 칸 하나를 차지한다. - 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우 인접한 빈 칸으로 모두 퍼져나갈 수 있다. - 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. - 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 입력 - 첫째 줄에 지도의 세로 크기 N..