본문 바로가기

Algorithm/BOJ46

[백준] 11055번 가장 큰 증가 부분 수열 자바 문제 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 문제 풀이 구글링했다. 역시 DP는 너무 어려워.. 어떻게 이런 방법으로 풀 생각을 하지 라고 생각했다.. 알고리즘은 반복문을 돌면서 dp배열에 현재 인덱스까지의 최대 배열 합을 갱신해나가면서 배열을 채우고 가장 큰 값을 반환하면 되는 거였다. 코드에서 의문이었던 점은 현재 i번째의 배열 값과 그 전까지의(j) 배열 값들을 확인하는 반복문에서 i까지의 값이 증가되는 것을 확인하지 않고 그 j의 값 자.. 2022. 3. 17.
[백준] 2178번 미로 탐색 자바 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 문제 풀이 이 문제는 진짜 BFS의 정석 같다. 처음에 오른쪽 왼쪽으로 이동하는 것만 담았다가 벽에 막혀서 위나 왼쪽으로도 다시 올라갈 수 있다는 점을 깨닫고 다시 상하좌우로 dr, dc배열을 바꾼거랑 visited배열을 int가 아니라 boolean으로 처음 쓰고 바꾼 거 말고는 나름 빨리 푼 것 같다. 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo.. 2022. 3. 4.
[백준] 14719번 빗물 자바 문제 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제 풀이 ✔️ 알고리즘 1. 빗물 block[][] 배열에 받아두기 2. block배열의 맨 아래 행부터 위로 올라가면서 고인 빗물세기 3. 블록 처음 만났을 경우, 빗물이 고일 수 있으므로 start변수에 true로 설정해두기 4. start변수가 true이면서 다시 블록을 만났을 경우 end변수에 true로 설정하기 5. 그리고 다시 빈 곳을 만났을 경우 end변수 false로 바꾸기 6. 한 행의 반복이 끝났는데 end변수가 true.. 2022. 3. 4.
[백준] 1149번 RGB거리 자바 문제 (DP) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 처음에 DFS로 모든 경우에 한해 값을 계산하고 최소값을 갱신하는 방법으로 풀었는데 시간초과가 떴다. 구글링해보니 dp로 생각보다 간단하게 풀 수 있었다. 행렬의 크기를 [N][3]으로 잡아서 행은 집의 개수, 열은 RGB를 나타내는 개수로 각 집의 색상을 어떤 것을 칠하느냐에 따라 dp배열을 갱신한다. 모든 칠하는 경우의 개수를 보게 되므로 그 전 집의 색깔 중에서 최소값을 바로 택해도 가능하다. 소스 코드 imp.. 2022. 2. 11.
[백준] 14502번 연구소 자바 문제 (DFS, 브루트포스 알고리즘) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 세상에나 완전탐색 문제였다. 난 뭐 논리적으로 푸는 줄 알았는데 구글링해보니 그냥 모든 경우에 한해 벽 세우고 탐색하면서 안전구역의 최대값을 구하는 거였다... 나는 벽 세우는 것과 바이러스 퍼져나가는 것 둘 다 DFS로 구현했다. 그리고 minCount와 count 두 개의 변수를 이용해 답을 구했는데, 아래 코드에서 count는 해당 경우의 벽또는 바이러스의 개수 카운트이고, 이 수가 작을수록 안전구역의 개수가 커지는 것이므.. 2022. 2. 2.
[백준] 14888번 연산자 끼워넣기 자바 문제 (브루트포스 알고리즘) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 풀이 사용되는 연산자를 해당 연산자의 인덱스번호를 perm_data에 담는다. 예를 들어 '+'가 1개, 'x'가 2개 이면 perm_data = {0, 2, 2} 이런 식으로 담기게 된다. 이 배열을 조합하여 모든 경우에 해당 되는 연산자 순서를 구하고, 구하는 경우마다 계산결과를 구해 답을 갱신한다. 소스 코드 import java.util.Scanner; public c.. 2022. 2. 2.

티스토리툴바