전체 글 (229) 썸네일형 리스트형 [백준][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`)).. [백준][KOTIN][10972] 다음 순열 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 다음 순열에 대한 규칙을 이해하고 있을 때 문제를 접근할 수 있다. 1. 주어진 순열(number)을 오른쪽에서 부터 탐색하여 number[i] > number[i - 1] 위치를 찾는다. 2. 1번에서 구한 위치를 기준으로 순열을 나눈다. 3. 왼쪽의 순열에서 가장 마지막 인텍스의 값(a)과 오른쪽 순열에서 오른쪽 부터 탐색하여 (a) 보다 큰 값의 인덱스(b)를 찾는다. 위의 그림에서 4가 해당 된다. (a)와 (b) 를 swap 한다. 4... [백준][1748][KOTLIN] 수 이어 쓰기1 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 문제 풀이 1. 각 자리수가 같은 숫자의 범위를 탐색하여 결과를 구한다. 2. 입력이 1억이므로 전체 탐색을 해도 시간 초과 되지 않는다. 코드 import java.io.* fun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`)) val N = br.readLine() var result = 0 if (N.length == 1) { result = N.toInt() } else { for (i in 1..N.toInt()) { if.. [백준][9095][KOTLIN] 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 1. 주어진 문제를 푸는 방법은 두 가지가 있다. 2. 첫번째는 1을 만드는 개수 2를 만드는 개수 3을 만드는 개수 4를 만드는 개수를 구해 본다. 2-1. 1 -> 1 2 -> 2 3 -> 4 4 -> 7 2-2. 2-1 과정에 DP 를 이용하여 아래의 점화식을 구할 수 있다. DP[n] = DP[n - 3] + DP[n - 2] + DP[n - 1] 3. 두번째는 dfs 를 이용한 완전 탐색을 통해서 경우의 수를 구한다. 3-1. 처음 시작을 0으로 해서 현재의 합과 입력값이 n.. [백준][2309][KOTLIN] 일곱 난쟁이 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 문제 풀이 1. 처음에 접근할 때 9명의 난쟁이 중 7명을 뽑아서 합을 구하는 것으로 접근했다. 2. 1번과 같이 접근하기 위해서 백트래킹을 이용한 조합을 통해서 7명의 배열을 구하고 합이 100인 배열을 구했다. 3. 위와 같이 할 경우 경우의 수가 너무 많고 각 배열의 합을 다시 확인해야 해서 비효율적이다. 4. 9명의 전체 키의 합을 구한 뒤 이중 for 문을 이용하여 2명의 키를 뺀 합이 100인 .. [백준][17413] 단어 뒤집기2 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 풀이 1. 문제 조건을 문자열의 char 를 하나씩 탐색하여 구현할 경우 시간 초과가 발생한다. 2. 문자열을 검색할 때 첫 문자가 " [백준][KOTLIN][1406] 에디터 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 풀이 1. substring 을 이용해서 문자열을 변경하여 구현할 경우 시간초과가 발생한다. 2. left/right stack 을 정의해서 처음으로 입력된 문자열을 left stack 에 저장한다. 3. 편집기의 명령어가 "L" 일 경우 커서가 왼쪽으로 한 칸 이동했으므로 left stack 의 top 값을 빼서 right stack 에 저장한다. 이때 left stack 이 비어있으면 조건.. 이전 1 ··· 9 10 11 12 13 14 15 ··· 29 다음
