트리 트리의 개념 트리 (Tree) : 계층적인 구조를 가진 자료구조 예 : 가계도, 조직도, 컴퓨터의 디렉토리 구조 등 트리의 특징 노드가 N개인 트리는 항상 N - 1개의 링크(link)를 가진다. 트리의 루트에서 어떤 노드로 가는 경로는 유일하다. 임의의 두 노드간의 경로도 유일하다(같은 노드를 두 번 이상 방문하지 않는다는 조건하에). 일반적으로 각 노드가 데이터를 저장하는 데이터 필드와 자식 노드를 가리키는 링크 필드를 가지게하는 방법으로 프로그램에 표현한다. 트리의 용어 노드 (node) : 트리를 구성하는 기본 요소 루트 노드 (root node) : 계층적인 구조에서 맨 위에 있는 노드 서브 트리 (sub tree) : 트리에서 한 노드와 그 노드의 자손들로 이루어진 트리 부모 노드 (pa..

링크드 리스트 연결 리스트 (Linked List) 연결 리스트의 개념 연결 리스트 (Linked List) : 데이터와 포인터를 가진 각 노드들을 일렬로 연결시킨 형태의 자료구조 예 : 버킷 리스트, 요일들 등 연결 리스트의 특징 메인 메모리상 물리적으로 흩어져있는 데이터들을 서로 연결하여 하나로 묶는 방식 삽입/삭제 시 앞뒤에 있는 데이터들을 이동할 필요없이 해당 데이터들을 연결하는 줄만 수정하면 된다. 첫 번째 데이터만 알면 나머지 데이터들을 연결된 줄로 추적 가능하다. 포인터를 저장하기 위한 추가적인 메모리 공간이 필요하다. 연결 리스트의 구조 노드 (node) : 연결되는 상자, 데이터 필드와 링크 필드로 구성 데이터 필드 (data field) : 저장하고 싶은 데이터가 들어감 링크 필드 (l..

스택과 큐 스택 스택의 개념 스택 (STACK) : 데이터를 쌓아올리는 형태의 자료구조 예 : 접시 더미, 책상에 쌓여있는 책, 창고에 쌓여있는 상자 등 스택의 특징 후입선출 (LIFO: Last-In First-out) 방식 가장 최근에 들어온 데이터가 가장 위에 있으며 가장 먼저 나간다. 데이터의 들어오는 방향과 나가는 방향이 같은 단방향 입출력 구조이다. 스택에서 입출력은 맨 위에서만 일어나며 스택의 중간에서는 데이터를 삭제할 수 없다. 예: 스택에 A, B, C, D 순서대로 입력한 후 하나를 삭제하면 맨 위에 놓여진 D가 삭제된다. 스택의 구조 스택 상단 (stack top) : 입출력이 이루어지는 부분 스택 하단 (stack botton) : 스택 상단 반대쪽인 바닥 부분 요소 (element..

Q1. 2개의 정수를 서로 교환하는 알고리즘을 의사코드로 작성해보자. A1. Q2. 사용자로부터 받은 2개의 정수 중에서 더 큰 수를 찾는 알고리즘을 의사코드로 작성해보자. A2. Q3. 1부터 n까지의 합을 계산하는 알고리즘을 의사 코드로 작성해보자. A3. Q4. set(집합) 추상자료형을 정의하라. 다음과 같은 연산자들을 포함시켜라. Create, Insert, Remove, Is_In, Union, intersection, Difference A4. Q5. Boolean 추상 자료형을 정의하고 다음과 같은 연산자들을 포함시켜라. A5. Q6. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입력이라고 가정하자. A6. Q7. 다음과 같은 코드의 시간 복잡도는? 여기서 n이 프로그램의 입..

자료구조 복습 교재 : c언어로 쉽게 풀어쓴 자료구조 (개정 3판) - 청인국, 공용해, 하상호 지음 1.3 알고리즘의 성능 분석 요즘 컴퓨터는 예전의 컴퓨터에 비하여 엄청난 계산속도와 방대한 메모리를 자랑하고 있으며 계쏙하여 발전을 거듭하고 있음. 하지만 요즘에도 여전히 프로그램의 효율성은 중요함. 이유 : 최근 상용 프로그램의 규모가 이전에 비하여 엄청나게 커지고 있음. 처리해야할 자료의 양이 많기 때문에 알고리즘의 효율성이 더욱 중요함. 사용자들은 여전히 빠른 프로그램을 선호함. 효율적인 알고리즘 : 알고리즘이 시작하여 결과가 나올 때까지의 수행시간이 짧으면서 컴퓨터 내에 있는 메모리와 같은 자원을 덜 사용하는 알고리즘. 수행시간 측정방법 가장 단순하지만 가장 확실한 방법. 알고리즘을 프로그래밍 언..

자료구조 복습 교재 : c언어로 쉽게 풀어쓴 자료구조 (개정 3판) - 청인국, 공용해, 하상호 지음 1.2 추상 자료형 추상 자료형 자료형 (data type) : 데이터의 종류. 우리말로 자료형 자료형의 예 : 기초적인 자료형 : 정수, 실수, 문자형 등 이외 : 스택, 큐, 리스트, 트리 등 C언어에서 제공하는 자료형 : 정수 (ex. 0, 1, 2, ...) 실수 (ex. 3.14) 문자 (ex. 'a', 'b', ...) 배열 ( 동일한 자료형이 여러 개 모인 것 ) 구조체 ( 다른 자료형이 여러 개 모인 것 ) 자료형 기초 자료형 파생 자료형 사용자 정의 자료형 char 배열 구조체 int 포인터 공용체 float 열거형 double 자료형을 작성할 때는 실행 가능한 연산에 대해서도 신경 써야..

자료구조 복습 교재 : c언어로 쉽게 풀어쓴 자료구조 (개정 3판) - 청인국, 공용해, 하상호 지음 1.1 자료구조와 알고리즘 자료구조란? 컴퓨터 프로그램 구성 : "프로그램 = 자료구조 + 알고리즘" - 자료 구조 (data structure) : 프로그램에서 자료들을 정리하여 보관허는 여러 가지 구조들 - 알고리즘 (algorithm) : 주어진 문제를 처리하는 절차 자료구조와 알고리즘은 밀접한 관계. 자료구조가 결정되면 그 자료구조에서 사용할 수 있는 알고리즘이 결정됨. 컴퓨터가 복잡한 자료들을 빠르게 저장, 검색, 분석, 전송, 갱신하기 위해서는 자료구조가 효율적으로 조직화되어 있어야 하고, 각 응용에 가장 적합한 자료구조와 알고리즘을 선택해야 함. 예 : #define MAX_ELEMENTS ..