Falling in Love with Coding

분할 기법 1. K 번째 작은 수 찾기 1) 문제 - 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수는? 2) 문제 풀이 - 10, 7, 2, 8, 3, 1, 9, 6 이라는 숫자 중에서 세 번째 작은 수 구하기 1. 10, 7, 2, 8과 3, 1, 9, 6으로 분할 2. 10, 7, 2, 8 중 세 번째 작은 수는 8 3. 3, 1, 9, 6 중 세 번째 작은 수는 6 4. 작은 문제의 해결책이 큰 문제의 해결책으로 이어지지 않는다. 2. 분할(Partition) ① 임의로 피벗 설정 ② 다운 포인터와 업 포인터 설정 ③ 다운은 피벗보다 작거나 같은 것, 업은 피벗보다 크거나 같은 것 찾음 ④ 스와핑 ⑤ 포인터가 일치하거나 교차할 때까지 ③, ④를 반복 ⑥ 업 포인터 ..

재귀란? - 수학이나 컴퓨터 과학 등에서 자신을 정의할 때, 자기 자신을 재참조하는 방법 - 재귀 함수의 형태로 많이 사용 재귀 호출의 개요 1. 재귀 호출이란? 1) 정의 "자기 자신을 호출하여 순환 수행되는 것" ▪ 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출 방식 보다 재귀 호출 방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있음 2) 특성 대표적인 분할 정복 알고리즘 ① 문제의 크기 N ② 큰 문제를 작은 문제로 환원 ③ 작은 문제 역시 큰 문제와 유사함 ④ Self Call, Boomerang 2. 재귀 호출의 예 1) 팩토리얼(Factorial) 연산 ▪ 1~n의 모든 자연수를 곱하여 구하는 연산 ▪ 마지막에 구한 하위 값을 이용하여 상위 값을 구하는 ..

힙를 이용한 우선 순위 큐 힙와 관련된 주요 개념 이해 1) 힙(Heap) “쌓아 놓은 더미” 2) 용어 - 최대 힙(Max Heap) ▪ 키 값이 큰 레코드가 우선 순위가 높은 것으로 간주 ▪ 루트 노드의 키가 가장 큼 - 최소 힙(Min Heap) ▪ 최대 힙과는 정반대 ▪ 키 값이 작을수록 우선 순위가 높음 - 정렬 ▪ 이진 탐색 트리는 값의 크기를 기준으로 삽입되기 때문에 왼쪽 노드보다 오른쪽 노드가 더 큰 값을 가짐 ▪ 힙은 키를 기준으로 값을 정렬하기 때문에 값들끼리의 상관관계는 없음 힙의 특징 - 힙의 구성 힙 = "완전 이진 트리" ▪ 배열로 표시하는 것이 가장 효율적 ▪ 루트부터 시작해서 위에서 아래로, 왼쪽에서 오른쪽으로 진행 ▪ 노드 필기하는 순서로 트리를 순회하면서 인덱스를 부여 ▪..

큐, 스택과 달리 중요도에 따라 먼저 처리하는 방식 - 시간에 따른 우선 순위 : 스택, 큐 -시간 외 다른 가치 우선 순위 : 우선 순위 큐 ▪ 우선 순위 큐는 스택이나 큐 보다 일반적인 구조 - 키의 필요 여부 ▪ 에서는 키(= 우선 순위 값) 필드가 필요 ▪ , 에서는 시간에 따라 자료구조를 조직화하게 되므로 키 필드가 불필요 추상 자료형 우선 순위 큐 - 용어 ▪ Create : 새로운 우선 순위 큐를 만들기 ▪ Destroy : 사용되던 우선 순위 큐를 파기하기 ▪ Add : 현재 우선 순위 큐에 새로운 레코드를 삽입하기 ▪ Remove : 가장 우선 순위가 높은 레코드를 삭제하기 ▪ IsEmpty : 현재 우선 순위 큐가 비어있는지 확인하기 - 우선 순위 큐에서의 삭제(Remove) 작업 ▪ ..

큐잉 이론(Queueing Theory) - 서버의 수 : 2대 - 각 서버의 수행 시간 : 1분 - 객체의 유입량 : 30명 / 1시간 * 평균 고객 수, 기다리는 고객 수 예상 1. 추상 큐(Abstract Queue) 1) 구성 및 삽입과 삭제 방법 ▪ 선형 정렬을 이용 ▪ 삽입과 삭제가 개별적으로 실행 ▪ 삽입(Push Into)에 어떤 객체든 제한이 없으며, 그 객체는 큐의 Back ▪ 큐의 처음 객체는 Front ▪ 삭제(Pop From)는 큐의 현재 Front에서 실행 2) 선입 선출(Firtst-In-First-Out, FIFO) 자료구조 3) 4가지 연산 * 2가지 예외 상황 ▪ 빈 큐에서 삭제(Pop) 연산 혹은 첫 객체(Front) 참조 시 정의되지 않음 2. 응용 분야 1) 손님-제..

스택의 괄호 검사 1. 개요 - 스택의 괄호 검사 ▪ 수식에 포함되어 있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 후입선출 구조로 구성되어 있음 ▪ 후입선출 구조의 스택을 이용하여 괄호를 검사함 ▪ 수식을 왼쪽에서 오른쪽으로 하나씩 읽으면서 괄호 검사 ① 왼쪽 괄호를 만나면 스택에 Push ② 오른쪽 괄호를 만나면 스택을 Pop하여 마지막에 저장한 괄호와 같은 종류인지를 확인 - 같은 종류의 괄호가 아닌 경우 괄호의 짝이 잘못 사용된 수식임 ▪ 수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택이 됨 - 수식이 끝났어도 스택이 공백이 되지 않으면 괄호의 개수가 틀린 수식임 2. 알고리즘 - 괄호의 쌍 검사 알고리즘 testPair( ) exp ← Expression; Stack ..

기본 연산 Push와 Pop 1. Push와 Pop 연산 - 스택에서의 원소 삽입/삭제 과정 * 공백 스택에 원소 A, B, C를 순서대로 삽입하고 한번 삭제하는 연산과정 동안의 스택 변화 2. Push 알고리즘 - 스택의 Push 알고리즘 ① top ← top+1; ▪ 스택 S에서 top이 마지막 자료를 가리키고 있으므로 그 위에 자료를 삽입하려면 > 먼저 top의 위치를 하나 증가(+1) ▪ 만약 이때 top의 위치가 스택의 크기(stack_SIZE)보다 크다면 > 오버플로우(Overflow) 상태가 되므로 삽입 연산을 수행하지 못하고 연산 종료 ② S(top) ← x; ▪ 오버플로우 상태가 아니라면 스택의 top이 가리키는 위치에 x 삽입 push(S, x) top ← top+1; // ① if (..

1. 개요 - 접근, 삽입 및 삭제 * 스택 탑만 접근 가능 * 한쪽 끝에서 삽입, 삭제 ▷ 삽입, 삭제 위치를 스택 탑 부근으로 제한 ▷ 구현 자료구조에서 탑이 아닌 다른 곳을 접근할 수 있어도 하지 않기로 약속 - 연산 스택 탑에 푸시(Push) - 삽입, 팝(Pop) - 삭제 2. 추상 자료형 스택 - 주요 작업 - 주요 함수 ▪ GetTop(Push(S, X)) = X ▪ Pop(Push(S, X)) = S ▪ IsEmpty(Create( )) = TRUE ▪ IsEmpty(Push(S, X)) = FALSE ▪ GetSize(Push(S, X)) = GetSize(S) + 1 스택의 구현 1. 배열을 이용한 스택의 구현 - 연산 // StackA.h (C Interface by Array) #d..

연결 자료구조 1. 순차 자료구조의 문제점 - 문제점 1) 삽입 연산이나 삭제 연산 후에 연속적인 물리 주소를 유지하기 위해서 원소들을 이동시키는 추가적인 작업과 시간 소요 * 원소의 개수가 많을수록 원소들이 이동 작업으로 인한 오버 헤드가 많음 * 삽입, 삭제, 연산이 많이 발생하는 경우에 성능 상의 문제 발생 2) 순차 자료구조는 배열을 이용하여 구현하기 때문에 배열이 갖고 있는 메모리 사용의 비효율성 문제를 그대로 가짐 2. 연결 자료구조의 정의 - 연결 자료구조(Linked Data Structure) : 자료의 논리적인 순서와 물리적인 순서가 일치하지 않는 자료구조 * 각 원소에 저장되어 있는 다음 원소의 주소(Pointer)에 의해 순서가 연결되는 방식 -> 물리적인 순서를 맞추기 위한 오버 ..

연결 리스트 1. 연결 리스트란? * 리스트의 목록을 순서대로 연결한 것 2. 연결 리스트의 기초 typedef struct { int Data; //노드 내부의 실제 데이터 또는 레코드 node* Next; //Next가 가리키는 것은 노드 타입 } node; //구조체에 노드라는 새로운 타입명 부여 typedef node* Nptr; //Nptr 타입이 가리키는 것은 노드 타입 Nptr p, q; //Nptr 타입 변수 p, q를 선언 - 노드 이어붙이기 p = (node *)malloc(sizeof(node)); p->Data = 33; p->Next = (node *)malloc(sizeof(node)); p->Next->Data = 22; p->Next->Next = NULL; 3. 출력, 삽입..