전체 글 검색 결과

해당 글 200건

알고리즘 풀이 - 백준 1987(알파벳, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 RxC 크기의 보드의 각 위치에 대문자 알파벳이 하나씩 있고, 좌측 상단에 말이 있다면 상하좌우로 움직여 지금까지 지나오지 않은 알파벳으로만 이동 가능할 때, 최대 이동 가능한 칸 수를 구하는 문제 2. 풀이 ① 완전 탐색 이용하기 이 방법은 굉장히 쉽다. 알파벳은 총 26개 이므로 26크기의 boolean 배열을 만들고 사용된 알파벳의 위치는 true로 바꾸어가며 탐색을 수행하면 된다. 재귀를 이용하여 각 위치를 탐색한 뒤 그 결과가 최대값이 되는 경우를 저장한 뒤 출력한다. 하지만 최대 20x20이기 때문에 모든 탐색을 수행하게 되면 시간이 매우 오래 걸린다. 따라서 ..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 16:20

알고리즘 풀이 - 백준 4574(스도미노쿠, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 1~9의 숫자의 위치와 도미노의 위치가 주어질 때, 스도쿠를 풀고난 뒤 그 결과를 출력하는 문제 2. 풀이 관련 문제인 스도쿠 문제는 여기서 참조 가능 스도미노쿠는 스도쿠를 풀되 2개의 숫자가 이어진 도미노를 모두 놓아서 해결할 수 있는 경우를 찾는 문제이다. 우선 주어진 도미노와 1~9의 숫자를 스도쿠 상에 위치시키고 사용 가능한 도미노를 위치시켜 전체 문제를 풀 수 있는 경우에 출력을 한다. 9x9가 고정이므로 81을 이용해 9로 나누어 행(y) 좌표, 9로 나눈 나머지를 열(x) 좌표로 구할 수 있으며 이를 통해 해당 위치가 0이라면 인접 비어 있는 위치까지 찾아서 ..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 15:51

알고리즘 풀이 - 백준 2580(스도쿠, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 9줄에 걸쳐 스도쿠 상태값이 주어질 때, 스도쿠를 채워 넣는 경우를 출력하는 방법 2. 풀이 스도쿠를 풀 수 있는 경우의 수만 주어질 때, 스도쿠를 풀고 그 결과를 출력하는 문제로 현재 숫자가 들어있지 않은 모든 위치를 list에 저장한 뒤 각 위치에 넣을 수 있는 숫자를 조사하여 넣는 방식이다. 숫자가 지정되지 않은 list의 index를 재귀함수로 전달하고 모든 index 위치에 숫자가 들어갔다면 해당 결과를 출력하면 된다. 풀이 방식은 다음과 같다. ① 2차원 배열을 9x9 크기로 생성하여 주어진 값들을 모두 저장하되, 숫자가 0인 위치는 별도 list로 저장한다. ..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 14:44

알고리즘 풀이 - 백준 9663(N-Queen, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N-Queen 문제로 NxN 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 경우의 수를 구하는 문제 2. 풀이 유명한 N-Queen 문제이다. NxN 체스판에 가능한 모든 경우에 퀸의 위치를 검사해 그 경우가 서로를 공격할 수 있는 위치라면 위치시키지 않고 가능한 경우만 체크하여 모든 경우의 수를 구하는 문제이다. 재귀로 간단히 풀 수 있다. 체크해보자. ① 체스판의 크기를 입력받아 그 크기에 맞은 2차원 배열을 생성한다. ② (0, 0) 부터 시작하여 퀸을 위치시키도록 재귀함수에 현재 퀸을 위치시킬 Column 번호를 전달하여 시작한다. ③ 현재 Column에서 각..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 14:16

알고리즘 풀이 - 백준 16198(에너지 모으기, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N개의 에너지 구슬이 일렬로 모였을 때, 처음과 마지막을 제외한 1개를 제외 시, 양 좌우의 곱의 에너지를 얻을 때, 이 작업을 반복하여 얻을 수 있는 최대의 에너지를 구하는 문제 2. 풀이 중간에 위치한 구슬을 제거하고 양 옆의 구슬의 수치를 곱하여 에너지를 획득하는 문제로, 2개만 남을 때까지 모든 경우의 수를 다 체크하여 최대가 되는 경우를 출력하는 문제이다. 재귀 방식을 사용하여 구슬을 제거하는 모든 순서를 체크하여 그 중 최대의 에너지를 얻게 되는 경우를 찾아 출력하였다. 풀이 방식은 다음과 같다. ① 각 구슬의 무게를 배열에 저장한다. ② 현재 에너지, 제거되지..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 14:09

알고리즘 풀이 - 백준 16197(두 동전, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 NxM 크기의 보드와 4개의 버튼으로 이루어진 게임에서 벽, 동전, 빈칸이 있을 때, 동전은 2개가 주어져 위치한다고 하는 경우 최소한의 움직임으로 동전을 1개만 외부로 떨어뜨리는 움직임의 횟수를 구하는 문제 2. 풀이 완전 탐색 기법을 통해 시뮬레이션으로 구현하는 방식으로 해결한 문제이다. 실제로 모든 방향으로 동전을 이동시킨 뒤, 1개만 떨어지는 모든 경우를 체크하여 그 경우가 최소가 되는지를 조사하였다. 10회 이상 움직였거나 현재의 최소값 이상으로 움직인 경우에는 추가 탐색을 종료한다. 해결한 방법은 다음과 같다. ① 각 동전의 초기 위치를 저장할 별도 Class를..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 14:01

알고리즘 풀이 - 백준 15658(연산자 끼워넣기 (2), 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 N개의 수와 N-1개 이상, 4N개 미만의 연산자가 주어졌을 때, 연산을 수행하는 경우에 따라 최소/최대값을 구하는 문제 2. 풀이 숫자 N개가 주어질 때, 4N이하의 연산자가 주어진다면 연산자를 어떻게 배치했을 때 결과가 최대 / 최소값이 되는 지를 구하는 문제이므로 완전 탐색을 통해 해결할 수 있다. 단순히 재귀를 통해 전체 숫자가 N개이므로 N-1개의 연산자를 각 위치에 모두 대입하여 그 결과를 구한 뒤 출력하면 해결할 수 있다. 3. 코드 아래의 코드를 통해 정답을 알아보자. import java.io.*; import java.util.*; public class..
카테고리 없음 2021. 3. 28. 13:50

알고리즘 풀이 - 백준 14225(부분수열의 합, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 수열 S가 주어질 때, 수열 S의 부분 수열의 합으로 불가한 자연수 중 가장 작은 수를 구하는 문제 2. 풀이 완전 탐색을 통해 주어진 모든 숫자들의 합을 다 시도하고 그 중 나오지 않은 가장 작은 자연수를 출력하는 문제이다. 재귀 또는 비트마스크, 순열 등 완전 탐색의 갖은 방법으로 문제를 해결할 수 있지만 아래에선 재귀 , 비트마스크만 사용하였다. ① 재귀로 풀기 재귀를 통해 다음 탐색할 index값을 전달하여 현재 사용되지 않은 숫자들을 더할 때마다 그 결과를 boolean 배열에 저장하여 문제를 해결한다. ② 비트마스크로 풀기 숫자가 3개라면 총 000 ~ 111까..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 13:44