다락방

삽입 정렬(Insertion Sort)손 안의 카드를 정렬하는 방법과 유사하다.Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다.2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.과정정렬은 2번째 위치(index)의 값을 temp에 저장한다.temp와 이전에 있는 원소들과 비교하며 삽입해나간다.‘1’번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.시간복잡도평균, 최악의 경우 O(n^2)최선의 경우 O(n)공간복잡도주어진 ..

24.06.21 알고리즘, C알고리즘삽입 정렬(Insertion Sort)손 안의 카드를 정렬하는 방법과 유사하다.Selection Sort와 유사하지만, 좀 더 효율적인 정렬 알고리즘이다.2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다.과정정렬은 2번째 위치(index)의 값을 temp에 저장한다.temp와 이전에 있는 원소들과 비교하며 삽입해나간다.‘1’번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다.시간복잡도평균, 최악의 경우 O(n^2)..

선택 정렬(Selection Sort)해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이다.과정주어진 배열 중에 최소값을 찾는다.그 값을 맨 앞에 위치한 값과 교체한다.맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다.시간복잡도비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸린다. 최선, 평균, 최악이 경우 시간복잡도는 O(n^2)으로 동일하다.공간복잡도주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.장점알고리즘이 단순하다.정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟..

거품 정렬(Bubble Sort)서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.과정1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를,,, 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.시간복잡도O(n^2)정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로..

알고리즘거품 정렬(Bubble Sort)서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 이다.과정1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를,,, 이런 식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다.시간복잡도O(n^2)정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^..

CPU 스케줄링 알고리즘 CPU 스케줄링은 다중 프로그램 환경에서 CPU의 사용 시간을 효율적으로 분배하기 위한 방법이다. 이를 통해 시스템의 성능을 최적화하고, 대기시간을 최소화하며, CPU 사용률을 극대화하는 것이 목표다. 알고리즘 종류 선입선출 스케줄링(FCFS : First-Come, First-Served Scheduling) 이 알고리즘은 먼저 도착한 프로세스부터 처리하는 알고리즘이다. 프로세스 실행 시간을 예측하기 쉽고 단순하고 공평하지만 CPU 버스트 시간이 긴 프로세스가 먼저 도착하면 다른 프로세스들은 긴 대기 시간을 감수해야 하는 호흡성문제가 발생할 수 있다. 최단 작업 우선 스케줄링(SJF : Shortest Job First Scheduling) CPU 버스트 시간이 가장 짧은 프로..

25305 커트라인 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector num_arr; int n, k; cin >> n >> k; for (int i = 0; i > tmp; num_arr.push_back(tmp); } sort(num_arr.begin(), num_arr.end(),greater()); cout

Sort sort 알고리즘은 헤더파일에 속해있다. sort(start,end)를 이용해서 범위에 있는 인자 (element)를 오름차순으로 정렬해준다. quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 nlogn이다. sort(arr,arr+n); sort(v.begin(), v.end()) sort(v.begin(), v.end(), compare()); // 사용자 정의 함수 sort(v.begin(), v.end(), greater()); // 내림차순 sort(v.begin(), v.end(), less()); // 오름차순

1018 체스판 다시 칠하기 #include using namespace std; string WB[8] = { "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", }; string BW[8] = { "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", "BWBWBWBW", "WBWBWBWB", }; string board[50]; int cntWB(int x, int y); int cntBW(int x, int y); int main() { ios_base::sync_with_stdio(false); cin.t..

2231 분해합 #include using namespace std; int main() { int N; int result = 0; cin >> N; for (int i = 1; i < N; i++) { int sum = 0; int num = i; while (num != 0) { sum += num % 10; num /= 10; } if (sum + i == N) { result = i; break; } } cout