본문 바로가기
  • 개발하는 곰돌이

Algorithm118

[Kotlin/Java] 소수 찾기와 에라토스테네스의 체 소수를 판별하는 기본적인 방법 소수(prime number, 素數)는 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 자연수를 의미한다. 예를 들면 2, 3, 5, 7 ... 등이 있다. 어떤 수 \(x\)가 주어졌을 때 \(x\)가 소수인지 판별하는 가장 간단한 방법은 2부터 \(x-1\)까지 모든 수로 \(x\)를 나누었을 때 나누어 떨어지는 수가 있는지 확인하는 것이다. // Kotlin fun isPrime(x: Int): Boolean { for (i in 2 until x) {// 2부터 x-1까지 반복 if (x % i == 0) return false// x가 한 번이라도 나누어 떨어지면 소수가 아님 } return true// 모두 반복해도 나누어 떨어지지 않으면 소수 } // Java .. 2022. 11. 29.
[Kotlin] 백준 2839 : 설탕 배달 문제 링크 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 해설 탐욕법으로 풀 수 있는 간단한 수학 문제다. 처음 N kg이 주어지면 먼저 5로 나눈 값을 옮겨야 할 봉지 수에 더하고 나머지를 남겨 놓는다. 여기서 나머지가 0이면 그 값이 즉시 정답이 된다. 나머지가 0이 아니라면 반복문으로 포장하지 않은 설탕(=나머지)의 양이 3으로 나누어 떨어질 때까지 계산을 시작한다. 포장하지 않은 설탕이 3으로 나누어 떨어진다면 나눈 값을 옮겨야 할 봉지 수에 더하고 반복문을 종료한다. 나머지가 3으로 나누어 떨어지지 않는.. 2022. 11. 28.
[Kotlin] 백준 11292 : 키 큰 사람 문제 링크 11292번: 키 큰 사람 민우는 학창시절 승부욕이 강해서 달리기를 할 때에도 누가 가장 빠른지를 중요하게 생각하고, 시험을 볼 때에도 누가 가장 성적이 높은지를 중요하게 생각한다. 이번에 반에서 키를 측정하였 www.acmicpc.net 문제 해설 가장 키가 큰 사람들의 이름을 입력된 순서대로 출력하기만 하면 되는 문제다. 알고리즘 분류 상으로는 정렬으로 분류되어 있지만 정렬을 할 필요는 없다. 학생의 이름과 키가 입력될 때마다 리스트에 해당 학생을 저장함과 동시에 현재 가장 큰 키와 비교하여 키의 최대값을 갱신한다. 모든 학생을 입력 받았으면 리스트에서 키의 최대값과 일치하는 키를 가진 학생들을 차례대로 출력하면 된다. Kotlin에서는 컬렉션 객체에 filter 함수를 사용하여 해당 조건.. 2022. 11. 28.
[Kotlin] 백준 1920 : 수 찾기 문제 링크 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 해설 수열이 주어지고 이후 입력되는 숫자들을 주어진 수열에서 찾을 수 있는지를 검사하는 문제다. 일단 이 문제는 첫 입력으로 수열을 받은 후 단순히 in 키워드로 탐색을 하면 \(n\)과 \(m\)이 각각 최대 10만이므로 최악의 경우에 \(100,000\times 100,000=10,000,000,000\)번의 경우를 탐색하게 되어 시간초과가 발생한다. 따라서, 좀 더 효율적인 탐색 방법을 찾아야.. 2022. 11. 26.
[Kotlin] 백준 1065 : 한수 문제 링크 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 문제 해설 1부터 1000까지의 모든 경우를 계산해야하는 완전탐색 문제다. n이 주어졌을 때 n 이하의 수 중 각 자리수가 등차수열을 이루는 수의 총 개수를 구해야한다. 우선 생각해야하는 점은 수열의 항이 2개 이하인 모든 수열은 등차수열이 된다는 점이다. 항이 1개뿐인 경우는 공차가 몇이든 상관 없이 등차수열이 되고, 항이 2개인 경우는 두번째 항 - 첫번째 항의 값이 공차인 등차수열이 되기 때문이다. 예를 들어, X가 31이라면 각 자리를 항으로 하는.. 2022. 11. 25.
[Kotlin] 백준 4673 : 셀프 넘버 문제 링크 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 문제 해설 완전탐색법으로 풀어야 하는 문제다. 먼저 1~10000까지의 수가 셀프 넘버인지 검사할 배열을 선언한다. 이후 1부터 10000까지 모든 수에 대해 d(n)을 구하고, d(n)이 10,000 이하일 경우 배열의 d(n)번째 값을 true로 변경한다.(true는 d(n)의 생성자 n이 존재하는 경우를 뜻한다.) 이후 배열에서 값이 false인 인덱스를 모두 출력하면 된다. Code fun ma.. 2022. 11. 25.
[Java] 프로그래머스 : 더 맵게 문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 힙 트리(heap tree)를 사용하는 문제다. 입출력 예의 설명에 따르면 모든 음식의 스코빌 지수가 K이상이 되지 않았을 때는 문제의 조건에 따라 만들어진 새로운 음식도 섞이는 대상이 될 수 있다. 스코빌 지수가 가장 낮은 두 수를 지속적으로 뽑아내고 새로운 음식을 집어넣으면서 정렬을 해야하는데, 일반적인 배열이나 리스트를 사용하면 음식을 섞을 때마다 매번 정렬을 하게 되면 시간복잡도 상으로 굉장한 손해를 보게 된다. 따라서, 힙 트리를 사용하는 것이 바람직하다. 힙 트리 방식으로 동작하는 대표적.. 2022. 11. 24.
[Kotlin] 백준 1064 : 평행사변형 문제 링크 1064번: 평행사변형 평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC) 이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나 www.acmicpc.net 문제 해설 점 3개가 주어졌을 때 만들어지는 평행사변형 중 가장 긴 둘레와 가장 짧은 둘레 길이의 차이를 구하는 문제다. 점 3개가 주어지면 위 그림과 같이 3개의 변이 만들어지는데, 평행사변형은 마주 보는 변의 길이가 같으므로 두 변의 길이의 합에 2를 곱한 값이 둘레의 길이가 된다. 가장 큰 평행사변형의 둘레와 가장 작은 평행사변형의 둘레의 차이만 구하면 되기 때문에 3개의 변 중에 가장 긴 변의 길이에서 가장 짧은.. 2022. 11. 24.

티스토리툴바