본문 바로가기

Programming/Algorithm

(15)

[Kotlin] 백준 1292 - 쉽게 푸는 문제 1. 문제동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.2. 입력첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.3. 풀이 (생각의 흐름)1. 구간의 합 -> 3~7 구간의 합이란, 7까지 누적된 합 - 2까지 누적된 합과 동일하다2. 3~7구간의 ..

[Kotlin] 백준 2693 - N번째 큰 수 문제배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오.배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다.첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000보다 작거나 같은 자연수이다.풀이1. 숫자형 배열의 크기를 비교한다.2. n번째 숫자를 찾아내는것 -> 정렬을 고려한다. -> 기본 1회 정렬로 풀이가 가능하다.3. 내부함수를 이용한 시간복잡도는 O(nlog(n))으로 시간 안으로 풀이가 가능하므로 채택한다.소스import java.util.*fun main() = with(System.`in`..

[Kotlin] 백준 2609 - 최대공약수와 최소공배수(유클리드 호제법) 문제두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.풀이1. 최대공약수를 구한다. 최대공약수는 큰값을 작은값으로 나누었을 때, 나머지가 나오지 않는 첫 시점의 값이다.2. 유클리드 호제법을 알고있냐는 문제이다.코드import java.util.*fun main() = with(Scanner(System.`in`)) { var n1: Int = nextInt() var n2: Int = nextInt() val m: Int // 최대공약수 // 예외처리 n1 > n2로 변환 if(n2 > n1){ val temp ..

[Kotlin] 백준 2309 - 일곱 난쟁이 문제왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.풀이1. 합이 100이 되는 경우를 찾는다.2. 난쟁이의 7명의 키 총합을 구하..

[Kotlin] 백준 10870 - 피보나치 수 5 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.풀이1. n번째 자리의 값은 n-1번째, n-2번째 값의 합이다. -> n-1, n-2번째 값을 기억하고 있어야한다. -> 배열 자료구조를 채택해서 값을 저장..

[Kotlin] 배준 3460 - 이진수 문제양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다.첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. (1 ≤ T ≤ 10, 1 ≤ n ≤ 10^6)풀이1. 2진수의 경우, 2로 나눈 나머지가 존재한다면(나머지는 1) 해당 위치 1의 값이 온다.2. 테스트 케이스 당 n의 값을 2로 계속 나눈다면 최대 log(n)번 수행해야한다. O(TlogN)3. T는 최대 10 n의 최댓값은 10^6으로 이므로 최대 log(10^7)의 시간복잡도를 가지므로 2로 계속 나누는 방법을 채택한다.소스 코드import java.uti..

[Kotlin] 백준 2501 - 약수 구하기 문제어떤 자연수 p와 q가 있을 때, 만일 p를 q로 나누었을 때 나머지가 0이면 q는 p의 약수이다. 6을 예로 들면6 ÷ 1 = 6 … 06 ÷ 2 = 3 … 06 ÷ 3 = 2 … 06 ÷ 4 = 1 … 26 ÷ 5 = 1 … 16 ÷ 6 = 1 … 0그래서 6의 약수는 1, 2, 3, 6, 총 네 개이다.두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.첫째 줄에 N과 K가 빈칸을 사이에 두고 주어진다. N은 1 이상 10,000 이하이다. K는 1 이상 N 이하이다.풀이1. 나머지가 0으로 나누어 떨어지면 약수이다.2. N이 10,000이하이다 -> 무식한 방법인 1부터 N까지 모두 확인해도 1만분의 1초(1억에 1초로 가정)3. 시간복..

[Python] 프로그래머스 - 무인도 여행 파이썬 풀이 import sys sys.setrecursionlimit(10000) def dfs(x, y, maps, visit): val = 0 if x = len(maps[0]): return val if y = len(maps): return val if visit[y][x] is True: return val if maps[y][x] == "X": return val visit[y][x] = True return int(maps[y][x]) + dfs(x - 1 , y, maps, visit) + dfs(x + 1 , y, maps, visit) + dfs(x, y - 1, maps, visit) + dfs(x, y + 1, maps, visit) def solution(..

이전 1 2 다음

728x90

티스토리툴바