본문 바로가기
728x90

알고리즘(w.KOTLIN)/탐색

 (23)
[백준][KOTLIN][14391] 종이 조각 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 문제 풀이 1. 처음에는 N, M 중 큰 값을 기준으로 자르면 무조건 최대 값인줄 알고 풀었다. 반례가 있다는 것을 알지 못했는데 아래의 경우 길이를 길게 자른다고 최대가 되지 않는다. (가로 4, 세로 3으로 짤라야 최대 값이 나온다. 2. N, M 의 최대 값이 4이고 가로/세로 반복이므로 2^(N * M) 의 경우의 수를 가진다. 3. 모든 경우에 대해서 완전 탐색을 수행한다. (i : 행..
[백준][KOTLIN][2529] 부등호 https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 문제 풀이 1. 주어진 입력을 DFS 를 이용하여 완전 탐색 한다. 2. 이때 입력된 부등호에 따라 이전 result 에 저장된 마지막 숫자와 입력으로 들어오는 숫자의 크기를 비교하여 result 에 넣을 수 있는 값인 지 확인 한다. 3. result 크기가 k + 1 일 때 최대/최소 값을 비교하여 저장한다. 이때 최소값의 경우 예제에서 0이 들어가므로 String 으로 저장하고 9자리 숫자..
[백준][KOTLIN][15661] 링크와 스타트 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 문제 풀이 1. 14886 과 유사한 문제로 팀을 나눌 때 동일한 인원 수가 아닌 한 팀이 1명에서 부터 (N-1)명까지 팀이 될 수 있는 부분을 추가한다. 코드 import java.io.* var result15661 = Int.MAX_VALUE fun main(args: Array) { val br = BufferedReader(InputStrea..
[백준][KOTLIN][14889] 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 풀이 1. 팀의 수 N 에 대해서 N/2 의 개수를 구하는 조합의 경우의 수를 DFS 를 이용하여 구한다. 2. visit 배열을 이용하여 방문된 index 를 startTeam 이라고 생각하고 방문하지 않은 index 를 linkTeam 이라고 생각한다. 2-1. 내가 짠 코드에서는 방문 배열 visit 를 이용하지 않고 startTeam/linkTeam 을 List 에 저장하여 코딩하여 좀 더 복잡해 졌다. ..
[백준][KOTLIN][14501] 퇴사 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이 1. 문제에서 주어지는 N 이 15까지 주어져 있다. 2. 2^15 을 다 탐색해도 1억이 넘지 않아 시간 초과가 발생하지 않으므로 DFS 를 통해서 완전 탐색한다. 3. 탐색 시 2가지 경우에 대해서 탐색 한다. 3-1. 면담을 시작할 경우 : DFS(Day + T[Day], Sum + P[Day]) 3-2. 면담을 하지 않고 다음 날로 넘어간 경우 : DFS(Day + 1, Sum) 4. 3번의 과정을 모두 탐색하고 Day 가 N보다 크거나 같을 경우 면담을 완료하고 퇴사를 한 경우이므로 최대 값인 지를 결과에 저장한다..
[백준][KOTLIN][1759] 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제 풀이 1. 주어진 입력 문자열을 오름 차순으로 정렬 한다. 2. 정렬된 문자열을 DFS 를 이용하여 완전 탐색 한다. 이때 암호 중 acis 왕 acsi 는 같은 경우로 판단하기 때문에 DFS 탐색 시 탐색 index 를 0 이 아닌 다음 탐색 index 를 시작으로 한다. 3. 결과 출력 시 최소 모음 1개 이상이고 자음 2개 이상인 지 확인 후 결과를 출력한다. 코드 import java.io..
[백준][KOTLIN][10971]외판원 순회2 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 풀이 1. 첫번째 도시 부터 N 번째 도시까지 하나씩 출발 도시로 선택한다. 2. dfs 를 이용하여 순회여행 경비의 최소값을 찾는다. 2-1. dfs 인자로 N(도시의 개수), VISIT(방문 도시 여부), W(도시 이동 비용), depth(방문한 도시 개수), sum(현재까지의 비용 총합) 넘겨 준다. 2-2. 1번 탐색 시 출발도시를 firs..
[백준][KOTLIN][10819] 차이를 최대로 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 풀이 1. 주어진 배열 A 를 반복을 허락하지 않고 DFS 를 이용하여 나올 수 있는 배열의 경우를 구한다. 2. 1번에서 구해진 각 배열에서 "차이의 최대 값"을 구한다. 코드 import java.io.* var answer10819 = Int.MIN_VALUE fun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`))..

티스토리툴바