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

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. 문제이해 1359번: 복권 (acmicpc.net) 1359번: 복권 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 다음과 같은 룰의 복권이 있을 때, 지민이가 복권에 당첨될 확률을 구하는 것이 목표이다. “1부터 N까지의 수 중에 서로 다른 M개의 수를 골라보세요. 저희도 1부터 N까지의 수 중에 서로 다른 M개의 수를 고를건데, 적어도 K개의 수가 같으면 당첨입니다!” 2. 문제풀이 지민이가 1부터 N까지의 수 중에 서로 다른 M개의 수를 골랐을 때, 복권과 적어도 K개의 수가 같으면 당첨이다. 조합, 확률 관련 문제로 고등학교 문제 푸는 것과 비슷한 느낌을 받았다.풀이 방법은 아래 그림과 같다. 문제의 예제 입력 4에 대한 풀이 예시이다.위 풀이방법을 일반화해보면 ..

1. 문제이해 https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 위의 그림과 같이 육각형 모양의 벌집이 있다. 중앙의 방 1부터 시작해서, 돌아가면서 1씩 증가하는 번호를 주소로 매길 때, 입력으로 주어진 방까지 최소 몇 개의 방을 지나야 하는지 출력하는 것이 목표이다. 2. 문제풀이 위와 같은 벌집 모양의 방들에서, 1번에서 N번째 방까지 몇 개의 방을 지나야 하는지 구하는 문제이다. 아래 그림을 자세히 보자. 위 그림에서 볼 수 있듯, 문제의 벌집 모..

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/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net M 이상 N 이하의 자연수 중 소수인 것을 찾아 해당 값들의 합과 값들 중 최솟값을 출력하는 것이 목표이다. 2. 문제풀이 M 이상 N 이하의 소수를 모두 찾아 해당 값들의 합과 최솟값을 출력하는 문제이다. 이전에도 비슷한 문제를 풀이한 적이 있어서, 해당 방법과 비슷한 방법으로 풀이했다. 제곱근 값(루트값)을 기준으로, 앞의 있는 수들과 뒤에 있는 수들은 서로 짝을 이루므로, 제곱근 값을 기..

1. 문제이해 https://www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net L보다 크거나 같고, R보다 작거나 같은 자연수들 중 8의 개수가 가장 적은 숫자의 8의 개수를 출력하는 것이 목표이다. 2. 문제풀이 L보다 크거나 같고, R보다 작거나 같은 자연수들 중 8의 개수가 가장 적은 숫자의 8의 개수(min)를 구하는 문제이다. 아래 예제풀이를 통해 자세히 알아보자. 1. 두 수의 자릿수가 틀린 경우 : 무조건 두 수의 중간에 10, 100, 1000 ... 과 같은 숫자가 포함되므..

1. 문제이해 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 주어진 식에 괄호를 적절히 사용하여 식의 값의 최소값을 구하는 것이 목표이다. 단, 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 또한, 연속해서 두 개 이상의 연산자는 나타나지 않는다. 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/2588 2588번: 곱셈 첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다. www.acmicpc.net 위와 같은 방식으로 세 자리 자연수의 곱을 구할 때, (3), (4), (5), (6) 의 위치에 들어갈 값을 구하는 것이 목표이다. 2. 문제풀이 상당히 쉬운 난이도의 문제이다. 사실 단계별로 풀어보기 포스팅도 하고 있는데, 어느정도 문제풀이가 필요할 것 같아서 쓰는건 비밀 (3), (4), (5), (6) 의 위치에 들어갈 값을 구하는 것이 목표인데, (3)의 경우 (2)의 일의자리 숫자와 (1)의 곱 (4)의 경우 (2)의 십의자리 숫자와 (1)의 곱 (5)의 경우 (2)의 백의자리..