백준 검색 결과

해당 글 78건

[BOJ 12100] 2048(Easy) (C++)

2048(Easy) (Gold 2) 문제 전체 문제 보기 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 접근법 가장 큰 블록의 값을 구하기 위해서 좌우상하로 최대 5번까지 이동할 수 있습니다. 총 \(4^5 =1,024\)개의 경우의 수가 나오기 때문에 모든 경우의 수를 완전탐색하여 문제를 해결할 수 있습니다. 모든 경우의 수를 완전탐색하기 위해서는 백트레킹을 활용할 수 있습니다. 백트레킹에서 다음과 같이 탐색을 진행하여 문제를 해결했습니다. 깊이가 5라면 현재 레벨에서 가장 큰수..
Algorithms/Backtracking 2021. 9. 27. 10:47

[BOJ 13460] 구슬 탈출 2 (C++)

구슬 탈출 2 (Gold 2) 문제 전체 문제 보기 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 접근법 보드를 상하좌우 중 한번 기울일 경우 구슬들의 위치가 변합니다. 각 구슬들의 위치를 이동할 수 있는 하나의 노드로 보고 한번 기울여 이동된 구슬의 위치를 인접 노드로 생각하여 BFS로 풀 수 있습니다. BFS를 활용하여 보드를 기울일 수 있는 다양한 경우의 수 중 R만 구멍에 들어갈 수 있는 최단 거리를 구할 수 있습니다. BFS의 알고리즘의 기본적인 구조..
Algorithms/DFS & BFS 2021. 9. 26. 14:36

[BOJ 16236] 아기 상어(C++)

아기 상어 (Gold 4) 문제 전체 문제 보기 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 접근법 이번 문제는 BFS를 활용하여 풀 수 있습니다. 그리고 구현할 것이 상당히 많은 문제입니다. 그리고 먹이를 한번 먹을 때마다 BFS 탐색을 진행하기 때문에 탐색량도 많은 문제입니다. 하지만 정상적으로 구현하였다면 C++ 기준으로 0ms가 나오기 때문에 시간 초과가 발생하였다면 로직의 문제로 무한 루프가 형성되었을 가능성이 큽니다. 쉽게 놓칠 수 있는 부분이 문제에서 상어의 위치를 9로 주어졌는데, 먹이..
Algorithms/DFS & BFS 2021. 9. 25. 17:20

[BOJ 14500] 테트로미노(C++)

테트로미노(Gold 5) 문제 전체 문제 보기 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 접근법 이번 문제는 테트로미노로 만들 수 있는 모든 모양으로 모든 위치에서 탐색을 수행하여 풀 수 있는 Brute Force 문제입니다. 완전 탐색을 하기 위한 테트로미노 모양을 만들어 내는 방법이 조금 까다로운 구현 문제입니다. 우선 테트로미노 블록은 회전과 대칭을 통해서 만들 수 있는 모양이 총 19가지입니다. 전체 위치는 500 * 500 이기 때문에 각 위치별 19번씩 탐색을 진행하더라도 충분히 시간 내에 탐색..
Algorithms/Brute Force 2021. 9. 25. 12:13