문제설명입력 & 출력나의 풀이문제 접근 방법"백준 - 색종이 만들기" 문제는 하얀색(0)과 파란색(1)로 칠해진 종이가 주어지고 전체 종이가 모두 같은색으로 칠해있지 않으면 N/2로 나눠가면서 모든 영역의 종이가 같은색으로만 이루도록 만들고, 각 종이의 색깔의 개수를 출력하는 문제입니다. 위와 같이 최종적으로 나누어진 색종이들을 보면, 흰색은 9개, 파란색은 7개로 나누어집니다.제가 접근한 방법은 다음과 같습니다. 주어진 종이 전체가 하나의 색깔로 이루어져 있는지 확인모두 같은 색이면 하얀색 종이 개수 또는 파란색 종이 개수를 증가시키고 종료.하나의 색깔이 아니라면 4등분(재귀 호출)N × N 크기의 종이를 N/2 × N/2 크기의 네 개의 부분으로 나누고,각각을 재귀적으로 검사.이 때 4등분으로 나누는..
개요하노이 탑 알고리즘은 다음과 같은 규칙을 가집니다.한 번에 하나의 원반만 이동 가능큰 원반이 작은 원반 위에 올 수 없음이러한 규칙을 보면 맨 위의 원반부터 이동하므로 선입선출 구조인 큐나 배열의 사용을 고려할 수 있습니다. 하지만 하노이 탑은 대표적인 재귀 문제로 알려져 있습니다. 본 글에서는 하노이 탑 알고리즘에서 재귀 호출이 더 적합한 이유에 대해서 정리하고자 합니다. 왜 하노이 탑 문제에서 재귀를 사용해야할까❓ 하노이 탑 문제 간단 소개하노이 탑은 세 개의 기둥과 크기가 다른 원판들로 구성된 퍼즐입니다.모든 원판을 처음 기둥에서 마지막 기둥으로 옮기되, 큰 원판 위에 작은 원판만이 올 수 있습니다.이러한 분할 정복(Divide and Conquer) 방식은 재귀 호출과 자연스럽게 어울립니다.1..
문제설명입력 & 출력나의 풀이접근 방식이번 "백준 - N과 M(2)" 문제는 다음의 조건을 만족하는 수열을 출력하는 문제입니다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다. [백준, 15649번] N과 M(1) (백트래킹, Java)문제설명입력 & 출력나의 풀이이번 "백준 - N과 M (1)" 문제는 1부터 N까지의 자연수 중에서 길이 M인 순열을 모두 구하는 문제입니다. 문제 접근 방식1. 순열 생성길이 M의 순열을 구성해야 하므로pixx.tistory.com 위 N과 M (1)문제와 다른 점은 오름차순이라는 점입니다. 순열 문제로, 순서를 고려하여 모든 경우를 출력합니다. 따라서 아래와 같은 결과가 나옵니다.1 21 31 42 12 32 43 13 23 4..
백트래킹(Backtracking) 알고리즘이란 ❓백트래킹(Backtracking)은 문제 해결을 위한 탐색 기법 중 하나로, 재귀적 탐색과 되돌리기(backtrack)를 활용하여 최적의 해를 찾는 방법입니다. 많은 최적화 문제, 조합 문제, 순열 문제 등에서 널리 사용되며, 가능한 해를 하나씩 시도하면서 해가 될 것 같지 않으면 더 이상 탐색하지 않고 되돌아갑니다. 여기서 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)라고도 합니다. 백트래킹(Backtracking)의 기본 개념백트래킹은 탐색 트리에서 깊이 우선 탐색(DFS) 방식으로 진행되며, 각 노드에서 가능한 모든 선택을 해본 후, 그 선택이 잘못된 경로일 경우에는 다시 되돌아가서 다른 선택을 시도하는 방식입니다. 이..
