탐색

오랜만에 백준 문제를 풀었다. Brute Force 부터 유형별로 차근차근 풀어보려 한다. 이 문제는 찐 Brute Force 문제이다. Brute Force는 하나하나 직접 다 해보는 방법을 말한다. 일반적으로 이 방법은 시간과 공간을 초과하기 때문에 만능은 아니지만.. 구현 방법이 떠오르지 않을 때는 가장 먼저 시도해 보면 좋은 방법이기도 하다. 이 문제는 5개의 테트로미노를 뒤집고 돌려서 종이에 놓았을 때 차지하는 4칸의 합을 가능한 경우 모두 구해준 뒤 가장 큰 값을 출력하면 된다. 테트로미노는 5개이지만 실제로 우리가 고려해야 하는 테트로미노는 다음과 같이 총 19개가 된다. 그리고 이 19개 각각에 대해 해당 종이(M*N)를 전부 돌면서 발생할 수 있는 모든 경우를 다 탐색해 주어야 한다. 이..

이번에 살펴볼 문제는 백준 1507번 궁금한 민호 문제이다. https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 이 문제는 플로이드 와셜 알고리즘을 통해 모든 경로를 탐색하여 푸는 문제이다. 모든 쌍의 최단 경로를 다 확인하는 문제로 이 알고리즘이 익숙하지 않으면 조금 생각하기 어려울 수도 있다. 먼저 플로이드 와셜 알고리즘에 대해 간단하게 설명한 후에 문제를 풀어 보도록 하겠다. 플로이드 와셜 알고리즘(Floyd Warshall Algorit..

오늘 살펴볼 문제는 백준 9202번 문제이다. https://www.acmicpc.net/problem/9202 9202번: Boggle 문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle로 이겨본 적이 없다. 이렇게 질 때마다 상근이는 쓰레기 버리기, 설거지와 같은 일을 해야 한다. 이제 상근이는 프로그램을 작성해서 부인을 이겨보려고 한다. Boggle에서 단어는 인접한 글자(가로, 세로, 대각선)를 이용해서 만들 수 있다. 하지 www.acmicpc.net 사실 이 문제는 굉장히 어려웠다. 그래서 나는 다른 분의 코드를 어느정도 참고해서 풀었다..