노드 기반 자료구조 노드 기반 자료구조는 배열의 정적 길이의 제약과중간 삽입/삭제 시간복잡도를 해결한 자료구조로 링크드리스트가 대표적이다하지만 링크드리스트도 탐색은 O(N)이 걸리기 때문에 이를 해결하기 위해1차원의 링크드리스트를 2차원 계층구조로 만든 것 트리 구조이다 트리(Tree) 노드 기반 계층구조를 가진 자료구조이다트리의 노드들은 위치에 따라 각각 부모와 자식 관계를 가지고 있다트리 관련 용어 - 루트 노드 (Root Node): 트리의 최상단 노드 - 리프 노드 (Leaf Node): 자식 정점이 없는 정점- 서브 트리 (Subtree): 특정 노드 기준으로 해당 노드의 후손 노드들 - 높이 (Height): 계층의 수- 레벨 (Level): 루트노드가 Level 0, 루트노드의 자식이 Lev..
스택과 큐는 이를 활용하는 코딩 테스트 문제가 주로 등장한다 스택(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 InInd..
탐색 알고리즘(Search Algorithm) 자료구조 안에 저장되어 있는 특정 자료를 찾아오는 알고리즘이다대표적인 탐색 알고리즘으로는선형 탐색, 이진 탐색, 해시 기반 탐색이 있다선형 탐색(Linear Search) 자료구조의 모든 자료를 순서대로 훑어가며 특정 자료를 찾는 알고리즘이다예를 들어 반복문을 돌면서 순회하면서 찾는 경우를 의미한다 이진 탐색(Binary Search) 정렬되어 있는 자료구조에 절반씩 자료를 제거해 가며 원하는 자료를 찾는 알고리즘이다단계가 진행 될 때마다 탐색 범위가 절반씩 줄어들어서 이진 탐색이라고 부른다 선형탐색 vs. 정렬 후 이진탐색선형탐색과 이진탐색의 공간 복잡도는 같지만,시간 복잡도는 이진탐색이 O(N) 보다 빠를 수 있다따라서,탐색 빈도가 높다면, 정렬 후 이..
정렬 알고리즘자료구조로 저장된 자료들을 특정한 순서로 정렬하는 알고리즘이다정렬하기 위해서는 모든 데이터를 비교해야 한다최소 한 번씩은 모두 짚고 넘어가야 하다 보니정렬 알고리즘은 아무리 좋은 효율을 내더라도 O(N) 보다 느릴 수밖에 없다여러 가지 정렬 알고리즘이 많지만,효율은 낮지만 구현하기 쉬운 버블소트 (stable)효율이 좋지만 unstable한 퀵소트효율이 좋지만 stable한 머지소트가 대표적이다 정렬 알고리즘의 Stability정렬에서 stability(안정성)란 정렬 알고리즘이 동일한 키 값을 가진 원소들의 상대적인 순서를 유지하는 특성을 의미한다다시 말해, stability가 있는 정렬 알고리즘은동일한 값의 원소들이 정렬 전에 나열된 순서가 정렬 후에도 유지되고stablility가 없는..
자료구조(Data Structure) 자료(Data)를 저장하는 구조를 의미한다각 자료구조마다 장단점이 다르기 때문에 상황에 적절한 자료구조를 잘 선택하는 것이 중요하다자료구조의 종류 선형 자료구조와 비선형 자료구조로 구분된다선형 자료구조: 배열 / 가변배열 / 스택 / 큐 / 해시테이블 비선형 자료구조: 링크드 리스트 / 트리 / 그래프 / 힙 알고리즘(Algorithm) 특정 문제를 해결하는 증명된 방법이다모든 문제를 해결할 수 있는 알고리즘은 존재하지 않는다증명된 방법이기 때문에 굳이 해당 알고리즘 템플릿 코드를 이해하고, 암기하는 것이 중요하다 복잡도(Complexity) 알고리즘을 비교할 때, 시간과 공간을 비교하고시간 혹은 공간을 많이 사용할수록 복잡하다고 말한다복잡도에는 시간 복잡도와 공간..
분할 컴파일 관련된 소스코드끼리 묶어서 .h 파일과 .c 파일로 나눈다 그리고 그 파일들을 각각 컴파일한다 (분할 컴파일) 컴파일 결과인 .o 파일들을 한데 묶어서 빌드하는 방식이다 분할 컴파일 원리 빌드 프로세스에서 컴파일 단계까지는 각각의 .c 파일이 따로 컴파일된다 링크 단계에서 컴파일 완료된 .o 파일들을 묶어서 빌드한다 링킹 단계 전까지는 함수의 정의는 알 수 없다 선언부만으로 컴파일된다 링크 단계에서 각 함수의 정의 부분이 모여서 실행파일이 만들어진다 그래서 예를들어, 정의 부분 add() 함수의 매개변수 자료형이 서로 다르다면 컴파일 에러가 아닌 링크 에러가 발생한다 라이브러리(Library) 오브젝트 파일들을 모아서 묶어 놓은 파일을 라이브러리 파일이라고 한다 즉, 이 라이브러리 파일은 다..
조건부 컴파일 조건에 따라 특정 부분의 소스코드를 컴파일에 포함 혹은 배제시키는 문법이다 #ifndef NULL #define NULL (0) #endif /* NULL이 정의 안되어있다면, 값이 0인 NULL을 정의. */ #if !defined(NULL) #define NULL (0) #endif /* NULL이 정의 안되어있다면, 값이 0인 NULL을 정의. */ #if defined(NULL) #undef NULL #endif /* NULL이 정의되어 있다면, 그 정의를 해제시킴. */ #define NULL (0) /* 값이 0인 NULL을 정의. */ 조건부 컴파일 주의점 #define A #if defined (A) // 참 #define LENGTH (10) #endif #if A // 거..
전처리기(Preprocessor) 프로그래머가 작성한. c 파일을 전처리기는 아래와 같은 전처리 작업을 수행한다 1. 주석 삭제 2. 매크로 처리 (매크로된 것을 모두 복사 붙여 넣기) 3. include 되어 있는 .h 헤더파일 처리 (헤더파일 모두 복사 붙여 넣기) 위와 같은 작업을 통해 만들어진 파일이 Translation unit 파일이다 전처리기 지시자 (#) 전처리기 지시자가 붙은 문을 전처리기 지시문이라고 부른다 ex) #include, #define, #ifndef, #endif, … 전처리기 지시문의 활용 1. 매크로 문법을 통해 텍스트 대체 #define 구문이 대표적이다 소스코드 상의 특정 텍스트를 대체한다 이외에도 #undef 구문 혹은 전처리기 연산자 #, ##을 활용. 2. 다른..
입출력 리디렉션 표준 입력 또는 표준 출력의 소스 또는 대상을 변경하는 기술을 의미한다 이를 통해 프로그램은 사용자 입력이나 출력 대신 파일, 다른 프로세스의 출력 등을 사용할 수 있다 리디렉션은 주로 커맨드 라인 인터페이스(Command Line Interface)에서 사용된다 명령어를 실행할 때 기호를 사용하여 표준 입력 및 표준 출력을 파일로 리디렉션 할 수 있다 입출력 리디렉션 방법 stdin: 문자 stderr: 2> 문자(2번째 출력 ex. 에러 내용 출력) ex) a.exe output.txt 2> error.txt 입출력 리디렉션 예시 #define _CRT_SECURE_NO_WARNINGS #include int main(void) { int ans; scanf("%d", &a..
