완전탐색

백준 16234번: 인구이동(javascript, BFS, 완전탐색)

완전탐색이며 BFS로 풀 수 있는 문제이다. 물론 DFS로도 풀어도 되지만 문제 조건에 인접한 국가만 국경을 열 수 있다는 점에서 넓이 우선 탐색이 좀 더 직관적으로 풀 수 있다고 생각해 BFS로 접근하여 풀었다. 예제에서 N이 3이상인, 즉 인구이동이 다른 구역에서 동시에 일어날 때 인구가 어떻게 합쳐지는 지에 대한 설명이 없어 디버깅에 조금 어려움을 겪었던 문제였다. 물론 예제 4,5를 통해 알수는 있지만 그 과정을 일일히 찾기에 어려움이 있었다. 예제 4,5에서 인구이동이 일어나는 과정을 적은 글이 있어 이 문제를 푸는데 어려움을 겪는 사람이 있다면 참고하면 디버깅에 도움이 될 것 같다. const fs = require('fs'); const input = fs.readFileSync("/dev/..

백준 2589번: 보물섬(javscript, BFS, 완전탐색)

전형적인 BFS이며 브루탈 포스(완전탐색) 문제이다. 문제에서 보물이 묻혀있는 곳 두 거리간의 최단거리를 요구하고 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 최단거리로 이동할 수 있는 방법은 BFS 알고리즘이다. 왜 BFS알고리즘이 최단거리인지는 트리를 어떻게 탐색하는 지를 생각해보면 쉽게 이해할 수 있다. 따라서 이 문제는 완전탐색을 통해 BFS로 육지마다 다른 육지들로 이동할 때의 거리들 중 최대거리를 구하면 그 값이 답이 된다. 또한 BFS는 DFS와 다르게 한번의 이동에 주변을 다 탐색하므로 이동할 때마다 이동거리를 증가시키면 안되고 이전 이동거리에 1을 더해서 이동거리를 계산해야 한다. 위 생각을 토대로 짠 코드는 다음과 같다. 주의할 ..

백준 17135번: 캐슬 디펜스 (파이썬, 완전탐색, 구현)

정말 어려운 문제였다. 처음 문제를 봤을때 완전탐색 혹은 DP중에 고민했는데 시간복잡도가 M개 중에 3 개를 뽑는 조합 mC3 = m(m-1)(m-2)/6, 적들이 N번 움직이므로 반복문 O(N), 사정거리 D만큼, M열에 대해 거리를 탐색해야 하니 O(N^2)으로 M= 15, N = 15일 때 455*15*15*10= 10^6으로 시간제한인 1초에 넉넉하게 맞출 수 있어 완전탐색으로 풀어야 겠다고 생각할 수 있었다. 그러나 구현 문제를 거의 처음 풀어봐서 시간이 오래 걸렸는데 반복문이 많이 중첩되다 보니 순서나 반복값에 있어서 헷갈림이 많았다. 알고리즘은 간단하다. 먼저 조합으로 [0:M]에 대해 3개를 뽑는다. 이때 궁수의 위치는 N행에 고정이므로 열의 크기에 대해서 조합을 뽑아야 한다. 그다음 적과..

백준 1198번: 삼각형으로 자르기 (파이썬, 완전탐색)

완전탐색 알고리즘으로 최댓값을 구하기 위해 꼭지점을 하나씩 지워가며 그 값들을 배열에 넣고, max함수를 이용해서 최댓값을 구하였다. 삼각형의 넓이는 꼭지점들이 주어지므로 꼭지점 공식을 이용하였다. N각형에서 나올수 있는 삼각형의 경우의 수(갯수)는 nC3이므로 n(n-1)(n-2)/6이다. 완전탐색으로 풀기 위하여 N각형에서 시계방향으로 점을 하나씩 지워가며 계산하였다. 오각형을 예시로 들자면 다음과 같다. 물론 완전탐색문제는 파이썬 library인 combination을 이용하여 풀수도 있다. 완전탐색이나 조합이나 가능한 모든 경우의 수를 구하는 것이기 때문이다. 조합을 이용하여 푼 풀이는 다음과 같다. from itertools import combinations import sys def tria..