어 나 갱수.

이번 글에서는 자료구조 트리(Tree)에 대해서 정리하겠습니다. 트리란?트리(Tree)는 컴퓨터 자료구조에서 계층적인 자료를 표현하는 데 있어 사용되는 자료구조입니다.실제 나무를 거꾸로 한 것과 같은 모양을 하고 있어 트리(Tree)라고 표현합니다. 트리는 노드로 이루어진 자료구조트리는 하나의 루트노드를 가진다.각각의 간선은 방향성을 가지며, 부모는 자식에게만 연결가능하다.루트 노드는 0개 이상의 자식 노드를 가지고 있다.그 자식 노드 또한 0개 이상의 자식 노드를 가지고 있고, 이게 반복적으로 정의된다.트리는 사이클(cycle)이 존재할 수 없다.트리 관련 용어간선(edge) : 노드와 노드를 연결하는 선루트 노드(root node) : 부모가 없는 최상단에 위치하는 노드 (A)단말 노드(leaf no..

스택(Stack)은 말 그대로 '쌓아놓은 더미'를 뜻합니다. 식당에 쌓여있는 접시 더미, 책상에 쌓인 책, 겹겹이 쌓인 상자 모두 스택의 예에 해당합니다. 스택(Stack) 자료구조를 쉽게 예를 들어보자면, 박스 쌓기를 생각하면 됩니다. 박스를 아래에서 하나씩 쌓고, 그 박스를 뺄 때는 마지막에 쌓은 박스부터 빼야 한다는 점을 생각하면 쉽습니다. 후입선출(LIFO: Last-In First-Out) 스택의 가장 큰 특징은 후입선출(LIFO)입니다. 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미입니다. 스택의 입출력은 맨 위에서만 이루어지기 때문에 스택의 중간에 데이터를 삽입하거나 삭제하는것은 불가합니다. 프링글스를 생각하면 쉽습니다. 과자를 만들때 가장 나중에 넣은 과자를 제일 먼저 먹고, 가장 ..

오늘은 자료구조에서 Array와 LinkedList에 대해 알아보겠습니다. 배열(Array) 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다. 메모리 상에서 연속적으로 저장된다는 특징이 있기 때문에, index를 통한 접근이 용이하다. 배열의 크기를 처음 정하고 이후에는 변경하지 못한다. 장점 인덱스 접근 가능 : 인덱스를 통해 임의의 원소에 접근 가능하다. 처리하는 데이터의 양이 많아질수록 더 유리하다. 연속된 메모리 할당 : 주소값으로 원소에 접근할 수 있어서 편리하다. 단점 삽입 삭제가 어려움 : 원소를 삽입하거나 삭제할 경우, 해당 원소 이후 모든 원소를 한칸씩 밀거나 당겨야 하는 상황이 발생한다.(데이터를 연속된 메모리에 저장하기 때문이다) 배열의 크기는 고정적 :..

오늘은 자료구조 맵(Map)과 해시테이블(Hash Table)에 대해 알아보겠습니다. Map이란 Map은 키(Key)와 값(value)으로 저장하는 자료구조이다. 각 키는 중복이 될 수 없으면 키를 이용하여 해당 값을 빠르게 찾을 수 있다. 해싱(Hashing) 해싱 함수는 키(Key)를 받아서 정수값인 해시코드(HashCode)를 반환하고 반환된 해시코드는 값이 저장되는 버킷의 인덱스가 된다. Hash Table이란? 배열과 해시 함수를 사용하여 map을 구현한 자료구조 위의 그림과 같이 k1이라는 키(Key)를 해싱함수에 넣으면 해시코드를 반환하고 그 해시코드를 인덱스로 버킷을 만들어서 저장을 한다. 구조 키(Key) : 고유한 값. 해시 함수의 input이 된다. 값(value) : 저장소에 최종적..