진진진 개발일지

퀵 정렬(Quick Sort) 기준이 되는 피벗(pivot)을 기준으로 배열을 두 그룹으로 나눈 후 피벗을 기준으로 더 작은 값은 왼쪽으로, 큰 값은 오른쪽을 옮김. 1. 한 배열의 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 할 때 2. a[pl] >= x인 pl과 a[pr] x) pr--; if (pl name, y->name); }

삽입 정렬(Insertion Sort) i (0 tmp; j--) { a[j] = a[j - 1]; // tmp가 더 작으므로 정렬된 부분을 한 칸씩 뒤로 미룸 } a[j] = tmp; // 찾은 자리 j에 tmp를 넣음 } } 시간 복잡도: O(n^2) - avg, worst (best는 O(n))

선택 정렬(Selection sort) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 1. 정렬되지 않은 부분에서 가장 작은 키의 값을 선택 2. 아직 정렬하지 않은 부분의 첫 번째 요소와 교환 이 과정을 n-1회 반복 void selection(int a[], int n) { int i, j; for (i = 0; i < n - 1; i++) { int min = i; for (j = i + 1; j < n; j++) if (a[j] < a[min]) min = j; swap(a[i], a[min]); } } 시간복잡도: O(n^2) - best, avg, worst 모두 동일

버블 정렬(Bubble sort) 서로 인접한 두 원소를 비교하여 정렬되어 있지 않은 경우에 교환하는 정렬 알고리즘 *일련의 비교 과정을 패스(pass)라고 함 비교 횟수: (n-1) + (n-2) + ... + 1 = n(n-1)/2 이므로 시간복잡도 O(n^2) (best, avg, worst 모두) #include #include #define swap(x, y) do {int t = x; x = y; y = t;} while(0) void bubble(int a[], int n) { int i, j; for (i = n-1; i > 0; i--) { for (j = 0; j a[j + 1]) swap(a[j], a[j + 1]); } } } int main..

직접 재귀: 자신과 같은 함수를 호출 간접 재귀: 함수 a가 함수 b를 호출하고 다시 함수 b가 함수 a를 호출하는 구조 순차곱셈 (팩토리얼) int factorial(int n){ if(n > 0) return n * factorial(n-1); else return 1; } 유클리드 호제법(최대공약수) int gcd(int x, int y){ if(y == 0) return x; else return gcd(y, x%y); } 하노이의 탑 작은 원반이 위에, 큰 원반이 아래에 위치할 수 있도록 원반을 3개의 기둥 사이에서 옮기는 문제. 모든 원반은 규칙에 맞게 첫 번째 기둥에 쌓여 있고, 이 상태에서 모든 원반을 세 번째 기둥으로 최소의 횟수로 옮겨야 함. 해결 방법: 맨 밑의 원반을 제외한 위의 원..

큐(queue): 선입선출 구조 인큐(enqueue): 데이터를 넣음 디큐(dequeue): 데이터를 꺼냄 프런트(front): 데이터를 꺼내는 쪽 리어(rear): 데이터를 넣는 쪽 배열로 큐 만들기 배열 que[]={1, 2, 3} 인큐: que[3] = 4; 디큐: x = que[0]; -> 이후의 모든 요소를 한 칸씩 앞으로 옮김: 복잡도 O(n) ! 링 버퍼로 큐 만들기 링 버퍼: 배열의 처음과 끝이 연결되었다고 보는 자료구조 첫 번째 요소가 front, 마지막 요소가 rear-1 프런트와 리어의 값을 업데이트하며 인큐와 디큐를 수행하므로 복잡도 O(1) ! 헤더파일 IntQueue.h #ifndef __IntQueue #define __IntQueue typedef struct { int ma..

IntStack.h #ifndef __IntStack #define __IntStack typedef struct { int max; //스택 용량 int ptr; //스택 포인터 int* stk; //스택 첫 요소 포인터 } IntStack; int Initialize(IntStack* s, int max); int Push(IntStack* s, int x); int Pop(IntStack* s, int* x); int Peek(const IntStack* s, int* x); void Clear(IntStack* s); int Capacity(const IntStack* s); int Size(const IntStack* s); int IsEmpty(const IntStack* s); int IsF..

#include #include #include // score_rows는 2차원 배열 score의 행 길이, score_cols는 2차원 배열 score의 열 길이입니다. int* solution(int** score, size_t score_rows, size_t score_cols) { // return 값은 malloc 등 동적 할당을 사용해주세요. 할당 길이는 상황에 맞게 변경해주세요. int* answer = (int*)malloc(sizeof(int)*score_rows); double* avg = (double*)malloc(sizeof(double)*score_rows); for(int i=0;i

#include #include #include // 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요. int solution(const char* my_string) { int answer = 0; int index =0; char array[] = "0123456789+- "; int num = 0; int flag_num = 0; int flag_sign = 1; int i; while(index < strlen(my_string)){ for(i=0;i flag_num while문을 나온 후에도 마지막 숫자를 더하거나 빼줘야 함

내가 작성한 풀이 #include #include #include // 파라미터로 주어지는 문자열은 const로 주어집니다. 변경하려면 문자열을 복사해서 사용하세요. long long solution(const char* numbers) { long long answer = 0; char* ptr; ptr = numbers; while(strncmp(ptr,"",1)!=0){ answer *= 10; if(strncmp(ptr,"zero",4)==0) ptr += 4; else if(strncmp(ptr,"one",3)==0) {answer+=1; ptr += 3;} else if(strncmp(ptr,"two",3)==0) {answer+=2; ptr += 3;} else if(strncmp(ptr,"..