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

BOJ107

[Kotlin] 백준 1874 : 스택 수열 문제 링크 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 해설 문제를 이해하기만 하면 스택을 이용하여 손쉽게 풀 수 있다. 예제 입출력의 경우를 예로 들어 보자. 4, 3, 6을 수열에 넣기 위한 동작을 그림으로 표현하면 다음과 같다. 그림에 대해 설명하자면 처음에 수열에 4를 추가해야 하는데 스택에 4가 없기 때문에 1, 2, 3, 4를 차례대로 삽입한다. 이후 스택의 맨 위에 있는 4를 제거하여 수열에 추가한다. 다음.. 2022. 12. 2.
[Kotlin] 백준 2108 : 통계학 문제 링크 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 문제 해설 주어진 입력으로부터 제시된 값들을 구하면 된다. 1, 2, 4는 손쉽게 구할 수 있지만, 최빈값을 구하고 최빈값이 여러개일 때 두 번째로 작은 값을 구하는 부분은 조금 생각을 해봐야 한다. 최빈값을 구하기 위해 수가 나타나는 빈도를 저장할 별도의 배열을 생성한다. 그리고 N개의 수를 입력받으면서 빈도를 저장할 배열에서 입력하는 수 + 4000을 인덱스로 하는 요소값을 1씩 증가시킨다. N개의 수 입력이 끝났다면 빈도수를 저장한 배열의 최대값이 2개 이상인.. 2022. 12. 2.
[Kotlin] 백준 4949 : 균형잡힌 세상 문제 링크 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다 www.acmicpc.net 문제 해설 스택을 이용하여 풀 수 있는 괄호 문제다. 문자열에서 괄호 외의 다른 문자는 모두 무시하고 괄호의 경우만 계산하면 되는데 모든 괄호가 짝을 이루되, 5번의 조건과 같이 괄호 내부에서도 괄호가 짝을 이뤄야 한다. 예를 들어 "[(])"의 경우는 대괄호 안에 소괄호는 왼쪽과 오른쪽이 모두 존재하지만 대괄호 사이에는 왼쪽 소괄호가, 소괄호 사이에는 오른쪽 대괄호가 있어서 짝을 이루지 못하므로 균형잡힌 문자열이 아니다. 스택을.. 2022. 12. 2.
[Kotlin] 백준 2805 : 나무 자르기 문제 링크 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 해설 상근이가 M미터 이상의 나무를 가져가면서 가져가는 나무의 양이 최소가 되는, 즉 절단기의 높이 H의 최대값을 구해야 한다. 단순하게 모든 경우를 하나씩 체크할 수도 있겠지만 나무의 최대 높이가 무려 10억이고 최대 나무의 수도 100만이나 되기 때문에 이렇게 하면 1초에 1억회의 계산을 한다고 해도 최대 1000만초(약 116일)라는 엄청난 시간이 걸린다. 따라서 더 효율적인 방법을 찾아야 한다. 이 .. 2022. 12. 2.
[Kotlin] 백준 1966 : 프린터 큐 문제 링크 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 해설 큐(Queue)를 이용하면 쉽게 풀 수 있다. 우선 문서가 인쇄 대기열에 등록된 순서와 중요도를 묶은 배열을 모두 큐에 삽입한다. 그 후 M번째 문서가 인쇄될 때까지 아래 과정을 반복해서 수행한다.(코드의 14~25번째 줄) 현재 인쇄 대기열의 0번째 문서의 중요도가 가장 높은지 확인한다. 가장 높을 경우 해당 문서를 인쇄하고 원래 순서가 M이면 반복문을 종료한다. 가장 높은 경우가 아니면 해당 문서를 빼서 다시 큐의 맨 뒤에 삽입한다. 이 과.. 2022. 11. 30.
[Kotlin] 백준 9020 : 골드바흐의 추측 문제 링크 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 해설 10,000 이하의 짝수 \(n\)이 주어졌을 때, \(n\)을 차이가 가장 작은 두 소수의 합으로 나타내야 한다. 기본적으로는 4948번 문제와 접근 방법이 비슷하다. 모든 테스트 케이스 중 가장 큰 \(n\) 이하의 모든 소수를 탐색한 후 각 테스트 케이스에 대해 주어진 문제의 계산을 수행하면 된다. 문제에 \(n\)의 골드바흐 파티션을 구하면서 두 소수의 차이가 가장 작은 경우를 출력하라는 조건이 걸려있다. 어떤 짝.. 2022. 11. 29.
[Kotlin] 백준 4948 : 베르트랑 공준 문제 링크 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 해설 어떤 자연수 \(n\)이 주어졌을 때 \(n\) 초과, \(2n\) 이하인 소수의 개수를 구해야하는 문제다. 어떤 수 \(x\) 이하의 모든 소수를 구하는 방법은 에라토스테네스의 체를 이용하는 방법이 있다. 이 문제도 에라토스테네스의 체를 이용하면 손쉽게 해결할 수 있다. 문제의 조건에 따르면 \(n\)의 최대값은 123,456이고, \(2n\) 이하인 소수의 개수를 구해야하므로 최악의 경우에는 246,912 이하인 소수를 구해야 한.. 2022. 11. 29.
[Kotlin] 백준 2839 : 설탕 배달 문제 링크 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 문제 해설 탐욕법으로 풀 수 있는 간단한 수학 문제다. 처음 N kg이 주어지면 먼저 5로 나눈 값을 옮겨야 할 봉지 수에 더하고 나머지를 남겨 놓는다. 여기서 나머지가 0이면 그 값이 즉시 정답이 된다. 나머지가 0이 아니라면 반복문으로 포장하지 않은 설탕(=나머지)의 양이 3으로 나누어 떨어질 때까지 계산을 시작한다. 포장하지 않은 설탕이 3으로 나누어 떨어진다면 나눈 값을 옮겨야 할 봉지 수에 더하고 반복문을 종료한다. 나머지가 3으로 나누어 떨어지지 않는.. 2022. 11. 28.

티스토리툴바