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

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/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 1 ~ N 까지의 숫자가 적힌 N장의 카드가 주어질 때, 다음과 같은 규칙을 적용 후, 마지막에 남는 카드에 적힌 숫자를 출력하는 것이 목표이다. 1. 제일 위에 있는 카드를 바닥에 버린다. 2. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 3. 다음과 같은 동작을 카드가 한 장 남을 때까지 반복한다. 2. 문제풀이 전형적인 큐(queue) 문제이다. 큐..

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 이하의 소수를 모두 찾아 해당 값들의 합과 최솟값을 출력하는 문제이다. 이전에도 비슷한 문제를 풀이한 적이 있어서, 해당 방법과 비슷한 방법으로 풀이했다. 제곱근 값(루트값)을 기준으로, 앞의 있는 수들과 뒤에 있는 수들은 서로 짝을 이루므로, 제곱근 값을 기..