본문 바로가기
728x90

알고리즘

 (101)
[백준][2231] 분해 합 https://www.acmicpc.net/problem/2231문제 풀이1. N의 생성자를 구한다는 것은 반대로 분해합이 N 이 되는 수를 구하는 것으로 접근한다.2. 백만개의 자연수에 대해서 분해합을 각각 구하여 N 과 같은 경우의 수 중 최소 값을 찾는다.3. 각 자리수의 합을 구할 때 kotlin string 에서 제공하는 sumOf 를 이용하면 각자리 수의 합을 쉽게 구할 수 있다.코드import java.io.BufferedReaderimport java.io.InputStreamReaderfun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`)) val N = br.readLine().toInt()..
[백준][2798] 블랙잭 https://www.acmicpc.net/problem/2798문제 풀이1. 3중 for 문을 이용하여 카드를 세 장 뽑는다.2. 뽑은 세 장의 카드 합이 M 보다 작거나 같고 현재 result 값보다 크면 result 에 저장한다.3. result 를 출력 한다.코드import java.io.BufferedReaderimport java.io.InputStreamReaderfun main(args: Array) { val br = BufferedReader(InputStreamReader(System.`in`)) val (N, M) = br.readLine().split(" ").map { it.toInt() } val numbers = br.readLine().split(" ").m..
[Algorithm] Brute Force 브루트 포스는 모든 경우의 수를 탐색하면서 요구 조건을 충족하는 결과를 가져오는 알고리즘이다.모든 경우의 수를 100% 탐색하기 때문에 무조건 정답을 얻을 수 있다.브루트 포스 알고리즘은 2가지 종류가 있다.1. 선형 구조 : 순차 탐색2. 비선형 구조 : BFS, DFS, 백트래킹모든 문제를 브루트 포스 알고리즘으로 풀 수 없다. 해당 알고리즘은 설명에서 말한 것과 같이 모든 경우를 탐색하기 때문에시간 복잡도나 메모리를 넘어서는 경우가 발생한다.주어지는 문제가 브루트 포스로 해결이 가능한 지 확인하여 적용 유무를 판단해야 한다. - 브루트 포스 문제 (BOJ)https://www.acmicpc.net/step/22
[백준][2501] 약수 구하기 https://www.acmicpc.net/problem/2501 2501번: 약수 구하기첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.www.acmicpc.net문제 풀이1. 1부터 N 까지 루프를 돌려 (N % index == 0) 인 index 를 result list 에 저장한다.2. result list 의 크기가 K 보다 작으면 조건에 따라 0을 출력 한다.3. result list 의 크기가 K 보다 크거나 같으면 (K - 1)번째의 값을 출력한다.코드import java.io.BufferedReaderimport java.io.InputStreamReaderfun main(args: Array) { val br = ..
[백준][5086] 배수와 약수 https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 문제 4 × 3 = 12이다. 이 식을 통해 다음과 같은 사실을 알 수 있다. 3은 12의 약수이고, 12는 3의 배수이다. 4도 12의 약수이고, 12는 4의 배수이다. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오. 첫 번째 숫자가 두 번째 숫자의 약수이다. 첫 번째 숫자가 두 번째 숫자의 배수이다. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다. 입력 입력은 여러 테스트 케이스로 이루어져..
[백준][KOTLIN][4779] 칸토어 집합 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 문제 풀이 1. result 의 초기 값을 "-" 로 설정 한다. 2. N 크기 만큼 아래의 과정을 반복한다. 3. result 값 + (result 의 크기 만큼 빈칸) + reulst 값 을 채운다. 4. result 를 출력한다. 코드 import java.util.Scanner fun main(args: Array) { val sc = Scanner(System.`in`) while (sc..
[KOTLIN] 모음사전 - https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 문제 설명 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다. 단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇..
[KOTLIN]전력 망을 둘로 나누기 - https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 문제 설명 n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를 2개로 분할하려고 합니다. 이때, 두 전력망이 갖게 되는 송전탑의 개수를 최대한 비슷하게 맞추고자 합니다. 송전탑의 개수 n, 그리고 전선 정보 wires가 매개변수로 주어집니다. 전선들 중 하나를 끊어서 송전탑 개수가 가..

티스토리툴바