탐색

탐색

    백준 14500 / 테트로미노 / Brute Force / JAVA / 골드 5

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

    백준 1507 / 플로이드 와셜(Floyd Warshall) 알고리즘 / JAVA

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

    백준 9202 / 트라이(Trie), DFS / JAVA

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