자료구조

Tree - 깊이 우선 탐색, 너비 우선 탐색, Binary Search Tree

Tree Tree 자료 구조는 대표적인 비선형 구조의 자료 구조이다. 비선형 자료구조란, 선형 구조가 아니라는 뜻. 선형 구조란, 자료 구조를 구성하는 데이터가 연속적으로 나열되어 있는 구조이다. 배열, 큐, 스택, 연결 리스트 등이 모두 해당된다. 반면, 트리는 비선형 구조이다. 이름에서 알 수 있듯이, 자료가 하나의 root에서 시작해 가지치듯이 쭉쭉 확장되는 자료 구조이다. 대표적인 자료구조로 족보를 들 수가 있다. Tree에 쓰이는 용어들도 족보(가계도)와 같은 용어가 많이 쓰인다. 그리고 윈도우의 파일 시스템도 대표적인 트리 구조의 예다. 트리 구조는 상하 관계가 명확하기 때문에, 계층 구조를 구현하는 데 적합하다. Tree 자료 구조는 기본적인 용어들이 많다. 우선 가장 맨 위에 있는 노드를 ..

Hash Table - Hash Table과 충돌, 충돌 해결 기법

해싱(Hashing) 해쉬 브라운(Hash Brown)이라는 음식이 있다. 감자를 잘게 다져서 모양을 잡아 튀긴 음식이다. 맥도날드의 맥모닝 세트에도 있는 음식인데, 술 안주로도 아주 좋다. 어쨌든 이 해쉬 브라운은, 감자를 해쉬(hash)하여 만들어졌다. 기존의 감자의 형체를 알아볼 수 없도록 다져놓은 것이다. 마찬가지로 프로그래밍에서 해싱(hashing)이란, 어떤 특정 값을 받아서 고정된 길이의 새로운 값을 도출해 주는 것이다. 이 때 새로운 값을 해쉬 값이라고 하며, 이러한 기능을 하는 함수를 해쉬 함수(hash function)라고 한다. 그리고 해쉬 함수를 이용해 자료를 저장하는 자료구조를 바로 해쉬 테이블이라고 한다. 해쉬 테이블(Hash Table) 해쉬 테이블은 해쉬 함수로 변환 된 값을..

Stack, Queue, Linked List - 자료 구조와 Big O 표기법

프로그래밍을 배우다보면은 생각지도 못한 배울 것들을 만나게 된다. 특히 점점 심화된 개념을 배우면 배울수록, 코드를 어떻게 짜야할 지 넓은 관점에서 생각하게 한다. 처음 프로그래밍을 배웠을 때는, if문과 for문만 있으면 세상 모든 문제를 다 풀수만 있을 것 같았다. 물론 지금도 for문과 if문을 엄청 자주 쓰지만, 사실 중요한건 단순히 문제를 해결하느냐가 아니고 어떤 방식으로 문제를 해결하느냐가 중요한 것같다. 그런 관점에서 자료구조의 개념은, 문제를 조금 더 넓은 시각에서 볼 수 있게 해주는 것 같다. 각각의 장단점을 가진 여러 자료구조를 문제 해결방식의 하나로 쓰면서, 어떤 코드가 조금 더 효율적일까를 고민하게 만들어준다. 따라서 자료구조는 조금 더 전문적인 프로그래밍 지식을 원한다면, 꼭 알아..