mondegreen

그래프 너무 어렵지만.. 가중치가 없는 그래프이니까 다익스트라 제외, 최단경로가 아니라 어디까지 이어져 있는지가 중요하니까 BFS가 아닌 DFS로 구현하기로 결정했다. 보통은 두개의 트리로 분리되어 있는 송전탑을 하나의 트리로 연결시키라고 하면 너무...정말... 유니온파인드 써서 쉽게 처리하겠지만 이건 반대로 한개를 두개로 나누라고 하니 풀이방법을 찾지 못했다. 아래는 책을 참고해서 푼 로직이다. 답인 answer는 최대값인 n-1로 설정한다. 그 이유는 다른 한쪽이 한 개의 송전탑으로 이루어진 경우에 가장 큰 차이를 가지는 때이므로 n-1로 초기화해준다. DFS부분이 문제인데 송전탑을 하나씩 연결해가면서 나머지 송전탑 무리들과의 차이를 최솟값으로 갱신해나간다. 그래서 현재 송전탑이 연결된 것으로 가정..

개인적으로 재귀를 직관적으로 이해하는 게 많이 어려웠다. 그래서 재귀를 다시 익숙하게 만들기 위해서 그나마 정답률이 높은 이 문제를 선택했지만 고민을 해봐도 영 감이 잡히지 않아서 풀이를 참고해서 풀었다. 그나마 할 수 있는 건 풀이를 보고 따라치는 게 아니라 손으로 스택에 함수를 쌓아가며 다시 의사코드를 작성해보고 이를 다시 코드로 옮기면서 로직을 이해하려 노력했다. 여기서도 문제를 작게 나눠서 보는 것이 필요한데 n이 3일 때는 3*3의 배열을 가진 칸에 5번째 칸 즉, (1,1) 칸이 비어있어야 한다. n이 9인 경우에도 9*9의 배열이지만 각각의 3*3의 배열로 이루어져 있어서 5번째 3*3 즉, (3,3) 부터 우하향으로 (5,5)까지의 배열이 비어있어야 한다. 이걸 깨달은 사람은 천재들인가....

순서 X 중복 X 서로 다른 n개의 원소 중 r개의 순서없이 골라낸 것 import java.util.Scanner; public class Main { static int n, m; static int[] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); arr = new int[m + 1]; rec(1); sc.close(); } private static void rec(int idx) { // 기저조건 if (idx == m + 1) { for (int a = 1; a < arr.length; a++) { System.out.print(..

순서 O 중복 X 서로 다른 것들 중 몇 개를 뽑아서 나열하는 것 import java.util.Scanner; public class Main { static int n, m; static int[] selected; static boolean[] used; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); selected = new int[m + 1]; used = new boolean[n + 1]; rec(1); sc.close(); } private static void rec(int idx) { // 기저조건 if (idx == m + 1) {..

재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용한다. 하나의 큰 문제를 해결하기 위해 다소 해결하기 쉬운 작은 문제의 결과를 조합한다. 재귀함수(Recursive Function)함수 내부에서 자기 자신을 호출하는 함수로서기저 부분(basis part)와 유도부분(inductive part)으로 이루어져 있다. 함수 호출은 프로그램의 메모리 구조 중 스택을 사용한다. 반복적으로 스택을 사용하기 때문에 메모리 및 속도에서 성능 저하가 발생한다.  함수 호출 시 기저 부분이 작동하지 않으면 자기 자신을 무한 호출하여 stackoveflow 발생 // n!에 대한 재귀함수int fact(int n){ if(n** 반복과의 비교n이 커질수록 재귀가 반복보다 메모리와 연산속도 효..