조합(Combination) 개념 - 서로 다른 것들(n개) 중에서 몇 개(r개)를 순서없이 골라낸 것 - nCr - 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합 구현 - 중복체크를 안하면서 코드가 더 간결해짐 - 시작 위치(start)를 매개변수로 넘겨 매개변수부터 끝까지 탐색 -> 중복이 발생하지 않음 - 현재 뽑은 수가 i이므로 i 다음 수부터 조합을 시도하도록 i+1을 넘김 - input[] : 서로 다른 숫자(n개)를 저장하기 위한 Integer 배열 - numbers[] : 뽑은 숫자(r개)를 저장하기 위한 Integer 배열 코드 public static void combination(int cnt, int start){ if(cnt == R){ System.out.println..
순열(Permutation) 개념 - 서로 다른 것들(n개) 중에서 몇 개(r개)를 뽑아 순서있게 한 줄로 나열 - nPr - 순서가 의미가 있으면 순열 / 순서가 의미가 없으면 조합 - n번째 수를 뽑을 때, n-1번 비교를 해야 사용 가능한 수를 판단할 수 있음(최악의 경우) 구현 - 몇 번째 자리의 수를 뽑는지 달라지고 있기 때문에 해당 부분이 가변적임 -> 매개변수로 받아옴(cnt) - input[] : 서로 다른 숫자(n개)를 저장하기 위한 Integer 배열 - numbers[] : 뽑은 숫자(r개)를 저장하기 위한 Integer 배열 - isSelected[] : 중복 체크를 위한 Boolean 배열 - 해당 자리를 선택하고 뒤를 다 탐색하고 다시 돌아오면 다른 수를 또 탐색해야하므로 그 자..
문제 - 우리가 흔히 알고 있는 하노이 탑 이동 순서를 출력하는 문제 - 세 개의 장대가 있고, 첫 번째 장대에서 세 번째 장대로 다음 규칙에 따라 원판을 이동 1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. - 이 작업을 수행하는데 필요한 최소의 이동 횟수와 이동 순서를 출력하는 프로그램 작성 고찰 오랜만에 다시 알고리즘을 풀기 시작했기 때문에 쉬운 단계부터 다시 도전해야겠다고 생각하였다. 백준에서 단계별 풀기로 재귀부터 시작했는데 오랜만에 문제를 풀어서 그런지 바로바로 아이디어가 떠오르지 않았다. 첫 번째 장대에서 시작해서 세 번째로 옮길 때, 전체를 두 덩어리(n-1개, 1개 - 맨 밑)로 나눠 이동시켰다. 두 덩어리 ..