www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이번 문제는 백트래킹 단계의 입문 문제 이다. 백트래킹 문제는, 트리 형태의 노드들을 깊이 우선 탐색 (DFS) 을 수행하면서, 노드의 유망성을 판단하여, 유망하지 못하다고 생각하면 가지치기를 하고(풀이시간 단축), 다시 부모 노드로 돌아가서 다른 자식 노드를 탐색하는 방식이다. 문제 풀이 dfs의 기본 틀은 아래와 같다. 재귀를 끝낼 조건을 정해줘야 하는데, index가 M이랑 같을 시점에 arr 배열의 모..
www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 분석 일단, 하노이 탑이란 위에 설명을 보면 알겠지만, 조건이 두가지가 있다. 한번에 한 원판만 옮길 수 있다. 아래의 원판은 항상 위에 원판보다 크다. 그렇다면 과연 어떻게 옮겨야 할까? 일단 원판 3개를 가지고 규칙을 살펴보자. 1. 일단 1번째 타워에서 3번째 타워로 3개의 원판을 옮기기 위해서는 그 위에 있는 두개의 원판을 먼저 가운데로 옮겨야 한다. ( 5번 그림 참조) 2. 가장 작..
www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수 란? 0번째 수와 1번째 수가 1이고, 2번째 수 부터 앞에 두 피보나치 수의 합이 된다. 코드로 표현 import java.util.Scanner; //10870번 문제 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = ..
www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 재귀의 기본적인 구현이라고 할 수 있는 팩토리얼 문제이다. 먼저 팩토리얼 이란? 숫자 n이 주어졌을 때, n 부터 1까지의 곱의 결과를 뜻한다. 0! = 1 1! = 1 2! = 2 x 1 3! = 3 x 2 x 1 .. n! = n x (n-1) x ... x 1 이것을 트리 형태로 만들면, 아래의 그림과 같다. 자 그럼 이제 점화식이 보인다. if (n==1) 일 경우 ∫(n) = 1; if (n==2) 일 경우 ∫(n) = 1; n은 0보다 큰 양의 정수이다. ∫(n)= n x ∫(n-1) 코드로 표현 해보자..
www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 🚀문제 💬 예제 입력 5 5 4 3 2 1 💬 예제 출력 1 2 3 4 5 🌈 나의 풀이 문제를 보고 당연히 Arrays.sort() 를 사용하려 했지만,, 시간 초과. 퀵 정렬은 평균 시간 복잡도가 O(nlogn) 이지만, 최악의 경우 O(n2) 까지 될 수도 있다. 일부러 퀵 정렬을 못쓰게 하려고 한 데이터가 있는 것 같다. ( 그럼 다른거 쓰면 되지🙃) Merge Sort 사용 X Counti..
🚀문제 재귀적인 패턴으로 별을 찍어 보자. 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번째 줄까지 별을 출력한다. 💬 예제 입력 27 💬 예제 출력 *********************..
