Algorithm (105) 썸네일형 리스트형 Quick Sort 퀵 정렬 (C++) Quick Sort 퀵 정렬 (C++) Counting Sort란? 기준 데이터(Pivot)을 설정하고 그 기준 보다 큰 데이터와 작은 데이터의 위치를 바꾸어가며 정렬하는 알고리즘 분할 정복 기법을 활용한다 불안정 정렬 순서 1. 피봇의 위치를 설정한다. 2. 분할 : 피봇을 토대로 데이터를 정렬해나간다. 정렬이 끝나면 피봇의 앞은 피봇보다 작은 값들이, 피봇의 뒤는 피봇보다 큰 값들이 오게된다. 3. 2의 과정으로 쪼개진 영역에 대해 재귀적으로 다시 정렬을 수행한다. 이를 애니메이션으로 나타내면 다음과 같다. 시간복잡도 평균 시간 복잡도 : O(NlogN) 이미 정렬이 되어있는 상태일 때 최악의 경우가 되며, 이 때의 시간 복잡도는 O(N^2) Code #include using namespace st.. Counting Sort 계수 정렬 (C++) Counting Sort 계수 정렬 Counting Sort란? 정렬하는 숫자가 특정한 범위 내에 있을 때 별도의 리스트를 활용하여 원소가 등장한 횟수를 기록하고, 횟수만큼 해당 숫자를 출력해준다. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능 메모리가 낭비될 수 있음 순서를 살펴보면 최대값을 담을 수 있도록 사이즈를 1 크게 잡고 리스트를 생성한다. 카운팅한다. 카운트 횟수 만큼 출력한다. 시간복잡도? O(N+K) , N은 데이터 개수 K는 최대값의 크기 Code #include #include #define ARRAYSIZE(A) sizeof(A)/sizeof((A)[0]) using namespace std; int main(void) { int arr[5] = { 4,.. Selection Sort 삽입 정렬 (C++) Selection Sort 삽입 정렬 Selection Sort란? 2번째 원소부터 시작하여 앞쪽의 원소들과 비교하여 삽입 위치를 특정한 후, 원소를 뒤로 옮기고 지정된 자리에 삽입하는 알고리즘 선택 정렬에 비해 효율적이다(최선의 경우 O(N)) 제자리 정렬, 안정 정렬 기준 원소의 앞쪽은 이미 정렬되어 있다고 가정한다. 순서를 살펴보면, 2번째 위치의 값을 tmp에 저장한다. 앞쪽의 원소들과 비교하며 위치를 특정하고 삽입한다. 다음 위치 값을 tmp에 저장하고 반복한다. 이를 애니메이션으로 표현한다면 다음과 같다. 시간복잡도? 최악 - O(N^2) 최선 - O(N) Code #include using namespace std; int main(void) { int arr[5] = { 5,2,3,7,4 .. [ SWEA ] 1221. GNS D3 C++ 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 문자열을 입력받을 때 문자열에 해당하는 값을 카운팅한 후, 0부터 9까지 카운트만큼 출력해준다. 코드 #include using namespace std; int getNumber(string target) { if (target == "ZRO") return 0; else if (target == "ONE") return 1; else if (target == "TWO") return 2; else if (target == "THR") return 3; else if (target == "FOR") return 4; else if (target =.. [ SWEA ] 1206. View D3 C++ 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 기준이 되는 건물의 위치를 Y라고 가정하면, Y-1, Y-2, Y+1, Y+2 위치 중 가장 높은 건물의 높이보다 Y위치의 건물이 더 높을 때 그 차이를 세대수의 합에 더해준다. 코드 #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); for (int t = 1; t > N; int* arr = new int[N]; for (int i = 0; i > arr.. Bubble Sort 버블 정렬 (C++) Bubble Sort 버블 정렬 Bubble Sort란? 서로 인접한 두 원소의 대소를 비교 하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 안정 정렬(Stable sort) 배열 내부에서 swap이 발생하기 때문에 별도 메모리 공간 불필요 = 제자리 정렬(in-place sorting) 순서를 살펴보면 [ X 회전 ] 0번째 원소와 1번째 원소를 비교하며 큰수를 뒤로 보낸다. 이를 N-X번째 원소까지 반복한다. 1번을 수행하고 나면 가장 큰 값이 마지막 위치로 이동된다. 1,2를 반복한다. 이를 애니메이션으로 표현한다면 다음과 같다. 시간복잡도? O(N^2) Code #include using namespace std; int main(void) { int arr[5] = {19,2,4,1.. 이전 1 2 3 4 5 ··· 18 다음
