트리 용도 용어 정리 종류 이진 트리 일반 트리 스레드 이진 트리 구현 배열 표현법 연결리스트 표현법 트리 활용 탐색 집합 표현 허프만 코드 트리 트리란 그래프의 한 종류로 무방향 연결 비순환 그래프(Connected Undirected Acyclic Graph)이다. 루트 노드가 존재하고, 루트 노드를 제외한 모든 노드의 in-degree가 1인 방향그래프라고 말할 수도 있다. 계층적인 구조를 가지며 그래프의 한 종류이므로 비선형 자료구조에 속한다. 용도 계층적인 조직을 표현하기 위해 사용되거나, 컴퓨터의 디렉토리 구조 / 인공지능의 decision tree 등에 이용된다. 또한 자료의 탐색 / 정렬 / DB 구성이나 분자구조식 설계 등에서도 다양하게 이용된다. (결정트리)(이진탐색) 용어 정리 노드 ..

그래프 용도 용어 정리 기본 심화 구현 인접 행렬 인접 리스트 비교 연산 분류 방향성에 따른 분류 연결에 따른 분류 사이클에 따른 분류 특수한 그래프 탐색 도출된 문제들 관련 알고리즘 참고 그래프 그래프란 '노드'와 노드를 연결하는 '간선'으로 이루어진 자료구조이다. 지금까지의 살펴본 자료구조들(리스트, 스택, 큐 등)과는 달리 그래프는 비선형 자료구조 이다. 용도 그래프는 일상생활에서 연결되어있는 객체 간의 관계를 표현할 때 사용된다. 예로 지도나 지하철 노선도, 전기회로, 도로 등을 들 수 있다. 또한 컴퓨터 세부전공에서는 통신 네트워크 분야에서도 쓰이며, 논리회로를 설계하고 분석하는 데에도 사용된다. 최근에는 웹사이트의 링크 연결(Page Rank)이나 SNS 상의 친구관계를 표현하는 데에도 사용되..

서론 자료구조 자료구조는 컴퓨터에서 자료를 정리하고 조직화하는 다양한 구조를 말한다. 프로그램은 자료구조와 알고리즘으로 이루어져있기 때문에, 자료구조는 반드시 공부해야하는 분야이다. 자료구조는 먼저 단순 자료구조와 복합 자료구조로 구분되고, 복합 자료구조에는 선형 구조와 비선형 구조가 있다. 순차적으로 살펴보자. 배열, 문자열 연결 리스트 스택, 큐, 덱 그래프 트리 힙 구조체

스택 특징 용도 연산 삽입 삭제 접근 구현 큐 용도 종류 연산 삽입 삭제 접근 구현 우선순위 큐 덱 용도 구현 스택 스택은 LIFO(Last-In First-Out), 즉 후입선출의 자료구조이다. 구조는 다음과 같은 형태이며, 접시처럼 쌓여서 이후에 삽입된 데이터가 먼저 빠져나가도록 되어있다. top 변수는 가장 최근에 들어온 요소를 가리키며 스택이 비어있으면 -1이다. 특징 LIFO 내부 요소를 확인할 방법이 pop 말고는 없다. 용도 입력의 역순이 필요할 때 스택을 주로 사용하며, 함수의 호출에서 복귀 주소를 기억하기 위해서 시스템 스택이 사용되기도 한다. 또한 괄호 검사, 계산기, 미로 탐색 등의 경우에 스택이 유용하게 사용된다. 계산기에서 중위 표기식(infix)을 후위 표기식(postfix)으로..

연결 리스트 리스트란? 정의 배열과의 비교 연산 삽입 삭제 접근 종류 / 구현 리스트란? 리스트는 순서를 가진 항목들의 모임이다. 이를 나타내는 대표적인 방법은 2가지가 있는데, 하나는 배열을 이용하는 방법이고 나머지 하나는 연결리스트를 이용하는 방법이다. 배열을 이용한 리스트를 선형리스트라고 하는데 구현 자체는 간단하고 임의접근이 가능하지만, 삽입 / 삭제 연산 시 다른 요소들의 이동이 불가피하므로 오버헤드가 크다. 연결리스트는 구현이 복잡하고 순차접근이 필요하지만 삽입, 삭제가 효율적이다. 정의 연결리스트란 아래의 그림과 같이 데이터와 링크로 이루어진 노드로 구성되어있다. 링크는 다음 요소를 가리키는 포인터이다. 연결리스트의 처음에는 헤드 포인터가 헤드 노드를 가리키고 있으며, 마지막 노드의 링크는 ..

목차 배열 선언 초기화 접근 다차원 배열 희소 행렬 표현 주소와 포인터 포인터 특징 제약 동적 메모리 할당 동적 배열(vector) 문자열 선언 초기화 함수 배열 / 문자열 배열 배열이란 단일 식별자로 _같은 자료형_의 여러 변수를 접근할 수 있게 해주는 자료구조이다. 선언 c++에서는 int arr[3];와 같이 자료형 배열이름[배열 길이];로 변수를 선언한다. 이 때, 대괄호 내의 요소의 갯수는 '컴파일 타임 상수'여야한다. 소스코드를 컴파일할 때, 고정 배열의 길이를 알아야하기 때문이다. 따라서 매크로 기호 상수 (ex_ #define ARRAY_LEN 5)나 열거자(ex_enum A{ARRAY_LEN = 5})는 배열의 길이로 사용할 수 있다. const 또한 컴파일 시 고정되는 상수이므로 사용가..

타원곡선 DSA 디지털 서명 자료조사 DSA란? 디지털 서명 알고리즘(Digital Signature Algorithm, DSA)은 디지털 서명을 위한 표준이다. NIST가 1991년 8월 DSS라는 미국 전자서명 표준에서 이용하기 위해 정부용 전자서명 알고리즘으로 발표했으며, 현재는 DSA와 함께 ECDSA, RSA를 사용하고 있다. 디지털 서명 인증 방식 전자서명(디지털 서명)은 무결성, 인증, 부인방지를 만족해야한다. 전자서명에는 공개키 암호화 알고리즘이 쓰이며 크게 3가지 종류의 알고리즘이 있다. 합성수의 소인수분해문제가 어렵다는 데에 기초한 RSA형 알고리즘 유한체의 이산대수 문제가 어렵다는 데에 기초한 ElGamal형 알고리즘 타원곡선을 이용한 EC-DSA, EC-KCDSA DSA는 이 중 E..

파일 시스템 정리 개요 오랜 기간 동안 저장되어야하는 정보의 저장에는 몇가지 조건이 있다. 프로세스가 종료된 후에도 정보가 유지되는 비휘발성 많은 정보를 저장할 수 있는 큰 용량 다수의 프로세스가 동시에 접근 가능한 접근성 오랜 기간동안 큰 정보를 저장하는 장치 중 하나인 Disk는 고정된 크기의 block들로 구성되어있는데, 다음과 같은 질문들을 불러일으킬 수 있다. Disk에 저장한 정보를 어떻게 찾을 것인가? 정보의 양이 방대해서 정보를 찾기가 쉽지 않다. 빈 공간을 어떻게 관리할 것인가? 새로운 정보를 저장할 때 빈 공간을 찾아서 사용해야한다. 사용자 별 권한을 어떻게 관리할 것인가? 데이터를 보호해야한다. 이 해답은 파일 과 파일시스템 에서 찾을 수 있다. 파일 파일은 저장 장치에 정보를 저장하..