프로그래밍 관련/자료구조 & 알고리즘

트리 TREE 트리 구조(tree 構造, 문화어: 나무구조)란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 트리에서 최상위 노드를 루트 노드(root node 뿌리 노드[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드[*])라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다. 트리 (Tree) 트리 구조란 계층적인 구조를 가지는 자료형태를 말합니다. 노드로 구성된 자료구조이며, 회사의 조직구..

큐 QUEUE 큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. 선형 큐 (linear queue) 은행업무에소 표를 뽑거나 줄을 서서 기다리는 사람들을 생각하면 쉬울 것 같습니다. 크기가 제한되어 있고 빈 공간을 사용하려면 모..

스택 STACK 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 쉽게 어떠한 박스에 물건을 하나씩 담아 넣고 꺼낼려면 위에서부터 꺼내야 하는 상황을 생각하면 될 것 같습니다. 배열을 이용한 스택 구현 class ..

다만, 다른 입력값에서 동일한 해시 값이 발생되는값이 같을 때 발생하는 충돌(Collision)문제가 있는데, 이것을 해결해야 하는 방법이 필요합니다. 1. 열린 어드레싱 방법 (Open Addressing Method) 선형 조사법(Linear Probing) : 충돌이 발생했을때 그 옆자리가 비어있는지 살펴보고, 비어있을 경우 그 자리에 대신 저장하는 방식 [이미지 출처 : http://faculty.cs.niu.edu/] 쉽게 옆자리가 비어있으면, 그 옆자리로.. 그 옆자리가 이미 있으면 그 옆자리로..계속 식으로 이동하게 되는 것 입니다. 계산이 단순하다는 장점이 있지만, 검색에 시간이 많이 소요되고, 테이블 내에 데이터들이 일정한 키 값으로 모이는 현상이 발생합니다. 이차 조사법 (Quadrat..

해시 [Hash] 해시 함수(hash function)는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. 그 용도 중 하나는 해시 테이블이라는 자료구조에 사용되며, 매우 빠른 데이터 검색을 위한 컴퓨터 소프트웨어어 널리 사용된다. 해시 함수는 큰 파일에서 중복되는 레코드를 찾을 수 있기 때문에 데이터베이스 검색이나 테이블 검색의 속도를 가속할 수 있다. 저장된 키와 값을 이루는것을 테이블이라고 하는데 이중에 키에 해당하는 값을 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근하기가 용이하게 만드는 작업이라고 할 수 있습니다. (사전을 생각해보면 적당한..

연결 리스트 (Linked List) 연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 연결 리스트의 종류로는 단일 연결 리스트, 이중 연결 리스트 등이 있다. 연결 리스트는 늘어선 노드의 중간지점에서도 자료의 추가와 삭제가 O(1)의 시간에 가능하다는 장점을 갖는다. 그러나 배열이나 트리 구조와는 달리 특정 위치의 데이터를 검색해 내는데에는 O(n)의 시간이 걸리는 단점도 갖고 있다. 단일 연결 리스트(Single Linked List) 먼저 리스트를 이해하기 위해서는 포..

재귀(Recursion) 재귀(再歸, Recursion)는 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 주로 이 방법은 함수에 적용한 재귀 함수(Recursion Function)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다. 즉, 자기 자신을 반복하여 호출한다고 보면 쉬울 것 같습니다. #include using namespace std; void RecursiveFunction(int num) { if (num >= 10) { cout

빅-오 표기법 (Big-Oh Natation) - 점근 표기법(Aasymptotic notation) 빅-오 표기법 (Big-O Natation) 계산 복잡도 이론에서 사용되는 점근 표기법. 컴퓨터 과학에서는 주로 입력 데이터의 크기와 알고리즘의 소요 시간 또는 메모리의 상관관계를 나타내지만, 엄밀히는 임의의 함수에 대하여 "함수의 입력값(정의역의 원소)이 커짐에 따라 그 출력값(그 원소의 상)이 얼마나 빠르게 커지는가"를 표현한다. 점근 표기법(asymptotic notation) 점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다. 찾아보니 빅-오..