Algorithm/완전탐색
BOJ 15686 치킨 배달
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 아이디어 1. map을 돌면서 집과 치킨집의 좌표를 저장 2. 저장해둔 리스트에서 치킨 집을 M개 선택 - 중복없이 순서 상관 없이 뽑는 조합문제 2. 각 경우마다 치킨 거리를 구해 최솟값 갱신 처음에 map을 보자마자 고정관념으로 map 전체를 돌면서 완전탐색을 해야할 거라고 생각했는데 그렇게 하면 너무 복잡해진다. 어짜피 거리를 구하는 문제이기 때문에 거리 구하는 공..
BOJ 2661 - 좋은 수열
https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 아이디어 먼저 조건 없이 생각해보면 숫자 1, 2, 3 중에서 중복을 허용하여 N개를 순서있게 나열하는 백트래킹 문제이다. 이 문제의 조건은 나쁜 수열을 제외하고 좋은 수열 중 가장 작은 수를 출력하는 것이다. 길이가 N인 수열에서 임의의 길이의 인접하는 두 개의 동일한 수열이 있는 경우를 나쁜 수열이라고 한다. 백트래킹을 통해 방문하면서 check 함수를 통해 좋은 수열만 다음 탐색으로 넘어갈 수 있도록 해..
BOJ 2529 - 부등호
2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 아이디어 탐색 일단 조건을 생각하지 말고 0~9까지의 숫자를 중복없이 순서있게 나열한다. private static void rec_func(int k) throws IOException { if (k == M + 1) { // 조건 } else { for (int i = 0; i 0) && (inequality[i] == '>')) { possible = true; } else { possible = false; } if (possible == false) { break;..
BOJ 2580 - 스도쿠
2580번: 스도쿠 (acmicpc.net) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 아이디어 재귀로 완전탐색하는 부분과 위의 2조건을 판단하는 부분을 따로 만들어 생각한다. 탐색 부분 행과 열을 전체적으로 돌면서 탐색하니까 재귀함수 rec_func의 파라미터는 행과 열로 지정해주었다. private static void rec_func(int row, int col) 먼저 row 행을 기준으로 col 열을 1열부터 9열까지 돌면서 숫자가 채워지지 않은 부분 (0인 부분)을 찾아서 for문으로 1~9까..
BOJ 10819 - 차이를 최대로
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 아이디어 N개의 정수를 중복을 허용하지 않고 순서있게 나열하는 순열문제이다. 먼저 가능한 순열을 완전탐색을 통해 다 뽑고 난 후 주어신 식에 대입해서 최댓값을 갱신한다. 시간복잡도 N의 최댓값은 8 이므로 순열의 시간복잡도인 O(N!)에 대입하면 8! < 1초라서 가능한 접근법이다. 구현 import java.io.*; import java.util.StringTokenizer; public class Main..
BOJ 1759 - 암호 만들기
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 아이디어 일단 먼저 최소 한개의 모음과 최소 두 개의 자음이라는 조건을 제외하고 생각해보자 서로 다른 C개의 알파벳 소문자들 중 L개를 중복없이 사전순으로 순서있게 나열하는 순열 문제이다. C개의 알파벳을 먼저 정렬한 후 중복없이 사전순으로 조합을 짜기 위해 prev 인자를 통해 k자리의 다음 자리인 k+1 자리는 prev +1 부터 탐색하도록 설정해서 완전 탐색으로 모든 경우의 수를 구한다. 이제 여..
BOJ 14888 - 연산자 끼워넣기
14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 아이디어 주어진 순서를 바꾸면 안되니까 연산자만 순서를 잘 조합해서 숫자 사이사이에 끼워넣으면 된다. 연산자는 딱 N-1개만큼 주어지고 모두 사용해야 하니까 N-1개의 연산자를 순서있게 나열하는 순열문제이다. 연산자를 +, -, *. / 순으로 개수를 받으니까 +를 1, -를 2, *를 3, /를 4로 인덱스를 설정하고 이 인덱스들을 N-1개 만큼 순서있게 나열한 후 인덱스로 연산자를 불러와서 계산하면 된다...
BOJ 1182 - 부분수열의 합
1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. 아이디어 먼저 정답의 최대치 계산해보기 먼저 N의 최대치가 20이이니까 부분수열의 개수는 최대 2^20 -> int N 결정 부분수열의 합은 최대 20*1,000,000 -> int S 결정 N개의 정수를 중복을 허용하지 않고 합이 S가 되는 진부분수열을 구하는 문제 1~N 크기의 부분수열 전부 체크해서 합이 S가 되는 경우 찾으면 되겠다!!! 부분 수열은 중복을 허용하지 않고 순서도 고려하지 않기 때문에 조합으로 구하면..
BOJ 14889 - 스타트와 링크
14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다. 스타트 팀: S12 + S21 = 1 + 4 = 5 링크 팀: S34 + S43 = 2 + 5 = 7 1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다. 스타트 팀: S13 + S31 = 2 + 7 = 9 링크 팀: S24 + S42 = 6 + 4 = 10 1. 아이디어 모든 N은 짝수이고 N/2명씩 팀을 짜니까 N개의 자연수에서 중복을 허용하..
BOJ 15666 - N과 M (12)
15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 1. 아이디어 N개의 자연수 중 중복을 허용하여 M개를 골라 순서있게 나열하는 중복순열 문제이다. 비내림차순이어야 하니까 재귀호출 시 prev를 넘겨주어 탐색하는 다음 자리는 이전 자리보다 큰 수, 즉 prev+1부터 탐색하도록 설정한다. N개의 자연수 중 같은 수가 여러번 나올 수 있다는 것을 생각해야 한다. N이 1 7 9 9 이고 M이 2인 경우를 생각해보면 1 1 1 7 1 9 1 9 7 7 7 9 7 9 9 9 9 9 9 9 문제의 조건이 중복되는 수..