kms0204

자료구조: 일차원 배열시간 복잡도: 배열이 완전히 정렬된 경우 : 첫번째로 마주치는 반복문만 돌고 끝남배열이 거의 정렬된 경우 : O(N)  -> 사전작업을 통해 배열을 거의 정렬된 상태로 만들어놓고 삽입정렬을 수행하면 굉장히 빨라진다! 이런 매력 때문에 다른 정렬을 사용하는 경우에도 가끔씩 삽입 정렬을 섞어서 사용하곤 한다.일반적인 경우, 최악의 경우 : O(N^2)따라서 최선의 경우 O(N), 최악의 경우와 평균적인 경우 O(N^2)"재귀적 성격"을 포함하며, 삽입 정렬이 제대로 정렬한다는 것을 "수학적 귀납법"으로도 증명할 수 있다.삽입 정렬은 선택정렬보다 2.5배 정도 빠르고, 버블정렬보다 11배 정도 빠르다. ( 버블  사용 목적 : 숫자의 오름차순 or 내림차순 정렬#include #inclu..

자료구조: 일차원 배열시간복잡도: 모든 경우에 O(N^2)사용 목적 : 숫자의 내림차순 or 오름차순 정렬#include #include int main(){ int arr[] = {1,2,3,4,5,6,7,8,9,10}; int arr_size = sizeof(arr) / sizeof(int); //mixing for(int i = 0; i arr[i+1]){ int temp = arr[i]; arr[i] = arr[i+1]; arr[i+1] = temp; } } } //print result for (int i = 0; i 개념 요약 : (오름차순 기..

자료구조: 일차원 배열 시간복잡도: 모든 경우에 O(n^2)사용 목적: 숫자의 내림차순 or 오름차순 정렬 #include #include int main(){ int arr[] = {1,2,3,4,5,6,7,8,9,10}; int arr_size = sizeof(arr) / sizeof(int); //mixing for(int i = 0; i 0; j--){ int max_num= arr[0]; int max_index = 0; for (int i = 0; i 개념 요약: (오름차순 기준) 배열의 처음부터 끝까지를 순환하여 가장 큰 값을 찾고, 맨뒤로 보내기(교환)

Brute force는 "난폭한 힘", "짐승 같은" 이라는 뜻이다. 그리고 이것이 이 알고리즘의 모든걸 설명한다. 브루트 포스 알고리즘은 이름 그대로, 조합 가능한 모든 문자열을 조합해 보는 알고리즘이다. 주로 암호학에서 사용되며, 흔히 브루트 포스 공격, 무차별 대입 공격이라고도 불린다. 그뿐만 아니라 다른 알고리즘 분야에서도 사용된다. 모든 영역을 전체 탐색하는 알고리즘이며, 선형 구조+비선형 구조를 모두 탐색하기 위해 순차 탐색 / 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)를 사용한다.(기본) 사실, 어떤 방식으로든 전체 탐색을 통해 문제를 해결하면 브루트 포스 알고리즘으로 풀었다고 할 수 있다. 이 알고리즘은 시간과 자원이 엄청나게 들어가지만, (시간 복잡도나 자원 측면에서 조차 효율적..

그리디 알고리즘이란 당장 할 수 있는 선택 중에 최적의 선택을 하는 알고리즘이다. 상황을 전체적으로 보고, 최적의 결과값을 내는 건 아니다. "앞으로 어떻게 될진 모르겠지만, 일단 지금 당장 내가 할 수 있는 선택 중에 최적의 선택을 하고 보겠어"에 가깝다. 예를 들어보자, 출발지부터 목적지까지의 최단 경로를 구해야 하는 상황이 생겼다. 이때 그리디 알고리즘은 모든 경로를 종합적으로 고려하여 최적의 경로를 찾는 것이 아니다. 출발지에서 갈 수 있는 가장 짧은 경로, 그다음 경로들 중에 가장 짧은 경로, 그다음 다음의 경로들 중에 또 가장 짧은 경로... 이리하여 목적지까지의 경로를 찾는다. 따라서 그리디 알고리즘이 항상 최적의 답을 낼 수 있는 건 아니다. 그리디 알고리즘이 최적의 답을 낼 수 있는 최고..

#include int main() { int n; char str[100001]; scanf("%d %s", &n, str); if (n

#include int main() { int n, k, cnt = 0; char str[20001]; scanf("%d %d %s", &n, &k, str); for (int i = 0; i < n; i++) if (str[i] == 'P') for (int j = i - k; j = 0 && j < n && str[j] == 'H') { str[j] = '-'; str[i] = '-'; cnt++; break; } printf("%d", cnt); return 0; } 식탁의 길이 n과 햄버거를 선택할 수 있는 길 k, 사람들과 햄버거가 놓인 식탁(문자열)이 주어진다. 이때, 햄버거를 먹을 수 있는 최대의 사람 수를 구하는 문제이다.(1

#include int main() { int n,arr[101],temp1,temp2,cnt=0; scanf("%d", &n); for (int i = 1; i

#include int main() { int n,result=1; scanf("%d", &n); for (int i = 1; i = 0 ) 결과값을 저장할 변수인 result를 선언하고, 1로 초기화하였다.(1로 초기화한 이유는 뒤에서) n을 입력받고, 1부터 n까지 반복하는 for문을 선언하고, result에 i를 계속 곱해주게 하였다. n이 0이라면 애초에 for문을 돌지 않고 1로 초기화된 result를 출력하므로, 0!을 출력할 수 있다. n이 1이라면 1 x 1인 셈이므로, 1!을 출력할 수 있다. n이 0과 1이 아니라면, 팩토리얼은 1x . . . x n-1 x n이므로, 마찬가지로 n!을 출력할 수 있다.

#include int main() { int n, cnt = 0; scanf("%d", &n); if (n == 1) { printf("1"); return 0; } for (int i = 1; i =100 && i