재귀

[백준] 17136 - 색종이 붙이기 (자바 Java)

[Gold II] 색종이 붙이기 - 17136 문제 링크 성능 요약 메모리: 22020 KB, 시간: 344 ms 분류 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing) 문제 설명 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 ..

[백준] 2448 별 찍기 - 11 (자바/Java) 재귀, 분할정복

문제 링크 성능 요약 메모리: 236216 KB, 시간: 528 ms 분류 분할 정복(divide_and_conquer), 재귀(recursion) 문제 설명 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 분할정복이 아직 익숙하지 않은 것 같다... 하하 일단 내 힘으로는 재귀로 풀었다 크기가 3일 때부터 차례대로 채워가는 식으로 구현하였다. 재귀 풀이 if (idx == N) return; if (idx == 0) { stars[0][N] = '*'; stars[1][N - 1] = '*'; stars[1][N ..

[알고리즘] 비트 연산자 & 부분집합 (자바/Java)

비트 연산자 &둘 다 1 이면 1 / 해당 비트가 있는지 검사! System.out.println(3 & 5); // 3 = 011 // 5 = 101 // -------- // 001 -> 1 | 하나라도 1이면 1 System.out.println(3 | 5); // 3 = 011 // 5 = 101 // -------- // 111 -> 7 ^ XOR - 서로 다르면 1 System.out.println(3 ^ 5); // 3 = 011 // 5 = 101 // -------- // 110 -> 6 A >1); // 5 / (2^1) = 2 // 101 -> 010 = 2 부분집합 N개의 원소를 가진 집합에서 전체 부분집합의 개수 = 2^N 1. 재귀 부분집합은 공집합부터 원소가 1개, 2개, … ..

[백준] 1182 - 부분수열의 합 (자바/Java) 재귀 부분집합

문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. N개의 수 배열에 대한 부분집합 중에서 합이 S가 되는 경우의 수를 찾으면 된다. 그러나 부분수열의 크기가 양수이기 때문에 공집합은 제외해야 한다. 처음에는 sum을 더하는 식으로 했지만, 공집합을 제외하기 위해 boolean 배열을 통해 sum에 더할 것..

[백준] 11729 - 하노이 탑 이동순서 (자바/Java): 하노이 타워(Towers of Hanoi)

문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈..

[백준] 2447 - 별 찍기 10 (자바/Java): 재귀

문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다. 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 설명 참고: https://velog.io/@sossont/%EB%B0%B1%EC..

[백준] 17478 - 재귀함수가 뭔가요? (자바/Java): 재귀 Recursion

문제 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대학교가 자신과 맞는가에 대한 고민을 항상 해왔다. 중앙대학교와 자신의 길이 맞지 않다고 생각한 JH 교수님은 결국 중앙대학교를 떠나기로 결정하였다. 떠나기 전까지도 제자들을 생각하셨던 JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다. JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자. 입력 교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다. 출력 출력 예시를 보고 재귀 횟수에 따른 챗봇의 응답을 출력한다. 재귀함수를 활용한 출력 문..