React
///
///
✴️

Class Problem Solving

<Class Problem Solving>에서는 저의 https://solved.ac/class 문제 풀이를 가장 빠르게 받아보실 수 있습니다.
Search
Class Problem Solving

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

예제 출력 1

My solution

이 문제는 정답률이 29퍼센트인데 sort 빌트인 메서드가 배열 내의 숫자를 비교할 때 아스키코드로 비교되기 때문에 일의 자리수를 넘어가면 사전순으로 "10"이 "2"보다 더 앞에 위치하게 된다는 사실을 알면 된다.
[2751] 수 정렬하기 2 Sort numbers 2
정렬
Class2
2021/10/14

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

예제 출력 1

My solution

[2609] 최대공약수와 최소공배수 Greatest Common Factor and Least Common Multiple
수학
Class2
2021/10/11

문제

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.

출력

입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.

예제 입력 1

예제 출력 1

My solution

[2292] 벌집 honeycomb
수학
Class2
2021/10/11

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

예제 입력 1

예제 출력 1

My solution

[2231] 분해합 decomposition
브루트포스 알고리즘
Class2
2021/10/11

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.
1.
산술평균 : N개의 수들의 합을 N으로 나눈 값
2.
중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3.
최빈값 : N개의 수들 중 가장 많이 나타나는 값
4.
범위 : N개의 수들 중 최댓값과 최솟값의 차이
N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.
둘째 줄에는 중앙값을 출력한다.
셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.
넷째 줄에는 범위를 출력한다.
통계학 Statistics
구현
정렬
Class2
2021/10/08

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.
이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.
N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입력 1

예제 출력 1

My solution

[2164] 카드2 card2
스택/큐
Class2
2021/10/08

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

예제 출력 1

My solution

소수 구하기 문제에 이어 똑같은 문제인데 소수를 에라토스테네스의 체를 이용해서 2부터 그 수를 제곱근한 수까지만 약수가 존재하는지 확인한 다음 하나라도 존재하면 그 수는 소수가 아닌 것을 확신할 수 있으므로 isPrime() 함수를 이용해 아래와 같이 구현할 수 있다.
소수 찾기 Find decimals
수학
Class2
2021/10/08

문제

여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.
1.
현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2.
나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.
예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.
여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

입력

첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.
테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 이때 맨 왼쪽은 0번째라고 하자. 두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

출력

각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

예제 입력 1

예제 출력 1

프린터 큐 Printer queue
스택/큐
구현
Class2
2021/10/06

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

예제 출력 1

My solution

소수 찾기는 이미 2번 정도 풀어본 흔한 기출문제였다. 기본적으로 알고 있는 방식으로 소수를 판정할 수 있지만 입력이 너무 커지면 시간복잡도가 엄청나게 늘어나게 된다. 그래서 효율성면에서 fail이 나오는 문제들이 있다. 소수 판정에 막혀봤을 때 한참 고민해보다가 에라토스테네스의 체 라는 걸 알게 되었다.
소수 구하기 Find decimals
수학
Class2
2021/10/05

문제

임시

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

스택 수열 Stack sequence
스택/큐
Class2
2021/10/04

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1

예제 출력 1

My solution

이진탐색으로 문제를 푸는데 하나의 값을 찾는 것이 아니라 배열의 원소를 돌아가면서 하나씩 찾아서 0 또는 1을 넣어주어야 했다. while문이 중첩되어 시간복잡도가 O(n^2)가 되었는데 제출해보니 시간초과가 떴다.
수 찾기 Find number
이분탐색
Class2
2021/10/04
랜선 자르기 LAN cable cut
체스판다시칠하기 Repaint the chessboard
영화감독 숌 Movie director shun
펠린드롬수 Pelindrome number

Class3

[1676번] 팩토리얼 0의 개수
[1620번] 나는야 포켓몬 마스터 이다솜
[1541번] 잃어버린 괄호
[1463번] 1로 만들기
[1389번] 케빈 베이컨의 6단계 법칙
[1260번] DFS와 BFS
[1107번] 리모컨 remote
[1074번] Z
[1012번] 유기농 배추 organic cabbage
[1003번] 피보나치 함수 fibonacci function

Class2

[18111번] 마인크래프트 Minecraft
[15829번] Hashing
[11866번] 요세푸스 문제 0 Josephus problem 0
[11651번] 좌표 정렬하기 2 aligning coordinates 2
[11650번] 좌표 정렬하기 aligning coordinates
[11050번] 이항 계수 1 binomial coefficient 1
[10989번] 수 정렬하기 3 sort numbers 3
[10866번] 덱 deque
[10845번] 큐 queue
[10828번] 스택 stack
[10816번] 숫자 카드 2 number card 2
[10814번] 나이순 정렬
[10773번] 제로 zero
[10250번] ACM 호텔 ACM Hotel
[2805번] 나무 자르기 cutting trees
[9012번] 괄호 bracket
[7568번] 덩치 bulk
[4949번] 균형 잡힌 세상 a balanced world
[2869번] 달팽이는 올라가고 싶다
[2839번] 설탕 배달 sugar delivery
[4153번] 직각삼각형
[2798번] 블랙잭 blackjack
[2751] 수 정렬하기 2 Sort numbers 2
[2609] 최대공약수와 최소공배수 Greatest Common Factor and Least Common Multiple
[2292] 벌집 honeycomb
[2231] 분해합 decomposition
[2164] 카드2 card2
[2108] 통계학 Statistics
[1978] 소수 찾기 Find decimals
[1966] 프린터 큐 Printer queue
[1929] 소수 구하기 Find decimals
[1920] 스택 수열 Stack sequence
[1874] 수 찾기 Find number
[1654] 랜선 자르기 LAN cable cut
[1018] 체스판다시칠하기 Repaint the chessboard
[1085] 직사각형에서탈출 Escape from Rectangle
[1436] 영화감독 숌 Movie director shun
[1181] 단어정렬 Word sort
[1259] 펠린드롬수 Pelindrome number
Made with