백트래킹

백트래킹

백트래킹 (Back Tracking) 1) 백트래킹란?백트래킹은 모든 경우의 수를 탐색하되, 조건을 만족하지 않는 경우 탐색을 중단하고 이전 단계로 되돌아가는 방식의 탐색 알고리즘이다. DFS 기반의 완전 탐색 기법 중 하나로, 불필요한 탐색을 줄여주는 가지치기(pruning) 기법이 포함된다. 2) 백트래킹 동작원리 1. 가능한 모든 경우를 시도한다 (DFS 기반 탐색). 2. 탐색 도중 조건에 맞지 않는 경우 더 이상 진행하지 않고 되돌아간다 (backtrack). 3. 조건을 만족하는 경우 정답 처리한다. 4. 다음 탐색을 위해 상태를 복구하고(undo), 새로운 경우의 수를 시도한다. // 백트래킹 구조void backtrack(int depth) { if (종료 조건) { ..

  • format_list_bulleted Algorithm/이론
  • · 2025. 5. 21.
[백준 15649] Java - N과 M (1)

[백준 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.
DFS 깊이 우선 탐색 (스택 방식)

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 깊이 우선 탐색 (재귀방식)

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.
[백준 1926] Java - 그림

[백준 1926] Java - 그림

그림 https://www.acmicpc.net/problem/1926 1) 문제어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와 가장 넓은 그림의 넓이를 출력하여라.그림은 1로 연결된 영역이고, 가로나 세로로만 연결된 것을 연결된 것이라 한다.그림의 넓이는 1의 개수이다.입력: 세로 크기 n (1 ≤ n ≤ 500), 가로 크기 m (1 ≤ m ≤ 500)이후 n줄에 걸쳐 0과 1로 이루어진 도화지 정보 제공출력: 그림의 개수와 가장 넓은 그림의 넓이 (없으면 0) 2) 예시입력출력6 5 1 1 0 1 10 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 149 3) 풀이 1. 아이디어2중 for문으로 모든 좌표 순회 → 값이 1이면서 방문..

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