코딩하는 해맑은 거북이

트리 - 계층적인 구조 - 사이클을 포함하지 않음 (부모-자식 관계) - 특별 노드(root)가 존재 - 서로 독립적인 서브트리를 가짐 트리의 종류 - 일반 트리 : 자식 노드의 수가 제한이 없음 - 이진 트리 : 자식 노드의 수가 2개 이하이다. 트리 기초 용어 - 루트(root) : 최상위 노드 (ex) A - 단말노드(terminal node) : 자식이 없는 노드 (ex) E,F,G,H,I,J - 형제노드(sibling) : 같은 층에 있는 노드 (ex) E,F,G - 레벨(level) : 트리의 각층의 번호 - 높이(height) : 트리의 최대 레벨 (ex) 3 - 차수(degree) : 노드가 가지고 있는 자식 노드의 개수 (ex) B의 차수는 3 트리의 표현 - 일반적인 구조 → 문제점 :..

큐(Queue) : FIFO (First-in-First-Out) 삽입(rear)과 삭제(front)가 다른 장소에서 이루어지는 순서 리스트 배열 큐 구현 - 큐 구조 정의 #define Max_Queue_Size 10 // 최대 큐크기 typedef int element; element queue[Max_Queue_Size]; int rear = -1; int front = -1; - 큐의 구현 방식 1) 선형 큐 : 단순 선형 배열로 구현한 큐로 포화 상태(Full)일 경우 배열을 조정해야 한다. 2) 원형 큐 : 선형 큐의 해결방법으로 큐의 시작과 끝이 마치 원으로 연결된 것 같이 사용한다. - 원형 큐는 rear과 front를 최초 0에서부터 시작한다. - rear = (rear+1) mod MA..

스택 : LIFO (Last-In-First-Out) 기본 연산인 삽입(push)과 삭제(pop)가 한쪽 끝(top)에서만 이뤄지는 순서 리스트 배열 스택 구현 - 스택 구조 정의 #define Max_Stack_Size 10 // 최대 스택크기 typedef int element; element stack[Max_Stack_Size]; int top = -1; - 공백 상태 int is_empty() { return (top == -1); } - 포화 상태 int is_full() { return (top == (Max_Stack_Size - 1)); } - 삽입 void push(element item) { if (is_full()) { printf("Stack full\n"); exit(1); } ..

리스트 동일 특성을 갖는 항목들의 모임 선형리스트 순서에 따른 항목들의 모임 리스트의 구현 1) 배열 구현이 단순하나 삽입/삭제 연산이 비효율적이다. 정적인 구조로 크기가 고정되어 있다. 2) 연결리스트 구현이 복잡하나 삽입/삭제 연산이 효율적이다. 동적인 구조로 크기에 제한을 받지 않는다. 연결리스트의 구조 - 노드 구조 : 데이터 + 다음 데이터를 가르키는 주소(포인터) 필드로 구성 다음 데이터가 없을 경우 포인터의 주소값은 None(또는 Null)이다. ** C/C++언어 - 노드 구조 정의 typedef struct ListNode { int data; struct ListNode* next; } ListNode; - 삽입 1) head가 NULL인 경우 -> 삽입 노드가 head 2) 리스트의 ..

배열 : 연속된 메모리 위치의 집합 배열의 저장방식 - 행 우선 순서 : c, c++, python - 열 우선 순서 : fortran 언어 배열의 표현 (행 우선) - 2차원 배열의 주소 계산 : int a[m][n] a[i][j]의 주소 = base + (i∙n + j) ∙ sizeof(int) - 3차원 배열의 주소 계산 : int a[l][m][n] a[i][j][k]의 주소 = base + ((i∙m∙n + j∙n) + k) ∙ sizeof(int) 구조체 : 타입이 다른 자료들을 그룹화한 것 typedef struct { char name[10]; int age; float salary; } person; 자체참조 구조 그룹의 구성 요소 중 자신을 가리키는 포인터 존재 typedef struc..

자료구조를 정리하게 된 계기 더보기 코딩테스트에서 쉬운 자료구조 문제가 출제되었는데 정확하게 기억나지 않았다. 그 문제에만 많은 시간을 들였지만 결국 풀지 못했던 적이 있다. 그래서 학부시절 배웠던 자료구조 일부를 다시 정리하고 까먹지 않도록 복습하기 위해서 글을 남긴다. 자료구조 : 주어진 문제를 해결하기 위해 필요한 데이터의 조직화 알고리즘 : 특정한 일을 수행하는 명령어들의 유한 집합 알고리즘 문제 유한한 입력 데이터 → 자료구조 + 알고리즘 → 입력 데이터에 대응되는 결과 알고리즘 조건 - 입력 : 0개 이상 입력 - 출력 : 1개 이상 출력 - 명확성 : 각 명령은 모호하지 않아야 함 ex) x = 1/n (X) if (n != 0): x = 1/n (O) - 유한성 : 한정된 단계 후에 반드시..