알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 검색 결과

해당 글 47건

알고리즘 풀이 - 백준 12100(2048 (Easy), 완전 탐색(시뮬레이션))

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 2048 게임 문제. 5번의 이동으로 얻을 수 있는 최대 큰 블록을 출력하는 문제 2. 풀이 이 문제는 시뮬레이션으로 해결하였다. 실제 모든 블록을 이동시켜 가면서 최대 값을 구하여 출력하는 문제이다. 시뮬레이션은 구현이 까다롭기에 푸는데 오래 걸렸다. 기본적으로 재귀를 통해 5번을 모두 이동시키고 이동이 끝났으면 최대값을 찾도록 한다. 이동하여 블록들을 위치시키는 것이 조금 구현에 까다롭다. 우선 아래의 그림을 통해 이해해보자. 아래의 예시에서는 동쪽으로만 이동시키는 경우를 통해 알아보자. 현재 Row / Column은 2중 반복문을 통해 각 Row, Column를 순회..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 17:34

알고리즘 풀이 - 백준 13460(구슬 탈출 2, 완전 탐색(시뮬레이션))

관련글 완전 탐색 포스팅은 여기를 참조 BFS 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 구슬을 굴려서 빨간 구슬만 구멍에 떨어뜨릴 수 있도록 최소한의 경우로 보드를 기울이는 문제 2. 풀이 이 문제는 시뮬레이션으로 해결했다. 시뮬레이션 문제는 실제 가능한 모든 방법을 직접 구현하여 체크해야 하는데 구현이 까다로워서 시간이 오래 걸렸다. 기본적인 아이디어는 다음과 같다. ① 최초 위치에서 동서남북 방향으로 구슬을 굴려 이동시킨다(벽에 닿거나 구멍에 떨어질 때까지). ② 구슬이 구멍으로 떨어진 경우를 체크한다. - 파란 구슬이 떨어진 경우 해당 방향으로 기울인 것은 답이 될 수 없으니 다음 방향으로 굴린다. - 빨간 구슬만 떨어진 경..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 16:56

알고리즘 풀이 - 백준 1062(가르침, 완전 탐색)

관련글 완전 탐색 관련 포스팅은 여기를 참조 1. 개요 문제의 링크는 여기를 참조 문제의 내용은 아래의 더보기를 클릭하여 참조 더보기 남극에 사는 선생님이 학생들에게 단어를 가르치는데, K개의 알파벳만 가르칠 수 있을 때, 전체 문자 중 가르칠 수 있는 문자의 최대 개수를 구하는 문제 2. 풀이 이 문제는 재귀를 통해 간단히 해결할 수 있다. 가르칠 수 있는 모든 알파벳의 경우를 체크하여 가르쳤을 때, 이해 가능한 모든 단어의 개수를 구하는 문제이다. 가르칠 알파벳을 26 크기의 배열로 저장하거나 비트마스크를 사용하여 해결할 수 있다. 간단한 문제이므로 코드를 통해 알아보자. 3. 코드 아래의 코드를 통해 정답을 알아보자. ① 완전 탐색 사용(Boolean 배열 이용) import java.io.*; i..
알고리즘 풀이(Problem Solving)/완전 탐색(Brute Force) 2021. 3. 28. 16:33

알고리즘 풀이 - 백준 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