[백준 15649] Java - N과 M (1)

https://www.acmicpc.net/problem/15649 N과 M (1) 1) 문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력: 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력: 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다. 2) 예시예제입력 1:3 1예제출력 1: 123예제입력 2:4 2예제출력 2:1 21 31 42 12 32 43 13 23 44 14 24 3예제입력 3:4 4예제출력 3..

• format_list_bulleted Baekjoon Coding Test/Java
• · 2025. 5. 3.

[백준 10870] Java - 피보나치 수 5

https://www.acmicpc.net/problem/10870 피보나치 수 5 1) 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.입력: 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.출력: 첫째 줄에 n번째 피보나치 수를 출력한다. 2) ..

• format_list_bulleted Baekjoon Coding Test/Java
• · 2025. 5. 2.

재귀함수 (Recursion)

재귀함수 1) 재귀함수 란?함수가 자기 자신을 호출하는 방식의 함수입니다.대표적으로, 팩토리얼 계산, 피보나치 수열, 하노이 탑, DFS, 백트래킹 등 모든 깊이 탐색 알고리즘의 기반이 됩니다. 2) 재귀함수의 동작원리재귀 함수는 내부적으로 '스택 구조'를 따릅니다.즉, 함수가 호출될 때마다 현재 함수는 잠깐 멈추고, 새로운 함수 호출이 먼저 끝날 때까지 기다립니다.맨 마지막 호출이 종료되면 차례로 다시 돌아옵니다. 3) DFS 활용분야활용 분야설명경로 찾기특정 노드까지의 경로 유무, 경로 목록 찾기미로 탐색출구가 있는지 확인하거나 모든 경로 탐색백트래킹 문제N-Queen, 순열/조합, 스도쿠 해결 등트리 탐색전위/중위/후위 순회 구현사이클 탐지그래프 내 순환 여부 확인위상 정렬DFS 기반 ..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 2.

DFS 깊이 우선 탐색 (스택 방식)

DFS 1) DFS란?시작 노드에서 가능한 깊이까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아(backtrack) 하여 다음 경로를 탐색하는 방식입니다.한 방향으로 계속 깊게 파고들며, 재귀 또는 스택(Stack)으로 구현 가능하고, 경로 탐색, 조합 탐색, 미로 문제, 백트래킹 등에 유리합니다. 2) DFS 시간복잡도와 공간복잡도시간복잡도 : O(V + E)V = 정점(노드)의 개수E = 간선의 개수공간복잡도 : O(V) 또는 O(h) V = 정점(노드)의 개수h = 그래프의 최대 깊이 3) DFS 활용분야활용 분야설명경로 찾기특정 노드까지의 경로 유무, 경로 목록 찾기미로 탐색출구가 있는지 확인하거나 모든 경로 탐색백트래킹 문제N-Queen, 순열/조합, 스도쿠 해결 등트리 탐색전..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 1.

DFS 깊이 우선 탐색 (재귀방식)

DFS 1) DFS란?시작 노드에서 가능한 깊이까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아(backtrack) 하여 다음 경로를 탐색하는 방식입니다.한 방향으로 계속 깊게 파고들며, 재귀 또는 스택(Stack)으로 구현 가능하고, 경로 탐색, 조합 탐색, 미로 문제, 백트래킹 등에 유리합니다. 2) DFS 시간복잡도와 공간복잡도시간복잡도 : O(V + E) V = 정점(노드)의 개수E = 간선의 개수공간복잡도 : O(V) 또는 O(h) V = 정점(노드)의 개수h = 그래프의 최대 깊이 3) DFS 활용분야활용 분야설명경로 찾기특정 노드까지의 경로 유무, 경로 목록 찾기미로 탐색출구가 있는지 확인하거나 모든 경로 탐색백트래킹 문제N-Queen, 순열/조합, 스도쿠 해결 등트리 탐색..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 1.

복잡도

복잡도 ( Complexity ) 1) 복잡도란?복잡도는 알고리즘이 문제를 해결하는 데 소요되는 리소스를 추상적으로 측정하는 방법 2) 복잡도의 종류 종류 의미측정 단위시간 복잡도실행에 걸리는 시간연산 횟수공간 복잡도사용하는 메모리 양저장 공간 3) 시간복잡도 (Time Complexity)입력 크기 n에 대해, 알고리즘이 수행하는 연산의 수를 수학적으로 표현한 것입니다.예시아래 코드는 n번 반복하므로 O(n)입니다.for (int i = 0; i 이중 반복문이라 총 n * n번 → O(n²)for (int i = 0; i 4) 공간복잡도 (Space Complexity)알고리즘이 문제를 해결하는 동안 사용하는 메모리 공간의 양예시배열 n개의 공간이 필요 → O(n)int[] arr ..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 1.