-내 생각 이번 문제의 경우는 쉽게 풀 수 있었던 것 같다. 처음에는 예제 입력 2의 경우 10이 1이 될 수 있는 경우를 직접 써봤고, dp배열을 만들어 각 인덱스를 숫자로 하여서 해당 숫자에 도달하기 위한 연산의 수를 저장하고자 했다. 예를 들어 n이 10인 경우 dp [10] = 0부터 시작하여서 10에서 가능한 경우의 수는 -1을 하거나, 2로 나누어 떨어지기 때문에 /2를 하는 경우가 존재한다. 그렇기 때문에 -1을 하게 된다면, dp [10] +1의 값을 dp [9]에 저장하는데 이때 값이 0인 상태라면 그냥 저장하고 0이 아니라면 저장되어 있던 값과 dp [10]+1의 값을 비교해 최솟값을 저장한다. 또 /2의 경우는 dp [5]에 앞선 과정을 반복한다. 이렇게 모든 반복을 1번까지 수행하면..

-내 생각 이전까지 풀어봤던 dp문제들과는 조금 차이점이 있다. 점화식을 세워야 하는데, 어떻게 세워야 할지 몰라서 다른 분들의 글을 참고했다.. 나 스스로 푸는 게 없다 무슨 ㅋㅋㅋㅋ 어찌 됐든 풀 수 없다면 풀이를 분석하고 외우는 수밖에 없을 거다.... -해법 우선 점화식을 세우기 위해서는 문제에서 주어진 조건을 활용해야 하는 것 같다. 문제에서 주어진 조건은 1. 계단은 한 칸 또는 두 칸을 오를 수 있다. 2. 계단을 3개 연속 밟을 수는 없다. 3. 마지막 계단은 무조건 밟아야 한다.인데, 점화식을 세우는 방법은 계단이 존재할 때 한 개의 칸을 기준으로 가능한 경우의 수를 찾는 것이다. 계단을 밟을 수 있는 경우의 수는 아래의 표와 같다. n-3 n-2 n-1 n번 째 칸 O X O O O 또..

-내 생각 동적 프로그래밍을 풀기 전까지 백 트래킹 문제들을 풀어서 그런지 이 문제를 보자마자 백 트래킹 방식으로 풀 생각을 해버렸다.. 도저히 어떻게 풀어야 될지 모르겠어서 다른 분들의 글을 참고했다. -해법 우선 이 문제 역시 점화식을 세워주어야 한다. https://m.blog.naver.com/occidere/220785383050 [백준] 1149 - RGB거리 (2017-12-02 수정완료) 문제 링크 : https://www.acmicpc.net/problem/1149 이 문제는 아주 전형적인 DP(동적 계획법) 문제 중 ... blog.naver.com 이 분의 블로그에 잘 정리가 되어 있기 때문에 자세한 설명은 생략하겠다. import java.util.*; public class Mai..

-내 생각 이제 동적 프로그래밍 알고리즘 분류의 문제를 4문제 째 풀고 있는데, 알 수 있었던 것은 무언가 수열과 같은 규칙이 발견되면 점화식을 세우는 것이 가장 중요한 것 같다. 또한 대다수의 수열은 수가 커질수록 기하급수적으로 수가 커지기 때문에 자료타입에 신경을 많이 써야 한다는 것이다. 이번 문제의 경우에도 점화식은 자세히 보면 dp[n] = dp [n-2] + dp [n-3]이라는 점화식을 찾을 수 있다. 또 한 가지 더 찾을 수 있는데 이 부분은 다른 분들의 글을 알 수 있었다. dp [n] = dp [n-1] + dp [n-5] 역시도 성립한다는 점이다. 필자는 첫 번째 점화식을 사용하였는데 오답 처리를 받아 검색해보다가 자료 타입에 문제가 있었다는 것을 알 수 있었다. int 형이 아닌 l..

-내 생각 문제의 이해는 간단했다. 점화식을 찾는 것이 익숙하지 않아서 1부터 증가하면서 경우의 수를 찾아보았다. n이 1일 때 1, 2일 때 2, 3일 때 3, 4일 때 5, 5일 때 8.... 이 경우를 보면 피보나치 수열이라는 것을 알 수 있었다. 즉 점화식을 세워보면 dp [n] = dp [n-1] + dp [n-2]가 된다. 그러나 피보나치수열은 46번째 숫자부터 int의 범위를 넘어서기 때문에 dp에 저장하는 값을 미리 15746의 나머지로 저장해야 한다고 한다. -해법 import java.util.*; public class Main { static int n; static int dp[]; // 메모이제이션 public static void main(String[] args) { Scan..

-내 생각 처음에는 문제에서 주어진 피보나치 함수를 이용해 static 변수를 선언하여 0과 1에 도착할 때 마다 카운트를 해주어 출력방식을 사용하였는데, 오답처리를 받았고 또, 메모이제이션 기법을 사용하지 않아 시간초과 처리도 받았었다. 그래서 다른 분들의 글을 참고하였는데... 너무 어려웠다.. -해법 이 문제는 시간초과 문제를 해결하기 위해선 문제가 요구하는 알고리즘 형태는 점화식을 세워 수식의 형태로 해결하는 것이다. 그러나 점화식을 세우는 것에 익숙하지 않았기 때문에 다른 분들의 글을 참고했는데, 한 가지 점화식을 알 수 있었다. 메모리의 형태는 무엇을 사용하든 작성자 마음이지만, 이 문제에서 발견할 수 있는 규칙성은 0의 경우는 0: 1번, 1: 0번 1의 경우는 0: 0번, 1: 1번, 2의..

-내 생각 이번 문제 역시 이전의 N과 M문제들과 같은 맥락의 문제였다. 차이점은 이 문제에서는 순열 + 이미 선택한 숫자를 중복해서 선택할 수 있다는 점이다. 구현으로는 어렵지 않았다. 단순히 방문 배열을 사용하지만 않으면 됐다. 하지만 처음으로 구현 후 출력까지 확인 후 제출을 했는데 시간 초과가 나버렸다... 아직 시간 복잡도 등을 고려할 수준이 못되기 때문에 어디서 문제가 있는 것인지 찾을 수 없었는데, 검색하는 도중 자바의 경우에는 일반적인 입출력을 사용할 시 시간 초과가 날 수 있다는 글을 보고 바로 수정한 후 제출했더니 정답처리를 받을 수 있었다. -해법 자바에서 일반적으로 우리가 사용하는 입출력 라이브러리는 Scanner를 이용한 입력방법과 System.out.print();를 이용한 출력..

-내 생각 우선 알고리즘 공부를 시작하고 순열 문제를 처음 접했다. 여러 글을 읽어보던 중 순열과 조합의 차이를 알 수 있었고, 이번 문제는 그 순열에 관한 문제였다. DFS와 백트래킹을 이용하라고 하는데 아직까지는 개념이 잡히질 않는다. DFS의 경우에는 한 가지를 고정한 후 가능한 경우의 수를 찾고 또 그 경우의 수에서 한 가지를 고정하고 하위 경우의 수를 찾고... 갖은 개념으로 알고 있으며 백트래킹은 이러한 과정에서 어떠한 조건에 걸리지 못하면, 다 배제를 해버리는 탐색으로 완전 탐색과는 다른 개념으로 알고 있다. 문제의 이해는 쉬웠지만 어떻게 구현해야 할지 감이 잡히질 않아서 다른 분들의 블로그 글들을 많이 참고했다. -해법 dfs메서드에 반복 횟수를 인자로 전달한다. 0번부터 전달하는 이유는 ..

-내 생각 단계별로 풀어보기 DFS, BFS로 분류되어 있는 백준 2606 바이러스 문제이다. 이전 단계에 백트래킹 알고리즘 단계가 있었는데 일반적으로 백트래킹의 경우 DFS를 기반으로 푼다는 글을 보고 우선 DFS와 BFS를 먼저 공부하기로 마음먹고 만난 문제다.(물론 이전에 DFS와 BFS 문제가 있었지만 단순한 개념 수준의 문제) 문제를 이해하는데 어려움은 없었고, 해법으로 처음 생각한 것은 단순히 인접 행렬로 그래프를 구성 후, 완전 탐색 방식인 DFS 또는 BFS를 사용하면 될 것 같았다. 그렇다면 DFS와 BFS 중 무엇을 사용해야 할지 선택해야 했는데, 문제 상으로는 바이러스에 감염된 컴퓨터와 인접한 컴퓨터부터 차례대로 감염된다는 언급이 있었기 때문에 한 노드의 인접한 노드를 모두 방문하는 ..

-내 생각 저번 게시글에서 공부했던 그래프의 순회 기법의 두 가지인 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)이다. 그래프의 구현은 인접 행렬을 이용하여 간단하게 구현할 수 있었고, DFS와 BFS의 구현의 경우에 DFS는 재귀 호출 형태로 구현이 쉬웠지만, BFS는 재귀나 스택이 아닌 큐만을 이용한다는 점을 간과해버리고 BFS도 재귀로 구현할 뻔했다.. 저번의 코드를 참고해서 작성할 수 있었다. -해법 코드를 보면서 이해해보자. import java.util.*; public class Main { static int node[][]; // 인접행렬 배열 static int check[]; // 노드의 방문여부 표시 배열 static Queue queue = new LinkedList(); /..