그리디 알고리즘 = 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 코테에서는 그리디 문제를 풀기 위해 최소한의 아이디어가 필요하다. 그리고 이러한 아이디어가 타당성이 있는지 검토를 해야한다. 코테에서의 그리디 문제는 그리디 알고리즘을 통해 얻은 해가 가장 최적이기 때문에 출제자의 의도를 파악하고 그리디하게 문제를 풀자. 대표적으로 거스름돈 문제를 보자. 거스름돈 문제 (500, 100, 50, 10) 해법 : 가장 큰 화폐 단위부터 돈을 거슬러 준다. 1. 동전들 중 큰 단위가 항상 작은 단위의 배수이다. 2. 작은 단위의 동전로 아무리 조합을 해도 큰 단위를 포함했을 때보다 최적인 상태를 만들 수 없다. 따라서 그리디하게 생각하고 이를 뒷받침해줄 근거를 찾는것이 중요하다. n = 1650 cnt =..

오늘은 선택정렬과 삽입정렬에 대해서 공부하겠습니다. 선택정렬과 삽입정렬 모두 시간복잡도가 O(n^2)입니다. 쉽게 설명하자면 이중반복문을 통해 구현하기 때문입니다. 그렇다면 이제 각각의 차이가 무엇인지 알아보도록 하겠습니다. 선택 정렬의 기본적인 아이디어는 리스트를 순회하면서 가장 작은 것을 제일 앞으로 보내는 방식입니다. # include void main(){ int i, j, min, index, tmp; int array[10] = = { 2, 1, 4, 3, 5, 7, 6, 8, 9, 10 }; for(i = 0; i

대표적인 2진 탐색문제이다. 다만 소스코드를 파이썬으로 제출하면 시간초과가 나온다. pypy3로 제출해야한다. import sys n, m = map(int,input().split()) tree = list(map(int,sys.stdin.readline().split())) left = 0 right = max(tree) while leftmid: total += x-mid if total < m: right= mid-1 else: left = mid +1 result = mid print(result)

연결리스트에 의해 구현되는 집합이 더 광법위하게 사용 가능하다. 데이터 구조의 보존 여부에 따라 파괴적(Destructive), 비파괴적(Nondestructive)으로 나눠진다. 단일연결리스트로 구현해보자. typedef struct node{ int elem; struct node* next; struct node* prev; }Node; Union(B) 합집합 단일연결리스트로 구현된 집합 A 와 B가 있다고 가정하면 비파괴적 합집합은 다음과 같이 구한다 Node *Union(Node *A, Node*B) { Node *p; if(A==NULL && B==NULL) return NULL; p= (Node*)malloc(sizeof(Node))l if(A==Null) { p->elem = B->elem..

스택 ADT는 후입선출 방식으로 데이터를 저장, 추출한다. 삽입과 삭제가 일어나는 부분을 탑(top)이라고 명시한다. 스택은 단일연결리스트로 구현이 가능하고 top은 리스트의 맨앞을 가리킨다. 스택은 배열로도 구현이 가능하다. 스택에서의 기본 연산인 push, pop, is_empty에 대해 구현해보자 #include int top = -1; typedef struct stack { char oper; int order; }STACK; void push(STACK stack[], char input, int limit, int order) { if (top >= limit - 1) { return; } stack[top + 1].oper = input; stack[top + 1].order = order..

리스트는 데이터를 순서대로 한줄로 저장하는 구조이다. 단순 연결리스트 아래는 단순한 노드의 구조체 구성과 생성 방법이다. typedef struct node{ int elem; struct node* link; }Node; 노드 생성 방법 Node* getnode(){ Node *NEW; NEW= (Node*)malloc(sizeof(Node)); return NEW; } 단순리스트의 탐색연산 Node *search(Node *head, int x) { Node *p; p = head; while (p != NULL) { if (p->data == x) return p; p = p->link; } return p; } 단순리스트의 삽입연산 void insert_node(Node **head, Node *..