Coding Test/백준 알고리즘 풀이45 [백준] N과M (1), (2), (3), (4) : 자바 백트레킹 이번 포스팅에서는 백준 N과 M 시리즈에 대해서 얘기해보자 ! 문제 (2),(3),(4)는 (1)에 조건이 추가된 문제들이다. N과 M(1) 알고리즘을 풀어봤다면 (2),(3),(4) 는 비교적 쉽게 풀 수 있다.✔️ N과 M (1) : 15649번arr : 출력할 수열을 담을 배열visited : 중복되지 않은 수를 출력하기 위해 방문 여부를 담을 배열import java.io.BufferedReader;import java.io.IOException;import java.util.StringTokenizer;import java.io.InputStreamReader;public class Main{ static int[] arr; static boolean[] visited; priv.. 2024. 10. 1. [백준] 7576 토마토 : 자바 BFS [골드5] ✔️ 문제 설명 (펼치기)더보기문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 .. 2024. 10. 1. [백준] 1600 말이 되고픈 원숭이 : 자바 BFS [골드 5] ✔️ 문제 설명 (펼치기)더보기문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x x 말 x x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.이제 원숭이는.. 2024. 9. 29. [백준] 15486 퇴사2 (자바) : DP [골드 5] ✔️ 문제 설명 (펼치기) 더보기더보기문제상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.N = 7인 경우에 다음과 같은 상담 일정표를 보자.35112421020102015402001일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.상담을 하는데 필요한 기간은 1일보다 클 .. 2024. 9. 17. [백준] 11055 가장 큰 증가하는 부분 수열 (자바) : DP [실버2] ✔️ 문제 설명 (펼치기)더보기 문제수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다. 예제 입력 1 101 100 2 50 60 3 5 6 7 8예제 출력 1 113 ✔️ 문제 풀이 + 코.. 2024. 8. 29. [백준] 11053번 가장 긴 증가하는 부분 수열 (자바) : DP [실버 2] ✔️ 문제 설명 (펼치기) 더보기문제수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.입력첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1 610 20 10 30 20 50 예제 출력 1 4✔️ 문제 풀이자세한 풀이는 아래의 제 다른 포스팅에 있습니다 !! [알고리즘] LIS : Longest Incr.. 2024. 8. 28. 이전 1 2 3 4 5 6 7 8 다음
