초보 개발자의 이야기, 릿허브

1. 문제이해 https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 다음과 같은 규칙을 따르되, N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 구현하는 것이 목표이다. 1. 2부터 N까지 모든 정수를 적는다. 2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. 3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. 2. 문제풀이 2부터 N까지의 자연수를 입력받고, K번째 지워지는 숫자를 찾는 문제..

1. 문제이해 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1. 산술평균 : N개의 수들의 합을 N으로 나눈 값 2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값 4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N개의 수가 주어졌을 때, 위와 같은 네 가지 기본 통계값을 구하는 것이 목표이다. 단, 산술평균은 소수점 이하 첫째 자리에서 반올림한 값을 출력하며, ..

1. 문제이해 https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net 상근이는 길을 걷다가, 신기한 기계를 발견했다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었고, 버튼을 누르면, 화면의 모든 B는 BA로 바뀌고, A는 B로 바뀐다는 사실을 알게되었다. 버튼을 K번 눌렀을 때, 화면에 A와 B의 개수를 구하는 것이 목표이다. 2. 문제풀이 A와 B의 갯수를 찬찬히 살펴보면 바로 규칙을 찾을 수 있는 간단한 DP문제이다. 아래 표를 살펴보자. 버튼..

1. 문제이해 https://www.acmicpc.net/problem/1235 1235번: 학생 번호 첫째 줄에는 학생의 수 N(2≤N≤1,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 학생의 학생 번호가 순서대로 주어진다. 모든 학생들의 학생 번호는 서로 다르지만 그 길이는 모두 같으며, 0부 www.acmicpc.net 학생의 수(N)와 각 학생들의 번호가 주어진다. 번호를 뒤에서 k자리만 남겨놓았을 때, 모든 번호를 다르게 만들 수 있는 k의 최솟값을 구하는 것이 목표이다. 2. 문제풀이 입력받은 학생 번호를 뒤에서 k만큼 남겨놓을 때, 모든 번호를 다르게 만드는 최솟값을 구하는 문제이다. 아래 예제 입력 1을 통해 풀이 방법을 자세히 알아보자. N = 3 1212345 1212356 0..

1. 문제이해 https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 1을 한번, 2를 두번, 3을 세번, 이런식으로 1 2 2 3 3 3 4 4 4 4 ... 이루어진 순열이 있다. 어느 일정한 구간이 주어졌을 때, 그 구간의 합을 구하는 것이 목표이다. 2. 문제풀이 1 2 2 3 3 3 4 4 4 4 5 5 5 5 5 ... 위와 같이 자연수 n 이 n 번 나타나는 형태의 수열에서, 주어진 구간의 합을 구하는 문제이다. 주어진 범위가 비교적 크지 않기 때문에, (1 ≤..

1. 문제이해 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 1번부터 N번까지의 사람이 원을 이루며 앉아있다. 정수 K가 주어질 때, 순서대로 K번째 사람을 제거하며, 남은 사람들로 해당 과정을 반복해나간다. N명의 사람이 모두 제거될 때까지 해당 과정을 반복할 때, 제거되는 순서를 요세푸스 순열이라고 한다. N과 K가 주어질 때, 요세푸스 순열을 구하는 것이 목표이다. 2. 문제풀이 이전에 풀이한 백준 1158번 요세푸스 문제와 완전히 동일한 문제이다. (백준에 동일한 문제가 이름만 살짝 틀리게 올라오다니..🤔) 풀이방법 또..

1. 문제이해 https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 다솜이는 자기 방 번호를 플라스틱 숫자로 붙이려고 한다. 플라스틱 숫자는 0 ~9 한 세트로 판매하며, 6, 9는 서로 뒤집어서 사용가능하다. 다솜이의 방 번호가 주어질 때, 필요한 세트의 개수를 출력하는 것이 목표이다. 2. 문제풀이 다솜이의 방 번호가 주어질 때, 필요한 숫자 세트의 개수를 출력하는 문제이다. 단, 숫자세트에는 0 ~ 9 까지의 숫자가 들어있으며, 6과 9는 서로 뒤집어서 사용가능하다. 6과 9가 서로 호환가능하다는 점에 유의해야한다. 아래 예제를 통해 풀이방법..

1. 문제이해 https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 단어를 입력받아, 해당 단어가 올바른 단어이면 1, 아니면 0 을 출력하는 것이 목표이다. 해당 단어가 늑대나라에서 사용하는 올바른 단어인지 확인하는 규칙은 다음과 같다. 1. 임의의 양의 정수 n에 대해서, 'w'가 n번 나오고, 그 다음에 'o'가 n번, 그 다음에 'l'이 n번, 그 다음에 'f'가 n번 나온 단어는 올바른 단어이다. 2. 올바른 단어 2개를 이은 단어도 올바른 단어이다. 3. 1, 2번 조건으로 만들 수 있는 단어만 올바른 단어이다. ..

1. 문제이해 https://www.acmicpc.net/problem/2884 2884번: 알람 시계 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, www.acmicpc.net 상근이가 설정한 알람시간(H시 M분)이 주어질 떄, 창영이의 방법을 적용했을 때 설정해야 하는 알람 시간을 출력하는 것이 목표이다. 2. 문제풀이 창영이의 방법을 사용하게 되면, 상근이가 설정한 시간보다 45분 일찍 알람을 설정해야 한다. 예를 들어, 상근이가 설정한 시간이 11시 40분일 경우, 창영이의 방법을 적용하면, 10시 55분에 알람을 설정해야 한다는 뜻이다. 주어진 단위가 시간인..

1. 문제이해 https://www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net A와 B를 입력받아, A / B를 출력하는 것이 목표이다. 단, 실제 정답과 출력값의 절대오차 또는 상대오차가 10^-9 이하여야 한다. 2. 문제풀이 A 나누기 B를 출력하면 되는 간단한 문제이다. 단, 이 문제에는 조건이 하나 있는데, 실제 정답과 출력값의 절대오차 또는 상대오차가 10^-9 이하여야 한다는 점이다. 해당 조건을 만족시키는 값을 출력하기 위해 필자는 precision 을 사용했다. precision은 몇 자리의 숫자를 나타낼 것인지를 지정해주는 함수로, 인자로는 n을 받는다. 예를 ..