개발자는 기록이 답이다

7. 조합의 경우수(메모이제이션) 예시 입력 1 5 3 예시 출력 1 10 예시 입력 2 33 19 예시 출력 2 818809200 강의 풀이(Time: 153ms Memory: 27MB) 먼저 nCr에 대해 이해보자 nCr : n개 중에 r개를 뽑는다는 의미이다 종이에는 지우고 썼다가 불편해서 블랙보드로 샀더니 비치는건 양해부탁드립니다.. {1,2,3,4,5}라는 배열처럼 5명의 학생이 있는데, 5번 학생을 뽑을 경우와 안뽑을 경우로 DFS를 접근하면 된다 아래처럼만 해도 nCr을 구할 수 있긴하지만, 입력값이 크다면 재귀를 많이 뻗기 때문에 오래 걸릴 것이다. 그래서 메모이제이션이 필요하다 // 메모이제이션 X import java.util.Scanner; public class Main { publ..

12. 경로탐색(DFS) 예시 입력 1 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 예시 출력 1 6 인접행렬 기본 코드 인접 행렬(Adjacency Matrix)은 그래프의 연결 정보를 행렬로 표현하는 방법입니다. 정점 간의 연결 여부를 2차원 배열로 나타내며, 두 정점이 연결되어 있으면 1로 표시하고 연결되어 있지 않으면 0으로 표시합니다. import java.util.Scanner; public class 인접행렬 { // n: 정점의 개수 // m: 간선(Edge)의 개수 static int n, m, answer=0; static int[][] graph; public void DFS(int v) { } public static void main(String[] ar..

3. 팩토리얼 예시 입력 1 5 예시 출력 1 120 내가 푼 풀이 public class Main { int answer = 1; public int DFS(int n) { if(n == 0) return 0; else { answer *= n; DFS(n - 1); } return answer; } public static void main(String[] args) { Main T = new Main(); System.out.println(T.DFS(5)); } } 강의 풀이 public class Answer { public int DFS(int n) { if (n == 1) return 1; else return n*DFS(n-1); } public static void main(String[]..

1. 재귀함수(스택프레임) 예시 입력 1 3 예시 출력 1 1 2 3 public class Main { public void DFS(int n) { if (n == 0) return; else { System.out.print(n + " "); // (1) 3 2 1 DFS(n - 1); System.out.print(n + " "); // (2) 1 2 3 } } public static void main(String[] args) { Main T = new Main(); T.DFS(3); } } 위의 코드에서 보는 것 처럼 출력을 몇번째 줄에서 하느냐에 따라 반환값이 다르게 나타난다. 1번의 경우 3 2 1로 출력되고, 2번은 1 2 3으로 출력된다. 재귀함수 위에 놓는지 아래에 놓는지에 따라 출력..