본문 바로가기

완전탐색

 (34)
[백준 / BOJ] 17182 우주 탐사선 (완전탐색) 문제 출처 : https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위 www.acmicpc.net 우주탐사선 ans호가 있다. ans호는 N개의 행성을 모두 탐사하는데 걸리는 최소시간을 계산하려한다. N개의 행성끼리 이동하는데 걸리는 시간이 주어질때 모든 행성을 탐사하기 위한 최소 시간을 출력하는 문제다. 풀이 플로이드 와샬로 최단경로를 만들어주고, 비트마스킹을 이용한 완전탐색으로 답을 찾은 문제다. (거의 3달만의 플로이드 와샬이라 알고리즘조차 가물 가물했다..) N이 최..
[백준 / BOJ] 16137 견우와 직녀 문제 출처 : https://www.acmicpc.net/problem/16137 16137번: 견우와 직녀 견우와 직녀는 여러 섬과 절벽으로 이루어진 지역에서 살고 있다. 이 지역은 격자로 나타낼 수 있으며, 상하좌우로 인접한 칸으로 가는 데 1분이 걸린다. 7월 7일은 견우와 직녀가 오작교를 건너 www.acmicpc.net 견우와 직녀는 여러 섬과 절벽으로 이루어진 크기 N*N 지역에 살고있다. 견우는 0,0에, 직녀는 N,N에 살고있다. 까치들은 견우와 직녀를 만나게해주기위해서, 오작교를 만드는데, 오작교는 T주기마다 생성되며, 1분동안 유지된다. 견우는 오작교를 2번이상 연속적으로 건널수없으며, 추가적으로 임의의 절벽에 다리를 하나 생성해서 건널수있다. 단, 다리를 생성할때, 교차로에는 짓지못하..
[백준 / BOJ] 1240 노드사이의 거리 문제 출처 : https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net N개의 노드로 이루어진 트리가 주어지고, M개의 쿼리가 주어질때, 노드 사이의 거리를 구하는 프로그램을 만드는 문제다. 풀이 트리 + 완전탐색 문제다. N이 1000, M이 1000으로, 한번탐색할때마다 최대 1000번 반복한다고 가정했을때, 최악의경우, 1000*1000번 반복하므로 시간복잡도는 O(NM)이 된다. 트리구조를 만든다음에 A위치에서 시작했을때, B위치에 도달했을때의 거리를 구하면된다. 거리구하는 소스코드 priv..
[백준 / BOJ] 17281 ⚾ (야구) 문제 출처 : https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 게임은 N개의 이닝으로 이루어져있다. 우리는 9명이 선수가 각 이닝에 얻는점수를 알고있다. 각 선수의 순서를 적절히 배치하여 (1번부터 9번까지) 얻을수있는 최대 점수를 구하는 문제다. 풀이 완전탐색으로 푼 문제다. 모든 선수의 배치가능한 조합을 구한후, 구해진 조합을 토대로 점수를 구하면 된다. 선수는 9명이지만, 1..
[백준 / BOJ] 16918 봄버맨 (Java) 문제 출처 : https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net R*C그리드가 있다. 0 초 - 봄버맨은 초기에 폭탄을 하나 설치한다. 1 초 - 봄버맨은 초반 1초에는 아무것도 하지않는다. 2 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다. 3 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다. 4 초 - 봄버맨이 폭탄이 없는곳에 폭탄을 설치하고 3초전에 설치한 폭탄을 터트린다. . . . 위 과정..
[백준 / BOJ] 9881 Ski Course Design (Java) 문제 출처 : https://www.acmicpc.net/problem/9881 9881번: Ski Course Design Farmer John has N hills on his farm (1
[백준 / BOJ] 9874 Wormholes (Java) 문제 출처 : https://www.acmicpc.net/problem/9874 9874번: Wormholes Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2
[백준 / BOJ] 14500 테트로미노 문제 출처 : https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net N*M크기의 종이에 숫자들이 쓰여있다. 이 종이에 테트로미노하나를 놓았을때, 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 찾는 문제다. 소스코드 완전탐색으로 푼 문제다. 종이의 세로,가로가 각각 최대 500이며, 한번 탐색마다 (모든 폴리오미노를 본다했을때,) 40번이라고 하면, 총 탐색횟수는 250000*40 = 10000000가 되어서 시간초과를 피할수있..

티스토리툴바