반응형 정렬5 [알고리즘c++] 삽입 정렬(Insertion Sort) 삽입 정렬 요약 카드를 정렬하는 방법과 유사하다 새로운 카드를 기존의 정렬된 카드 사이 올바른 자리를 찾아서 삽입하는 방식이다. 새로 삽입될 카드의 수 만큼 반복하여 정렬 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하며, 자신의 위치를 찾아서 삽입하여 정렬을 완성하는 알고리즘 매 순서 마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다. 삽입 정렬 알고리즘 두 번째 자료부터 시작하여 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 삽입 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기.. 2022. 11. 21. C++ 백준 11931 수 정렬하기 4 https://www.acmicpc.net/problem/11931 11931번: 수 정렬하기 4 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 N개의 수가 주어졌을 때, 이를 내림차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 내림차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 해당 문제.. 2022. 7. 25. 카운팅 정렬(Counting Sort) 카운팅 정렬이란? 카운팅정렬은 값을 비교해서 정렬하는 방식이라기 보다는 값의 갯수를 세고 그 갯수에 따라서 위치를 성정하는 방식이다. 동작 원리는 다음과 같다. 3,2,2,3,1 와 같은 Array(배열)가 있을때 3 2 2 3 1 1. 각 데이터의 갯수를 모두 카운트 해준다. - 위의 경우 Count[3] = 2; Count[2] = 2; Count[1] = 1가 된다. 2. 누적합을 계산하는 방식으로 1부터 최대값까지 누적 합하여 계산을 해준다. - 예를 들면 Count[1] = Count[1] + Count[0] = 1 Count[2] = Count[2] + Count[1] = 2 + 1 = 3 Count[3] = Count[3] + Count[2] = 2 + 3 = 5 따라서 Count[1] = .. 2022. 7. 8. 백준 10989 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 구현 언어 : c++ 입력: 출력: 카운팅 정렬을 활용해서 정렬이 잘 된것을 확인 할 수 있다. 2022. 7. 8. 백준 1181 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 2022. 5. 24. 이전 1 다음 반응형
