분류 전체보기
-
[백준/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, ..
-
[백준/BOJ] 1926번 그림 (C++)알고리즘 문제풀이/백준 2021. 1. 9. 02:21
www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net BFS 유형의 문제였습니다. 프로그래머스의 카카오프렌즈 컬러링북 문제와 거의 동일한 문제입니다. 배열을 탐색하면서 탐색이 완료된 곳의 값을 0으로 바꿔줌으로써 따로 방문 배열을 두지 않았습니다. #include #include using namespace std; int n, m; int map[501][501]; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; int..
-
[백준/BOJ] 1158번 요세푸스 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 20:03
www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 문제 분류는 큐를 이용하라고 되어있었지만, 저는 삭제 작업에 유리한 리스트 자료구조를 이용하여 문제를 해결했습니다. 리스트에 1번부터 n번까지 값을 넣고, 리스트가 빌 때까지 k - 1번마다 현재 이터레이터가 가리키는 원소를 벡터에 넣고 그 값을 삭제하는 과정을 반복하면 됩니다. #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n, k; cin >..
-
[백준/BOJ] 5397번 키로거 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 20:01
www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 리스트 자료구조를 이용하는 유형. 백준 1406번 문제를 해결했다면 어렵지 않게 풀 수 있는 문제입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; while(n--) { string s; cin >> s; list li; list::i..
-
[백준/BOJ] 1406번 에디터 (C++)알고리즘 문제풀이/백준 2021. 1. 8. 19:50
www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 리스트 자료구조에 익숙해질 수 있는 문제였습니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); string s; int n; cin >> s >> n; list li; for(int i = 0; i < s.size(); i++) { li.push_back(s[i]); } lis..