뜌릅

삽입정렬이란 삽입정렬은 2번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘입니다. 최선의 경우: 이미 정렬이 완료되어있는 배열, 이 경우에는 삽입할 위치를 지정할 필요없이 O(N)으로 끝이 납니다. Worst Case: 내림차순으로 정렬이 된 배열, 이 경우에는 삽입할 위치를 찾기 위해 탐색하기 때문에, 시간복잡도는 O(N^2)입니다. 예제 8,5,6,2,4를 오름차순으로 정렬해 봅시다. 코드 예시 void insertion_sort(vector &arr) { int n = arr.size(); int i = 0, j = 0; for (i = 1; i < n; i++) { int key = arr[i]; // ..

Bubble Sort 가장 간단한 정렬 알고리즘 거품 정렬 즉 Bubble Sort는 가장 기초적인 정렬 알고리즘이다. 서로 인접한 2가지 원소를 비교하고, 조건에 맞지 않다면 자리를 교환하는 알고리즘 입니다. 2중 포문으로 구성되어 있으며, 첫번째 포문의 1번째때, 첫번재와 두번째원소를 비교하고, 두번째와 세번째 원소를 비교하고 마지막-1번째와 마지막번째를 비교하는 식으로 구성됩니다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됩니다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어납니다. void bubbleSort(int[] arr) { in..

https://www.acmicpc.net/problem/2548 2548번: 대표 자연수 첫째 줄에는 자연수의 개수 N이 입력된다. N은 1 이상 20,000 이하이다. 둘째 줄에는 N개의 자연수가 빈칸을 사이에 두고 입력되며, 이 수들은 모두 1 이상 10,000 이하이다. www.acmicpc.net 매우 간단한 문제이다. 코드포스 a번으로 나올 거 같다. #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void solve() { int n; cin>>n; vector v(n); for(auto &x: v)cin>>x; sort(v.begi..

https://www.acmicpc.net/problem/14929 그냥 풀게 되면 시간 초과가 나게 된다. 따라서 밑과 같이 tmp 변수를 만들어서 풀게 되었다. void solve() { int n; cin>>n; vector v(n); for(auto & x: v)cin>>x; long long sum =0; long long tmp = 0; for(int i =0; i

https://www.acmicpc.net/problem/18323 18323번: Photoshoot Farmer John is lining up his $N$ cows ($2\le N\le 10^3$), numbered $1\ldots N$, for a photoshoot. FJ initially planned for the $i$-th cow from the left to be the cow numbered $a_i,$ and wrote down the permutation $a_1,a_2,\ldots,a_N$ on a sheet of paper. U www.acmicpc.net #include using namespace std; #define fast_io ios_base::sync_with_st..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net bfs을 활용하여 푸는 문제입니다. #include #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(ll i=0;i= n || _y >= n)continue; if (visited[_x][_y..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 백트레킹을 사용하여 풀 수 있는 문제입니다. 다만 ㅗ ㅓ ㅏ ㅜ 모양의 조각들은 백트레킹으로는 풀 수 없으므로 따로 함수를 만들어서 풀었습니다. #include #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j..

https://www.acmicpc.net/problem/16991 16991번: 외판원 순회 3 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 도시의 좌표 x, y가 주어진다. 모든 좌표는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 두 도시의 위치가 같은 경우 www.acmicpc.net 이미 외판원 순회를 풀어 보았지만, 시간이 오래 지나서 복습을 할겸 외판원 순회3을 풀어보았다. 한번 풀어본 문제였음에도 고생을 많이 하였다. 이 문제는 dp문제로 dp문제답게 어느부분이 겹치는지를 확인해야 한다.(시작점은 어디로 두든지 상관이 없다.) 겹치는 부분을 저장하기 위해 vector [n][2의 16승]을 활용하였다. 해당 dp는 시작 point와 ..

dfs을 활용하여 간단하게 풀 수 있는 문제이다. 이미 접근한 좌표는 다시 접근하지 못하게 visited배열을 활용한다. #include #include using namespace std; #define endl '\n' #define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define rep(i, j) for(ll i=0;i= n || c = n)continue; if (type == 0) { if (!visited[r][c] && board[x][y] == board[r][c]) { visited[r][c] = true; dfs(r, c, type); } } else if (type == 1) { if (!vi..

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS을 활용하여 풀수있는 간단한 문제입니다. visited배열을 사용해서 한번 접근한 숫자에는 다시 접근하지 못하도록 하여 메모리 초과를 방지해야 합니다. 지역변수의 초기값은 쓰레기값으로 초기화 된다는 것을 깜빡하고 있어서 푸는데에 오래 걸렸습니다. #include #include using namespace std; #define endl '\n' #define fast_io io..