본문 바로가기

전체 글75

병합 정렬 ( Merge sort ) 병합 정렬- 분할 정복(Divide & Conquer) 방법을 사용하는 알고리즘- 알고리즘을 구현함에 있어서 추가적인 임시 배열이 필요 ( 다른 정렬 알고리즘보다 메모리를 더 잡아먹음 )  시간 복잡도O(N * logN)   퀵 정렬 vs 병합 정렬퀵 정렬은 최악의 경우 O(N * logN) 을 보장하지 못함 ( 최악의 경우 => O(N^2) )병합 정렬은 최악의 경우에도 O(N * logN)을 보장함둘 다 O(N*logN)만큼 걸리더라도 보통 병합 정렬보다 퀵 정렬이 더 빠름 병합 정렬의 동작 원리 분할 ( 가장 작은 단위까지 분할 )   :   하나의 list를 두 개의 균등한 크기로 분할 정렬 ( 가장 작은 단위부터 정렬 )   :   분할된 부분 list를 정렬          =>  위 1,2 .. 2022. 2. 9.
버블 정렬 ( Bubble sort ) 버블 정렬- 바로 옆에 있는 값과 비교하면서 비교할 때마다 값을 스위칭하면서 이동- 선택 정렬과 시간 복잡도는 같지만 실제 수행시간이 가장 느림    => 버블 정렬 : 매번 비교할 때마다 값을 스위칭   => 선택 정렬 : 전체 원소를 비교해서 최솟값을 찾은 후 가장 마지막에만 값을 스위칭 시간 복잡도- O(N^2) #include#includeint main(){ int data[] = {1,5,9,8,2,5,6,3,7,10}; int i,j; for(i = 0; i data[j+1]) std::swap(data[j],data[j+1]); } } for(i=0;i 2022. 2. 9.
삽입 정렬(insertion sort) 삽입 정렬적절한 위치에 삽입한다.버블 정렬, 선택 정렬보다 빠르다.삽입 정렬은 옆의 값과 비교해서 더 클 때만 스위칭하기 때문에 더 빠르다.특정한 경우에 굉장히 빠르게 작용할 수 있다. ( 예 : 거의 정렬되어 있는 데이터일 때 ) 시간 복잡도    =>    O(N^2) 동작 원리- 특정한 위치에서 앞의 원소들과 비교해서 적당한 위치에 들어간다.ex) 1 5 6 7 8 10 4 3 2 9        => 4가 적절한 위치에 들어갈 때 이미 앞 부분은 다 정렬이 되어 있기 때문에 4만 앞의 원소들과 하나씩          비교해가며 들어가면 되기 때문에 매번 비교할 때마다 선택이나 버블처럼 교환하지 않아도 된다.        1 5 6 7 8 4 10 3 2 9  ->  4와 8 비교해서 자리 바꿈  .. 2022. 2. 8.
퀵정렬(Quick Sort) 퀵 정렬데이터의 갯수가 적을 때는 괜찮지만 데이터의 갯수가 10만 개만 넘어가도 보통의 상황에서선택,버블,삽입 정렬 알고리즘을 사용하기가 힘들다. 이런 경우 퀵 정렬을 사용한다면아무리 많은 양의 데이터라도 빠르게 정렬을 할 수 있다.대표적인 분할 정복 알고리즘c 라이브러리로 제공하는 sort() 함수가 퀵 정렬을 기반으로 구현되어 있다.이미 정렬이 되어있거나 거의 정렬되어 있는 데이터에 사용할 때는 성능이 매우 떨어짐 퀵 정렬의 시간 복잡도평균  :  O(N * logN)    -> 반씩 쪼개서 정렬하기 떄문에 logN인 것이다.최악  :  O(N^2) 퀵 정렬이 최악인 경우에도 O(N * logN)을 보장하는 방법- STL 라이브러리에서 제공하는 sort() 함수는 퀵 정렬을 기반으로 하되 별도의 처리.. 2022. 2. 7.
c언어 문자열 c언어를 처음 접했을 때 문자열을 char* 로 저장할 때와 char[]로 저장할 때 많이 헷갈렸다.그래서 차이점을 정리해본다. 배열로 선언된 문자열정상적으로 실행되는 경우1. char s1[10] = "hello";2. char s1[] ="hello"; 3. char s1[10] = "Hello";   s1[0] = 'A';   printf("%s");  // Aello  4. char s1[10] = "Hello";   char s2[10];   scanf("%s",s1);          => 기존에 있던 문자열은 사라지고 입력한 값으로 바뀜   scanf("%s",s2);      5. char buffer[100] = {0,};   FILE* fp = fopen("a.txt","r");   f.. 2022. 2. 4.
이중포인터 C언어로 PostgreSQL과 연동해 CLI에서 음식을 주문하는 대화형 프로그램을 구현할 때 이중포인터 때문에 고생했던 기억이 난다. 이 당시 PGresult 구조체의 주소값을 받아왔어야 됐는데, 받을 때 이중포인터가 아닌 그냥 포인터로 받아와서 함수 내에서 받아온 값을 핸들링한다고 해도 실제 main에 있는 원본은 변화가 없었다. 아무래도 이중포인터는 평생 나를 괴롭힐 것 같아 확실히 정리해두고 가야 할 것 같아서 정리한다. #include #include #include using namespace std; void setToNull(int**); int main(){ int five = 5; int* ptr = &five; printf("&ptr:%p | ptr(변수 five의 주소값 ): %p\n.. 2022. 2. 3.

티스토리툴바