알고리즘 문제풀이/백준
-
[백준/BOJ] 11656번 접미사 배열 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 21:50
www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 정렬 유형의 문제입니다. 문자열을 입력받고 0번부터 문자열 크기의 - 1 까지 인덱스를 시작점으로 문자열을 분리한 값을 string 벡터에 넣어줍니다. 그리고 마지막에 정렬을 해주면 간단하게 풀 수 있는 문제였습니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); string s; vector v; cin >> s; for(int i = 0..
-
[백준/BOJ] 5648번 역원소 정렬 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 21:41
www.acmicpc.net/problem/5648 5648번: 역원소 정렬 모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요. 단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니 www.acmicpc.net 정렬 유형의 문제입니다. n개의 숫자를 string으로 받고 이를 reverse 함수를 이용해 뒤집어줍니다. 그리고 long long 자료형 벡터에 모두 넣어준 후 sort 라이브러리 함수를 이용해서 오름차순 정렬해주었습니다. #include #include #include using namespace std; typedef long long ll; int main(void) { ios_base::sync_with..
-
[백준/BOJ] 11652번 카드 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 21:16
www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 정렬 유형의 문제였습니다. 입력값을 map으로 받고 그 입력값을 key값으로 나오는 빈도수를 value로 저장합니다. 저장이 끝나고, 벡터를 pair형으로 선언하여 map의 key, value를 한 쌍으로 옮겨줍니다. 마지막으로 cmp 함수를 크기와 빈도 수를 기준으로 정렬할 수 있게끔 구현하였습니다. 문제를 풀면서 주의해야할 점은 입력값의 크기가 최대 2^62 이므로 long long 자료형을 이용해야 ..
-
[백준/BOJ] 1431번 시리얼 번호 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 20:44
www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루 www.acmicpc.net 정렬 유형의 문제입니다. 길이, 숫자 자리수의 합, 사전순대로 비교를 하기 위해서 cmp 함수를 따로 만들어줬습니다. 그리고 숫자 자리수의 합을 기준으로 정렬하기 위해서 자리수의 합을 구하기 위한 함수로 getSum 함수를 만들었습니다. #include #include #include using namespace std; int getSum(string str) { int sum = 0; for(int..
-
[백준/BOJ] 11931번 수 정렬하기 4 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 20:13
www.acmicpc.net/problem/11931 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 병합 정렬을 내림차순으로 구현하여 해결했습니다. #include using namespace std; int a[1000001]; int tmp[1000001]; void mergeSort(int lt, int rt) { if(lt < rt) { int mid = (lt + rt) / 2; mergeSort(lt, mid); mergeSort(mid + 1, rt); int p1 = lt, p2..
-
[백준/BOJ] 2751번 수 정렬하기 2 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 18:01
www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 병합 정렬을 이용하여 문제를 해결했습니다. #include using namespace std; int a[1000001]; int tmp[1000001]; void divide(int lt, int rt) { if(lt < rt) { int mid = (lt + rt) / 2; divide(lt, mid); divide(mid + 1, rt); int p1 = lt, p2 = mid + 1, p3..
-
[백준/BOJ] 11728번 배열 합치기 (C++)알고리즘 문제풀이/백준 2021. 1. 10. 17:21
www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 병합 정렬의 근본이 되는 문제였습니다. 해당 문제를 풀고나서 2751번 문제를 풀어보면 좋습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector v1(n), v2(m), answer; ..
-
[백준/BOJ] 2178번 미로 탐색 (C++)알고리즘 문제풀이/백준 2021. 1. 9. 02:33
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS 유형의 문제입니다. 주의해야 할 점은 배열의 입력으로 받는 수가 붙어서 받아야 한다는 점입니다. 따라서 cin을 사용하지 않고 scanf를 이용하여 수를 입력받았습니다. (%1d 이런식으로 하면 수가 붙어서 입력되어도 하나씩 입력 받습니다.) 풀이는 그림 문제와 비슷합니다. #include #include using namespace std; int n, m; int map[101][101]; int dx[4] = {1, 0, -1, ..