알고리즘

(C++) 백준 15656번 - N과 M (7)

문제 링크 : https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 아주 간단한 백트래킹 문제로 N과 M (3) 문제처럼 특별한 조건이 없기에 다른 백트래킹 문제에 익숙하다면 어렵지 않게 풀 수 있는 문제이다. 입력받은 수들을 정렬한 후에 N과 M (3) 문제와 같이 풀이하면 된다. #include #include using namespace std; int n, m; int arr[10]; // ..

(C++) 백준 15655번 - N과 M (6)

문제 링크 : https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용한 풀이이다. 정렬을 한 후에 백트래킹을 하면서 이전에 들어간 수보다 들어갈 수가 더 적다면 그 경우는 건너뛰는 식으로 구현한다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int isUsed[..

(C++) 백준 15654번 - N과 M (5)

문제 풀이 : https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. N과 M (1)과 따로 입력값을 정렬해야 한다는 점만 제외하면 거의 동일한 문제이다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int isUsed[10]; void nNm(i..

(C++) 백준 15652번 - N과 M (4)

문제 링크 : https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 배열에 들어올 수가 이전에 배열에 삽입된 수보다 작지 않도록 조건만 달아주면 쉽게 풀 수 있다. #include using namespace std; int n, m; int arr[10]; void nNm(int idx){ if(idx == m){ // base condition for(int i = 0; i < m; i++){ cout..

(C++) 백준 15651번 - N과 M (3)

문제 링크 : https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 아주 간단한 백트래킹 문제로 특별한 조건이 없기에 다른 백트래킹 문제에 익숙하다면 어렵지 않게 풀 수 있는 문제이다. #include using namespace std; int n, m; int arr[10]; int isUsed[10]; void nNm(int idx){ if(idx == m){ // base condition for(..

(C++) 백준 15650번 - N과 M (2)

문제 링크 : https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹을 사용한 풀이이다. 백트래킹을 하면서 이전에 들어간 수보다 들어갈 수가 더 적다면 그 경우는 건너뛰는 식으로 구현한다. #include using namespace std; int n, m; int arr[10]; int isUsed[10]; void nNm(int idx){ if(idx == m){ // base condition for(int i = 0; i..

(C++) 백준 11652번 - 카드

문제 링크 : https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 문제 풀이 sort 함수로 정렬 후에 각 수마다의 등장 횟수를 직접 세서 가장 많이 등장한 정수를 출력하도록 풀이하였다. 구현이 크게 어렵진 않으나 입력되는 숫자의 크기가 int 범위에서 해결될 수 없기에 long long을 사용해야 한다는 점을 잘 체크해야 한다. #include #include #define ll long long using namespace std; ll ..

(C++) 백준 1431번 - 시리얼 번호

문제 링크 : https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 문제 풀이 sort 함수를 사용하고, 커스텀 비교 함수를 만들어 이를 활용함으로써 풀이를 진행하였다. #include #include using namespace std; string arr[51]; int n; string tmp; bool cmp(string &s1, string &s2){ // 커스텀 비교 함수 if(s1.size() != s2.size()) return ..

(C++) 백준 15688번 - 수 정렬하기 5

문제 링크 : https://www.acmicpc.net/problem/15688 15688번: 수 정렬하기 5 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이며, 같은 수가 여러 번 중복될 수도 있다. www.acmicpc.net 문제 풀이 계수 정렬(Counting Sort)을 이용한 풀이이다. 등장 횟수를 배열에 저장하고, 등장 횟수만큼 해당 숫자를 출력하는 형식으로 풀이했다. #include using namespace std; int a[2000002]; // 해당 숫자(-1000000~1000000)이 몇 번 나타나는지 저장하는 배열 int n, tmp; int mai..

(C++) 백준 11728번 - 배열 합치기

문제 링크 : https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 풀이 Merge Sort를 활용하여 풀이하였다. 이미 병합할 배열들이 정렬되어 있기에 두 배열의 최솟값을 비교하여 더 작은 최솟값을 출력하는 방식으로 풀이하였다. #include using namespace std; int a[1000001]; int b[1000001]; int n, m, tmp, ida, idb; int main() { i..