지속 가능한 꾸준함

www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net N개의 자연수와 자연수 M이 주어졌을 때, 길이가 M인 순열을 구하는 문제입니다. 여기서, N개의 자연수는 모두 다른 수입니다. 이전 N과 M (1, ..., 4) 문제는 N개의 자연수가 {1, ..., N}로 주어졌다면, 해당 문제는 임의의 자연수를 입력받고 그에 대한 순열을 구해야합니다. 이점을 유의하여 문제를 풀면 됩니다. 코드 #include #include using namespace std;..

www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 주어진 N개의 숫자들로 M개의 숫자를 중복을 허용하여 뽑아 만들 수 있는 수를 오름차순으로 출력하는 문제로 조합 문제입니다. 한 자리의 수를 뽑고 그다음 자리의 수를 뽑을때, 보다 같거나 큰 수를 뽑아야 하는 점을 생각해내는 것이 풀이의 핵심이라 생각됩니다. 코드 #include using namespace std; int N; int M; int numbers[9] = {1,}; void combinatio..

www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개의 원소 중에서 M개의 원소를 중복을 허용하여 사전 순으로 뽑는 경우를 탐색하는 문제입니다. 개인적으로 N과 M (1) 과 N과 M (2) 문제가 더 어려웠던 것 같습니다. 코드 #include using namespace std; int N; int M; int numbers[9] = {0,}; void permutation(int len) { if(len == M + 1) { for(int i = 1; i

www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 주어진 N개의 숫자들로 M개의 숫자를 뽑아 만들 수 있는 수를 오름차순으로 출력하는 문제로 조합 문제입니다. 한 자리의 수를 뽑고 그다음 자리의 수를 뽑을때, 보다 큰 수를 뽑아야 하는 점을 생각해내는 것이 풀이의 핵심이라 생각됩니다. 코드 #include using namespace std; int N; int M; int numbers[9] = {0,}; void combination(int len) { ..

www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 간단한 순열 문제입니다. 단, 작은 수 부터 출력해야 하며 중복을 허용하지 않고 선택해야 한다는 점을 고려해야합니다. 코드 #include using namespace std; int N; int M; int numbers[9]; bool picked[9]; void permutation(int cnt) //cnt: 몇 번째 자릿수인지를 의미함(맨 앞 자릿수 부터 셈) { if(cnt == M + 1) { f..

www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 그래프, 조합, DFS에 대한 개념이 필요한 문제였습니다. 알고리즘 문제를 풀다보면 어떤 문제들은 풀고나면 많은 배움을 얻었다고 느껴지는 문제들이 있습니다. 해당 문제가 이러한 문제였습니다. 결국 스스로의 힘으로 문제를 풀지는 못하고 솔루션을 보고서야 이해하고 풀 수 있었습니다. 특히, 조합을 생성하는데 있어 막힘이 있었습니다. N과 M 문제들을 다시 한 번 쭈욱 풀어봐야겠습니다. 알고리즘을 간략하게 나타내면 다음과 같습니다. 1...

www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 문제를 풀다가 다른 분의 솔루션을 참고하여 풀었습니다. 참고한 솔루션의 C++ Reference 사용법이나, algorithm 라이브러리의 사용법을 보았을때 많은 것을 배울 수 있었습니다. 해당 링크를 공유해드립니다. 11001.tistory.com/28#recentComments [백준 17837: 새로운 게임 2] (C++) 삼성 SW역량 테스트 https://www.acmicpc.net/workboo..

www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 �� www.acmicpc.net 해당 문제는 위상 정렬 알고리즘을 이용하여 풀 수 있습니다. 풀이는 다음과 같습니다. 1. 수행 가능한 순대로 작업을 수행한다. 이때, 동시에 수행가능한 작업은 동시에 수행한다. 2. 각 작업을 수행하였을때 걸린 최대 시간을 기록한다. 3. 각 작업을 수행하였을때 걸린 최대 시간 중 최대 시간을 출력한다. 모든 작업을 완수하는데 걸린 최소 시간을 구해야 하는데 풀이에선 최대 시간을 구하는 느낌이 ..

www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 본 문제는 정렬에 관한 문제입니다. 무분별한 C++ STL 사용으로 몇몇 정렬 알고리즘의 구현 방법을 잊은터라 정렬 알고리즘을 복습할겸 알고리즘 문제도 풀겸 일석이조의 효과를 누리고자 해당 문제를 풀었습니다. 코드를 제출하기전에 직감적으로 \(O(N^{2})\)의 복잡도를 갖는 정렬 알고리즘(Selection Sort, Insertion Sort, Bubble Sort)으로는 문제를 통과할 수 없음..

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 본 문제의 제목은 LCS(Longest Common Subsequence)입니다. 이름만 봐도 유명한 문제라는 느낌이 들어 서칭을 바로 해보았습니다. 역시나 유명한 문제였습니다. LCS는 Longest Common Substring과 Longest Common Subsequence이 존재합니다. 2개는 다른 의미를 가지므로 구분해야합니다. 차이점은 공통되는 부분의 연..