"꾸준하게, 지속하자 "

우선 문제 접근은 매우 쉬웠다 결국 틀렸지만ㅋㅋ,, 이전 포스트에서도 설명했듯, DP문제를 풀 때는 맨 마지막 항 N이 어떻게 구성될수 있는지 경우의 수를 나눠서 일반항을 구하는것과 구한 DP배열의 각 항이 무엇을 의미하는것을 정의하는게 제일 핵심이다. 1. 맨 마지막 항 N이 구성될 수 있는 경우는 3가지 이다. 내가 직접 그림을 그렸다. 그런데 매우 특이한 점은, 맨 마지막항을 "무조건" 방문해야 한다는 조건이 없기에, 만약 2번 3번 경우보다 아예 해당 노드를 안방문하는 경우가 더 클 경우, 그냥 바로 전 항의 dp값을 현재의 dp값으로 할 수 있다는 것이다. 여기서 방문(마신다)는 것은 dp[i]의 값에 현재의 인덱스값 arr[i]를 더해주느냐 마느냐로 정할수 있다. dp[i]의 값을 구하는 식에..

우선 어떤 알고리즘을 풀어서 해를 낼수 있겠다. 이런 느낌은 5초만에 바로 올정도로 접근법은 쉽지만, 구체적인 해답 경로를 찾기에는 어려웠다. 아니, 어렵다기 보다는 신박? 했다 해야하나... 우선 기존 BFS문제와는 조금 결이 달랐다. 기존 문제는 각문제마다 조건이나 상황이 다 다르겠지만, '어느 지점까지 도착할지 최솟값을 구하여라' 이런 류가 대부분이였다. 그러나 이 문제는 한 계층마다 같은 값을 더해준다는 느낌(한번 이동을 수행할때마다)은 BFS문제들과 같은데, 2가지 내 머릿속의 문제점을 해결하지 못하여서 쉽게 코드를 짜지 못하고 있었다. 내가 문제를 풀면서 마주했던 의문점. 1.어느곳이 마지막 도착점인지, 또한 무엇보다 모든 토마토가 다 익었는지 판단후 도대체 무슨 값이 모든 바구니가 다 익었을..

우선, '비용의 최솟값' 을 구하라는 말이 나왔으므로, DP로 풀어야 한다. 그런데 그 전까지는 DP배열이 1차원 배열이였는데 지금은 상황이 조금 다르고, DP[i][j]가 무엇을 가르키는지 구체적으로 정의하는 것이 매우 중요하다. 이전 포스트에서도 꾸준히 강조하는 말하지만 DP문제에서 무엇을 DP값으로 정할건지가 핵심이다. 나는 이 문제에서 2차원 배열로 주어진 입력값(행:N번째 집 열: 빨,초파)에서 결국 맨 마지막으로 선택되어질수 있는 색깔, 마지막 N번쨰 항에을 조건으로 삼아 DP값을 정의하였다. 우선 문제의 특수한 조건들 때문에 마지막 N번집의 색깔은 빨, 초, 파, 중 한개만 가능하다. 즉, 경우의 수를 3개로 나누어(마지막 색이 빨강부터 칠해질건지, 파랑부터 칠해질건지..) 모든 경우의 수를..

일단 매우 어려웠다. 그나마 이거 풀기 전, 2차원 배열의 DP를 활용하는 문제인 1149번 RGB 거리 문제를 풀지도 못하고, 정답을 한번 봐서 그런지, 접근법은 대충 맞았다. 그러나, 진짜 이런 2차원 배열의 DP활용 문제를 처음 봤더라면 접근조차 못했을 것이다. 우선 가장 핵심적인 아이디어는 "아래로 내려갈수록, 가장 최대의 값만 선택하면 안된다. 즉, 그리디로 풀수 없다." -> 그렇기에 모든 경우의 수를 다 따져야 된다.-> 처음부터 아래로 내려가는 규칙을 찾자. 이다. 노트에 그려 보면 맨 왼쪽노드와 맨 오른쪽 노드는 바로 그전 계층의 노드값을 그대로 받는다. -> if(j==0){ dp[i][j]=arr[i][j]+dp[i-1][0]; } if(j==i-1){ dp[i][j]=arr[i][j..

우선 문제를 보자마자 그래프 탐색 알고리즘을 이용하여 "연결요소"의 개수를 파악한 다음 그걸 리스트에 담고, 리스트를 정렬해준 다음, 차례로, 리스트 사이즈출력, 리스트요소들 하나씩 출력 해주면 끝난다. 풀이법을 생각해내는데 5분도 걸리지 않았지만.... 실제 정답을 내는데 디버깅 포함 1시간 걸린거 같다... 내가 실수한 부분은, 이 문제는 "최단거리"나, "백트레킹" 등, 그래프 탐색에 있어서 특수한 조건이 없기 때문에, DFS또는 BFS중 아무거나 사용 가능하다. 이유는 두 기법 모두, 연결된 노드를 전부 방문할수 있고, 그에 맞춰서 카운트 값을 올려줄수 있기 때문이다. 어제 쓴 포스트에서는 BFS를 이용해서 풀었기에, DFS로 풀어볼까 하면서 코드를 짰더니... 계속 리스트 사이즈 1, 값은 48..

전형적인 그래프 탐색 문제이며, "최단" 거리+미로의 탈출을 구하여야 함으로 BFS를 써야 한다. 최단 거리를 구하는 문제에서, DFS가 아닌 BFS를 쓰는 이유는 한가지 계층(똑같은 길이나 방법)을 이용해서 한번 이동을 한 거리가 모두 같음이, 자연스럽게 구현이 되기 때문이다. 또한 같은 계층으로써 방문한 노드가 목적지랑 같을시, 계층 한번이동할때(큐에 넣을때) 넣어준 카운트 값으로 쉽게 최단거리를 출력할 수 있다. 또한 미로의 탈출은 깊이우선 탐색을 하게되면, 해답을 찾지못해도, 계속 깊이가 끝날때까지 탐색을 하기에, 비효율 적이다. 그래서 난, BFS를 통해 이문제 풀이법을 구현해 보았다. 그러나 내가 이전 포스트에서 쓴 촌수문제에서, 큐에 넣을때(한번 계층이동이 이루어질때) 바로 카운트값을 더해주..

우선 순열이란 단어를 보자마자, 아 백트레킹을 이용한 순열을 구하는 것인가? 라는 생각이 들었다. 그러나 문제를 계속 읽으니, 그냥 각 인덱스값, 1부터 N까지에 대응되는 값을 이용하여, 인접리스트나 인접행렬을 통해 노드와 노드사이의 관계를 표현한 다음, 연결요소의 개수를 구하면 된다는 것을 알게 되었다. 처음 난, 이전에 풀어봤던 아파트 단지문제나 배추심기 문제 등에서 좌표평면에 (x,y) 좌표로 노드간의 연결관계를 표현 한 것을, 상화좌우 인접한 좌표로 dfs를 통해 끝까지 탐색하며1을 0으로 바꾸고, 그 곳들을 for문을 통해 처음부터 하나하나씩 dfs로 돌릴때, 해당 좌표가 1이면 카운트 해주는 식으로 풀이를 하면 될줄 알았다. 하지만 이 문제는, 좌표로 나타내었을때, 각 좌표들간의 상관관계가 존..

우선적으로 사용자로부터 N과 M 입력 값을 받는다. 그리고, 연산의 대상이되는 수들을 사용자로부터 N개 입력받는다. N P M을 구해보겠다. 우선 순열이나, 조합 모두 dfs의 방법중 하나인 백트레킹을 이용한다. 1.모든 노드를 탐색해야한다. 2.노드 탐색의 조건이 있다.(한번 방문한 노드는 방문하지 않는다. 그러므로 dfs를 통한 백트레킹 방법을 이용한다. import java.io.*; import java.util.*; public class Main { static int[] arr; static int[] output; static boolean[] value; static int N; static int M; public static void main(String[] args) throws I..

우선 증가하는 부분수열 문제를 dp로 풀수 있다면 이 문제또한 쉽게 풀수 있을것이다. 애초에 앞의 상자보다 값이 작으면 뒷 상자에 넣을수 있다는 조건이, LIS 문제의 정의와 같다. 다만 주의해야 할 점은, if 조건문에서 단순히 이전값이 현제 인덱스의 값보다 작을시, 이전 dp값에 +1한 것을 현재dp값에 더해주는것을 가능하게하는 조건으로 작용하는 것이 아니라,(아래의 코드에서 dp[i]=dp[j]+1 부분) 이전 dp의 값+1 한 것이 현재 dp의 값보다 커야한다라는 조건도 있어야 된다는 것이다. 나도 처음에 이 조건이 왜 필요한지 생각하느라 애를 참 많이 썼는데, 간단히 설명하자면 이전 값이 현재의 값보다 더 작다는 조건에 만족하는 중복된(같은수)를 카운트하는것을 방지하기 위한 장치이다. 예를 들면..