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

1. 문제이해 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 0과 1로만 이루어져있으면서, 아래 조건을 만족하는 수를 이친수라고 한다. N이 주어질 때, N자리 이친수의 개수를 구하는 것이 목표이다. 1. 이친수는 0으로 시작하지 않는다. 2. 이친수에서는 1이 연속으로 2번 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 2. 문제풀이 다이나믹 프로그래밍 문제이다. 처음 문제를 봤을 때 든 생각은, 1과 0 을 적절히 ..

1. 문제이해 https://www.acmicpc.net/problem/2548 2548번: 대표 자연수 첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다. www.acmicpc.net 모든 자연수들에 대해 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수를 대표 자연수라고 한다. N개의 자연수가 주어질 때, 그 중 대표 자연수를 출력하는 것이 목표이다. (단, 대표 자연수가 2개 이상일 경우, 가장 작은 숫자를 대표 자연수로 출력한다.) 2. 문제풀이 문제의 의도만 잘 파악하면 어렵지 않은 문제이다. N개의 자연수 중 전체 차이의 합을 최소로 하는 값을 찾는 ..

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/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 1번부터 N번까지의 사람이 원을 이루며 앉아있다. 정수 K가 주어질 때, 순서대로 K번째 사람을 제거하며, 남은 사람들로 해당 과정을 반복해나간다. N명의 사람이 모두 제거될 때까지 해당 과정을 반복할 때, 제거되는 순서를 요세푸스 순열이라고 한다. N과 K가 주어질 때, 요세푸스 순열을 구하는 것이 목표이다. 2. 문제풀이 N명의 사람들을 K번째 사람씩 제거해나갈 때, 제거되는 순서를 구하는 것이 목표이다. 예제 입력 1에 대한 아래 풀이를 보자. 위와 같이 K - 1번째..

1. 문제이해 https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 2차원 평면위의 좌표들을 y좌표가 증가하는 순으로, y좌표가 같다면 x좌표가 증가하는 순으로 정렬하는 프로그램을 구현하는 것이 목표이다. 2. 문제풀이 2차원 평면 좌표를 y좌표 순으로 정렬하되, y좌표가 같다면 x좌표 순으로 정렬하는 것이 목표이다. 이전에 풀이한 11650번 좌표 정렬하기와 흡사한 문제이다. 해당 문제에서는..

1. 문제이해 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net n개의 정수로 이루어진 수열이 주어진다. 이 중 연속된 몇 개의 숫자를 선택해 구할 수 있는 합 중 최댓값을 출력하는 것이 목표이다. 2. 문제이해 저는 시간초과가 너무 싫어요...^^ 문제풀이를 보시는 분들이라면 아마 아시겠지만, 역시나 모든 경우의 수를 따져 합을 비교하고 구하면 시간초과가 발생한다. 필자는 첫 번째로 이중 for문을 통해 모든 경우의 합을 구하고 비교했으나, 시간초과가 발..

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/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 아기 석환이는 n장의 카드를 가지고 카드 합체 놀이를 하려고 한다. 카드 합체 놀이의 과정은 아래와 같다. 1. x번 카드와 y번 카드를 골라 그 두장에 쓰여진 수를 더한 값을 계산한다. 2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어쓴다. 카드합체를 총 m번 할 때, n장의 카드에 적혀있는 수를 모두 더한 값이 점수가 된다. 이때,..

1. 문제이해 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 배열의 원소의 개수(N)와 원소값이 주어진다. 이때, 배열의 배치 순서를 적절히 바꾸어 다음과 같은 연산을 수행했을 때 얻을 수 있는 최댓값을 구하는 것이 목표이다. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 2. 문제풀이 문제를 똑바로 읽자.. 차이를 최대로 라는 문제 제목과 점화식을 잘못 보고 한참 헤맸다. 문제의 점화식을 잘 봐야 한다..