알고리즘(w.KOTLIN)/탐색 (23) 썸네일형 리스트형 [백준][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인 .. [알고리즘][KOTLIN] 할인 행사 https://school.programmers.co.kr/learn/courses/30/lessons/131127 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1. 구매할 목록을 wantMap 에 저장한다. 2. discount 크기까지 매일 날짜가 바뀌는 것 간주하고 탐색 한다. 3. 구매할 물품의 목록(wantMap) 이 날짜가 변경되면 초기 저장값으로 되어야 하므로 또 다른 map 을 선언하여 copy 하여 사용한다. 4. 시작 날짜(i) 부터 10일간 탐색한다. 단, 탐색 index 가 discount 크기와 같을 경우 탐색을 종료한.. [알고리즘][KOTLIN]연속 부분 수열 합의 개수 https://school.programmers.co.kr/learn/courses/30/lessons/131701 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1. 중복을 허용하지 않기 때문에 Set 자료구조를 선언한다. 2. 연속된 수열의 길이 정의하는 length 를 선언하고 초기값을 1로 한다. 3. length 가 (elements + 1) 의 크기가 될 때 까지 연속된 부분 수열의 합을 구한다. 4. 부분 수열의 합을 구할 때 주어진 수열이 원형 수열이기 때문에 index 가 elements 크기와 같거나 크면 elements 의 .. [알고리즘][KOTLIN] 점찍기 https://school.programmers.co.kr/learn/courses/30/lessons/140107 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1. 두 좌표 간의 거리를 구하는 공식을 이용 한다. X^2 + Y^2 = D^2 2. X, Y 를 k 만큼 증가하여 탐색한다. 3. 이때 이중 For 문으로 탐색을 할 경우 시간 초과가 발생한다. 4. 1번의 거리 식에서 Y^2 = D^2 - X^2 이 된다. 5. 4번에서 나온 Y값 중 k 배수가 될 수 있는 개수를 구한다. 코드 class Solution { fun solutio.. 이전 1 2 3 다음
