개발자는 기록이 답이다

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..

13. 경로탐색(인접리스트, ArrayList) 예시 입력 1 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 예시 출력 1 6 정점이 1000개 10000개로 들어온다면 인접행렬로는 비효율적이다. 왜냐하면 정점이 5라고하고 5행 5열로 잡으면 된다. 1번 정점에서 갈 수 있는 정점이 어디인지 탐색하는데, 100개 정도까지는 괜찮지만 1000개 10000개라고 하면 인접행렬이라는 그래프로 할때 10000x10000을 해야해서 메모리를 크게 잡습니다. 그리고 1번 정점에서 갈 수 있는걸 찾으려면 1부터 10000까지 for문을 다 돌아야 합니다. 메모리랑 시간복잡도 면에서 너무 비효율적입니다. 그래서 이럴때 인접리스트를 사용합니다. N이 5라고 가정했을때, 1번 리스트부터 5번 리스..

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..

9. 10. Tree 말단노드까지의 까장 짧은 경로(DFS/BFS) 루트노드에서 말단 노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 구하라 이런 최단 거리 문제는 BFS로 풀어야 맞습니다. 하지만 배우기 위해 DFS로는 어떻게 풀어야하는지 알아보겠습니다. DFS는 제약이 있습니다. 3번 노드에서 자식노드가 6번 노드로 하나만 있을 경우 풀기 어렵습니다. 정확하게 2개 자식노드가 있거나 아예 없어야 합니다. BFS에서는 레벨 탐색이라 상관없습니다. DFS : Depth-First Search 0,1,2레벨이 있는데 한번만에 가는 1레벨은 말단 노드라면 3원소입니다. 레벨이 바로 문제에서 정의하는 이동 횟수(거처가는 간선의 횟수)를 말합니다. 말단 노드를 만났을때, 매개변수에 있는 root가 가르..