노드 기반 자료구조 노드 기반 자료구조는 배열의 정적 길이의 제약과 중간 삽입/삭제 시간복잡도를 해결한 자료구조로 링크드리스트가 대표적이다 하지만 링크드리스트도 탐색은 O(N)이 걸리기 때문에 이를 해결하기 위해 1차원의 링크드리스트를 2차원 계층구조로 만든 것 트리 구조이다 트리(Tree) 노드 기반 계층구조를 가진 자료구조이다 트리의 노드들은 위치에 따라 각각 부모와 자식 관계를 가지고 있다 트리 관련 용어 - 루트 노드 (Root Node): 트리의 최상단 노드 - 리프 노드 (Leaf Node): 자식 정점이 없는 정점 - 서브 트리 (Subtree): 특정 노드 기준으로 해당 노드의 후손 노드들 - 높이 (Height): 계층의 수 - 레벨 (Level): 루트노드가 Level 0, 루트노드의 ..
스택과 큐는 이를 활용하는 코딩 테스트 문제가 주로 등장한다 스택(Stack) 기본적인 구조는 배열과 동일하다 하지만 먼저 들어온 데이터가 나중에 나가는 구조를 가진다 스택 구현 코드 더보기 #define _CRT_SECURE_NO_WARNINGS #include #include enum { FALSE = 0, TRUE = 1, MAXCOUNT = 1024 }; typedef struct Stack { int Data[MAXCOUNT]; size_t Top; } Stack_t; void Push(Stack_t* InStack, int InData); int IsEmpty(Stack_t* InStack); int Pop(Stack_t* InStack); int main(void) { return 0; } ..
배열, 가변 배열, 링크드리스트는 구현을 하는 과제에서 주로 등장한다 배열 배열은 연속적인 메모리 공간에 요소들을 저장하기 때문에 인덱스를 통해 상대적인 위치를 참조할 수 있다 배열을 생성할 때 길이를 지정하고 길이의 변경은 불가능하다 또한, 중간 삽입/삭제가 불가능하다 배열 구현 코드 더보기 #define _CRT_SECURE_NO_WARNINGS #include #include enum { FALSE = 0, TRUE = 1, INVALID_INDEX = -1, MAX_COUNT = 101 }; typedef struct Array { int Data[MAX_COUNT]; size_t Count; } Array_t; void Insert(Array_t* InArray, size_t InIndex, i..
탐색 알고리즘(Search Algorithm) 자료구조 안에 저장되어 있는 특정 자료를 찾아오는 알고리즘이다 대표적인 탐색 알고리즘으로는 선형 탐색, 이진 탐색, 해시 기반 탐색이 있다 선형 탐색(Linear Search) 자료구조의 모든 자료를 순서대로 훑어가며 특정 자료를 찾는 알고리즘이다 예를 들어 반복문을 돌면서 순회하면서 찾는 경우를 의미한다 이진 탐색(Binary Search) 정렬되어 있는 자료구조에 절반씩 자료를 제거해 가며 원하는 자료를 찾는 알고리즘이다 단계가 진행 될 때마다 탐색 범위가 절반씩 줄어들어서 이진 탐색이라고 부른다 선형탐색 vs. 정렬 후 이진탐색 선형탐색과 이진탐색의 공간 복잡도는 같지만, 시간 복잡도는 이진탐색이 O(N) 보다 빠를 수 있다 따라서, 탐색 빈도가 높다면..
정렬 알고리즘 자료구조로 저장된 자료들을 특정한 순서로 정렬하는 알고리즘이다 정렬하기 위해서는 모든 데이터를 비교해야 한다 최소 한 번씩은 모두 짚고 넘어가야 하다 보니 정렬 알고리즘은 아무리 좋은 효율을 내더라도 O(N) 보다 느릴 수밖에 없다 여러 가지 정렬 알고리즘이 많지만, 효율은 낮지만 구현하기 쉬운 버블소트 (stable) 효율이 좋지만 unstable한 퀵소트 효율이 좋지만 stable한 머지소트가 대표적이다 정렬 알고리즘의 Stability 정렬에서 stability(안정성)란 정렬 알고리즘이 동일한 키 값을 가진 원소들의 상대적인 순서를 유지하는 특성을 의미한다 다시 말해, stability가 있는 정렬 알고리즘은 동일한 값의 원소들이 정렬 전에 나열된 순서가 정렬 후에도 유지되고 sta..
자료구조(Data Structure) 자료(Data)를 저장하는 구조를 의미한다 각 자료구조마다 장단점이 다르기 때문에 상황에 적절한 자료구조를 잘 선택하는 것이 중요하다 자료구조의 종류 선형 자료구조와 비선형 자료구조로 구분된다 선형 자료구조: 배열 / 가변배열 / 스택 / 큐 / 해시테이블 비선형 자료구조: 링크드 리스트 / 트리 / 그래프 / 힙 알고리즘(Algorithm) 특정 문제를 해결하는 증명된 방법이다 모든 문제를 해결할 수 있는 알고리즘은 존재하지 않는다 증명된 방법이기 때문에 굳이 해당 알고리즘 템플릿 코드를 이해하고, 암기하는 것이 중요하다 복잡도(Complexity) 알고리즘을 비교할 때, 시간과 공간을 비교하고 시간 혹은 공간을 많이 사용할수록 복잡하다고 말한다 복잡도에는 시간 복..
