전체 글

(C++) 백준 1181번 - 단어 정렬

문제 링크 : https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 풀이 sort 함수와 커스텀 비교 함수를 사용하여 단어를 정렬하여 풀이를 진행하였다. 다만 C++ vector에서의 중복 제거를 처음 사용해 보아서 조금 어려움도 있었다. ※ unique 함수는 중복된 값들을 뒤로 보내고, 중복된 값들의 시작 위치를 반환한다. ※ erase 함수는 시작 위치부터 종료 위치까지의 값을 모두 제거한다. #include #include #..

(C++) 백준 15657번 - N과 M (8)

문제 링크 : https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제 풀이 백트래킹을 사용하여 풀이하였다. 입력받은 수들을 정렬한 후 배열에 들어올 수가 이전에 배열에 삽입된 수보다 작지 않도록 조건만 달아주면 쉽게 풀 수 있다. #include #include using namespace std; int n, m; int arr[10]; // 입력값들을 저장하는 배열 int result[10]; // 출력 순서를 저장할 배열 int i..

(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 ..