본문 바로가기

완전탐색

 (5)
[C++/PGS] Lv.2 : 전력망을 둘로 나누기 (완전탐색/bfs/dfs) https://school.programmers.co.kr/learn/courses/30/lessons/86971 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가능한 비슷하도록 두 전력망으로 나누었을 때, 두 전력망이 가지고 있는 송전탑 개수의 차이(절대값)를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 2 이상 100 이하인 자연수입니다. wires는 길이가 n-1인..
[C++/BOJ] 1107 : 리모컨 (완전탐색) https://www.acmicpc.net/problem/1107 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤..
[C++/BOJ] 10971 : 외판원 순회 2 (완전탐색, dfs, Backtracking) https://www.acmicpc.net/problem/10971 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가..
[C++/BOJ] 9663 : N-Queen (완전탐색, Backtracking) https://www.acmicpc.net/problem/9663 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 문제 힌트에 퀸의 Show must go on 노래가 있길래 신나게 들으면서 풀었음 백준 티어 골드4, 완전탐색 + 백트래킹 문제이다. 처음에 백트래킹 알고리즘으로 풀긴 풀었지만 재귀 과정이 잘 이해가 안되었는데, 어떤 동영상의 아래 그림을 보고 바로 이해가 되었다. 재귀의 흐름과 끊김을 바로 볼 수 있는 그림이다! main ide..
[코드트리] Backtracking - 백트래킹 / 재귀 연습문제 백트래킹. 대충 알고있는건 백트래킹 == 완전탐색(모든 경우의 수를 무식하게 찾기)에서 가지치기로 효율 높임 이정도라서..ㅋㅋ 연습문제도 풀어봐야겠다 대부분의 알고리즘 문제들은 원하는 모든 조합을 만들어 그 중 문제에서 원하는 답을 고르는 식으로 해결이 가능합니다. 만약 n 제한이 작고, 모든 조합을 만드는 데 걸리는 시간이 문제에서 주어진 제한 시간보다 더 작다면, 항상 모든 조합을 다 만들어 보는 것이 가독성 측면에서나, 코드를 작성하는 입장에서 가장 좋다고 할 수 있을 것입니다. 다만, (1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 2, 1), (1, 1, 1, 2, 2), .. 등 여러 가능한 순열과 조합을 만드는 것을 for문 만을 ..
728x90

티스토리툴바