본문 바로가기

Tech/Problem Solving

[백준 1912] 연속합 (Java) https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 접근 방법 다이나믹 프로그래밍 문제였다. 입력받은 수열은 numbers 배열에 담고 dp라는 배열을 하나 더 만들었다. dp에는 i번째까지의 연속합 중 최댓값을 담았다. i번째까지의 연속합 중 최댓값은 이전까지 연속합 중 최댓값(dp[i-1])에 i번째의 수를 더한 값(numbers[i])과 i번째 수를 비교해 큰 값이 해당한다. 이전까지의 합에 현재 수를 더한 것보다 현재 수가 더 크다면 다시 새로 시작해..
[백준 14502] 연구소 (Java) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 접근 방법 1. 벽을 3개 세우는 모든 경우를 찾는다. (부르트포스) - 벽이 3개가 될 때까지 벽을 세운다. - 벽이 3개가 되면 다음 ..
[백준 11726] 2*n 타일링 (Java) https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 방법 규칙을 찾아 점화식을 도출해 내야하는 DP 문제였다. 점화식 자체는 찾아내는데 크게 어렵지 않았다. 하나하나 그려가며 합을 비교해보면 dp(n) = dp(n-1) + dp(n-2)의 점화식이 어렵지 않게 도출된다. 문제는 왜 그런가였다. 아래 그림과 같이 비교해보고 쉽게 알 수 있었다. n = 1일 때는 세워진 타일 1개 n = 2일 때는 두 개의 세워진 타일과 눕혀진 타일로 총 2개였다. n = 3일 때부..
[백준 2583] 영역 구하기 (Java) https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net 접근 방법 탐색을 위해 입력받은 모눈종이 정보를 2차원 배열로 변환했다. 직사각형이 들어간 칸은 1, 그렇지 않은 칸은 0으로 표기했다. 배열과 다르..
[백준 2636] 치즈 (Java) https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net 접근 방법 바깥 공기와 접촉해 있는 치즈 부분을 탐색해 제거하기 위해 우선 바깥 공기와 내부 공간을 구별해야했다. (1, 1)부터 bfs를 통해 0인 공간을 -1로 변경하였다. (내부공간은 탐색되지 않으니 그대로 0) 그 다음 이 중 for문으로 치즈 가장자리(해당 좌표에서 상, 하, 좌, 우에 -1이 한 번..
[백준 9466] 텀 프로젝트 (Java) https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다. 학생들이(s1, s2, ..., sr)이라 할 때, r= www.acmicpc.net 접근 방법 일반적인 DFS로 접근하여 시도를 했는데 런타임 에러가 발생했다. 1 5 2 3 4 5 4 위 케이스와 같이 5 -> 4 ..
[백준 7569] 토마토 (Java) https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마 www.acmicpc.net 접근 방법 백준 7576번 토마토 문제의 심화 단계로 역시 bfs로 접근이 가능했다. 다른 점이 있다면 탐색 범위가 상,하,좌,우에 위층,..
[백준 7576] 토마토 (Java) https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net 접근 방법 시작점이 여러 개인 bfs 문제였다. 현재 위치와 일수를 담는 Point 객체를 만들었고 탐색하는 동안 조건에 만족한 경우 큐에..

티스토리툴바