sundori DevStory

#1 이진트리의 순회 이진트리의 순회 개념 순회(Traversal)란 모든 원소를 하나라도 빠트리거나 중복하지 않고 처리하는 연산을 의미한다. 리스트, 스택, 큐 등과 같은 선형 자료구조는 원소를 1:1 관계로 구성하기에 순회 연산이 필요가 없지만 이진트리는 1:2의 비선형 계층 구조이기에 현재 노드를 처리한 뒤에 왼쪽 노드, 오른쪽 노드 둘 중 어떤 노드를 처리할지 결정하는 순회 연산이 필요하다. 순회연산 작업 D: 현재 노드를 방문하여 처리. 작업 L: 현재 노드의 왼쪽 서브 트리로 이동. 작업 R: 현재 노드의 오른쪽 서브 트리로 이동. 이 3가지의 작업의 수행 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나눈다. 전위 순회 전위 순회(Preorder Traversal)는 D -> L -> R..

목차 01 트리의 이해 트리(Tree)는 자료들이 리스트, 스택 큐와 같은 1:1 관계의 선형 구조가 아니라 1:n 관계의 비선형 자료구조이며, 계층 자료구조이다. 트리의 구성 요소 노드 Node: 트리를 구성하는 원소(자료)를 노드(Node)라고 한다. 간선 Edge: 노드를 연결하는 선. 루트 Root 노드, Level 0: 트리의 시작 노드. 형제 Sibling 노드: 같은 부모 노드를 가진 자식 노드들. 조상 Ancestor 노드: 루트 노드까지 이르는 경로에 있는 노드는 모두 그 노드의 조상. (노드 K의 조상은 F, B, A) 서브 트리 Subtree: 자식 노드들은 독립하여 새로운 트리 구성이 가능 따라서 각 노드는 자식 노드 수만큼 서브트리를 가짐. (노드 B의 자손 노드는 서브트리 E의 ..

연결 리스트 스택 방식 #include #include #include // 구조체 정의 typedef struct Node { int x; // 노드의 데이터 필드 struct Node* link; // 다음 노드를 가리키는 링크 필드 } Node; // 노드를 연결 리스트에 삽입하는 함수 Node* insertNode(Node* tail, int data) { // 새로운 노드 생성 Node* newNode = (Node*)malloc(sizeof(Node)); if (!newNode) { fprintf(stderr, "메모리 할당 실패.\n"); return NULL; } // newNode 초기화 newNode->x = data; newNode->link = NULL; if (tail == NUL..

목차 # 순차 자료구조의 개념 자료는 구조화하는 방법에 따라 리스트, 스택, 큐, 데크, 트리, 그래프 등으로 나뉘는데 이러한 자료구조 유형을 프로그램으로 구현하는 방식에는 순차 자료구조와 연결 자료구조가 있다. 순차 자료구조 메모리 저장 방식 : 순차 자료구조는 구현할 자료들을 논리적인 순서대로 메모리에 연속하여 저장하는 방식. 연산 특징 : 삽입, 삭제 연산을 해도 빈자리 없이 자료가 순서대로 연속하여 저장되며 변경된 논리적인 순서와 저장된 물리적인 순서가 일치. 프로그램 기법 : 배열을 이용하여 구현 연결 자료구조 메모리 저장 방식 : 연결 자료 구조는 노드라고 하는 여러 개의 메모리 청크에 데이터를 저장하며, 메모리에 저장된 물리적 위치나 순서와 상관없이, 링크에 의해 논리적인 순서를 표현하는 방..

목차 # 재귀호출의 개념 재귀호출은 함수가 자기 자신을 호출하여 순환하여 수행되는 것으로 순환 호출 또는 Recursion이라고 부른다. 함수에서 실행해야 하는 작업에 따라 재귀호출을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성이 가능하다. 재귀호출을 사용하는 경우는? 팩토리얼 함수 대표적인 재귀호출 함수는 팩토리얼(Factiroal)인데 n에 대한 팩토리얼 함수는 1부터 n까지 모든 자연수를 곱하는 연산이다. #include int fact(int n){ int value; if(n

목차 # 구조체 개념 구조체도 배열처럼 여러 데이터를 그룹으로 묶어 하나의 자료형으로 정의가 가능하며, 배열은 자료형이 같을 때만 그룹으로 묶을 수 있지만, 구조체는 서로 다른 자료형도 그룹으로 묶을 수 있어 다양한 자료형을 가지거나 복잡한 자료의 형태를 정의할 때 유용하게 사용한다. 자료를 체계적으로 관리하려면 일정한 단위 형식으로 구성해야 하는데, 밑에 표가 이를 알려준다. 행, ROW, RECORD, 데이터베이스(RECORDS, Tuple) 열, Column, Field 행 ROW RECORD 김00 2014년 가입 3000 하00 2015년 가입 4000 홍00 2018년 가입 2000 권00 2023년 가입 5000 열, Column, Field 명칭 열, Column, Field 행 ROW R..

목차 # 포인터 개념 사용한느 모든 변수는 메모리의 특정 위치에 저장되는데 그 위치를 나타내는 메모리 주소를 포인터라고 한다. 포인터 변수는 메모리의 주소값을 저장하며, 포인터 변수 P가 어떤 변수 A의 주소를 저장하고 있다는 것은 포인터 변수 P가 변수 A의 위치(메모리 주소)를 가리키고 있다는 의미이다. 다른 말로는 포인터를 사용해 다른 변수를 액세스 할 수 있다는 소리이다. int A; int *P = &A; // 메모리 주소 한 개 저장. /* *int A에서 int 형 A변수를 선언했을 때 할당된 메모리 번지 예를들어 1번지라할 때, int *P = &A에 의해서 *변수 A의 주소 1번지를 포인터 P에 저장하므로 포인터 P는 변수 A를 가리키게 된다. *그러면 변수 A와 포인터 P가 논리적으로 ..

목차 # 배열의 개념 배열(Array)은 자료형이 같은 자료를 나열하여 메모리에 연속으로 저장하여 만든 자료 그룹이다. 예를 들어 요일을 나타내는 월, 화, 수, 목, 금, 토, 일과 같이 각각 변수로 선언하면 변수를 7개나 만들어 개별적으로 사용해야 하지만 하나로 묶어 배열로 만들면 배열을 한 번만 선언해 만들 수 있고, 각 요일이 배열의 요소가 되어 다루기 편해진다. # 1차원 배열 1차원 배열을 선언하는 형식은 밑과 같다. 자료형 배열이름 [배열요소의 개수 = 인덱스(idx)]; int array[10]; Tip. 변수 이름을 정할 때 영문자, 숫자 밑줄을 사용하며 첫 글자는 숫자를 사용할 수 없고 알파벳 대문자와 소문자를 구분하며 키워드나 예약어는 사용할 수 없다. 배열 선언의 예 의미 배열 요소..

목차 #1 알고리즘 알고리즘은 주어진 문제를 해결하는 방법을 추상화하여 일련의 단계적 절차를 논리적으로 기술해 놓은 명세서이다. 알고리즘 표현 방법의 종류 자연어를 이용한 서술적 표현 알고리즘을 사람이 쓰는 자연어(언어)로 표현하는 방법이다. 자연어는 서술적일 뿐만 아니라 쓰는 사람에 따라 일관성이나 명확성을 유지하기 어렵다. 따라서 누구라도 쉽게 이해하고 쓸 수 있어야 하는 알고리즘을 표현하는데 한계가 있다. 순서도를 이용한 도식화 알고리즘을 순서도(Flow Chart)를 작성하는 규칙에 따라 도식화하는 방법이다. 순서도를 이용하면 명령의 흐름을 쉽게 파악할 수 있지만 복잡한 알고리즘을 표현하는 데에 한계가 있다. 프로그래밍 언어를 이용한 구체화 알고리즘을 프로그래밍 언어를 사용하여 표현하는 방법이다...