코딩테스트 검색 결과

해당 글 93건

[BOJ 7576] (DFS/BFS) 토마토 (C++) - (최적화)

토마토(Silver 1) 문제 전체 문제 보기 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 접근법 이 문제는 7569번 토마토 문제와 동일하다. 7569번 토마토 문제는 3차원 공간에서 BFS로 풀이하는 문제이고 이번 문제는 오히려 조금 더 쉬운 2차원 공간에서 BFS로 풀이하는 문제이다. 그래서 접근법에 대한 설명은 7569번 토마토 풀이글을 참고하자 최적화 7569번 토마토 문제 풀고 조금 더 쉬운 이번 문제를 다시 풀게되어 이번에는 조금 더 시간을 줄일 수 있도록 최적화 부분에 조금 ..
Algorithms/DFS & BFS 2021. 8. 19. 12:08

[BOJ 2178] (DFS/BFS) 미로 탐색 (C++)

미로 탐색 (Silver 1) 문제 전체 문제 보기 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근법 이 문제에서 구해야 하는 값은 미로를 탈출하기 위해 필요한 최단경로의 길이이다. 최단 경로의 길이를 구하기 위해서는 DFS보다 BFS를 활용해야 한다. 너비 우선으로 탐색하는 BFS에서 탐색 깊이는 항상 최단거리를 보장하기 때문이다. 하지만 DFS는 최단 경로를 보장하기보단 하나의 경로를 끝까지 탐색하기 때문에 최단경로를 두고 다른 경로로 탐색을 완료할 위험이 있다. 아래와 같은 상황을 살펴보자. 이 미로에서는 위에 초록색 경로가 최단..
Algorithms/DFS & BFS 2021. 8. 18. 14:06

[BOJ 9461] 파도반 수열(C++)

파도반 수열(Silver 3) 문제 전체 문제 보기 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 접근법 파도반 수열은 다음과 같다. 1 1 1 2 2 3 4 5 7 9 12 16 21 28 37 49 파도반 수열의 규칙을 쉽게 찾을 수 있다. 임의의 위치 \(n\)에서 수열의 값을 \(f(n)\) 이라고 했을 때 \(f(n)\) 은 \(f(n-2)\) 와 \(f(n-3)\)의 합으로 이루어져 있다. 문제에서 주어진 삼각형 그림을 보면 \(f(n)\)은 \(f(n-1)\)과 \(f(n-5)\)번로 표현되어 있는데..
Algorithms/DP 2021. 8. 17. 09:57

[BOJ 1904] 01타일(C++)

01타일 (Silver 3) 문제 전체 문제 보기 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 접근법 이번 문제에서 구해야 하는 값은 1 타일과 00 타일을 활용해서 자릿수 N이 주어졌을 때 지원이가 만들 수 있는 모든 이진수 가짓수이다. 여기서 N의 값은 1,000,000 이하의 자연수로 꽤 크다. 그래서 자릿수 N이 주어졌을 때 지원이가 만들 수 있는 이진수의 최댓값은 \(2^1,000,000\)으로 모든 경우의 수를 따져보는 것은 불가능하다. 때문에 우리는 임의의 N에서 만들 수 있는 이진수의 가짓수 규칙..
Algorithms/DP 2021. 8. 16. 23:16