트리와 그래프 그래프를 설명하기 이전에, 트리가 빠질 수 없습니다. 그래프는 겉보기에 트리와 상당히 유사하지만, 더 다양한 표현 방법으로 인해 기능이 많아지고, 그럼으로써 어려워졌다고 볼 수 있습니다. 이번 포스트에서는 트리 자체에 대한 내용을 따로 다루지 않을 것이고, 필요하시다면 이전글을 참조해주세요. 차이 Tree 무조건적으로 부모-형제 관계와 같이 상-하 구조로 연결되어 있다. 위에서 아래로 방향성을 갖고 있다. 계층 모델을 사용 Graph 부모-형제 개념이 없다. 방향성에 대한 제약이 없다(양방향, 단방향). 연결 상태를 필수적으로 갖지 않아도 된다. 네트워크형 모델을 사용한다. 추가 용어 방향 그래프 : 간선의 방향이 존재하는 그래프. 무방향 그래프에서는 양방향으로 이동이 가능. 연결 그래프 ..
선행 내용 Map을 이해하시기 위해서는 Set에 대한 이해가 먼저 필요합니다. Set/Map을 구현하기 위한 Hash/Tree에 대한 설명, Set 활용에 대해 정리한 이전 글을 참조해주시면 감사하겠습니다. Set, Map 비교 Set은 값이 곧 저장 위치를 나타내는 자료구조입니다. Set은 기능이 부실한 점이 보였습니다. 예를 들어, 중복 저장이 되지 않는 점, 값을 순서대로 출력할 수 없다는 점 등 부족한 기능이 있었고, 이를 보충하기 위한 방안으로 Set에 좋은 기능은 가져가되, 인덱스를 따로 둠으로써 해당 문제점들을 해결하기 위한 방안인 Map이 있습니다. Set과 Map의 가장 큰 차이는 Set : 값이 곧 인덱스 (값을 해시 코드로 변환해 해당 위치에 저장) Map : 값과 인덱스 구분 (인덱..
개념 Set은 Map과 더불어 프로그래머로써 필수적으로 알아야 할 자료구조 중 하나입니다. Set/Map을 구현한 종류로는 Tree와 Hash가 있는데, 두 가지의 개념 및 Java Collection을 통한 활용을 할 예정입니다. 어떤 것으로 구현했느냐에 따라, 값 추가와 탐색 방법이 상이하며, 그에 따라 구현 방법별 값 추가와 탐색의 시간 복잡도가 다르게 됩니다. 일반적으로 Hash가 Tree보다 더 빠르므로, 자주 사용됩니다. Hash HashSet을 설명드리기 전에, Hash에 대한 이해가 필요하다고 생각됩니다. Set을 배우는 단계에서 Tree는 이미 알고 오셨을 가능성이 높으나, Hash는 아직 생소한 단어일 것이라 생각 되어, 따로 설명드립니다(Tree는 개념 자체는 설명하지 않을 예정입니다..
소개 Tree는 비선형 자료구조 중 하나입니다. 비선형이라는 것은 말 그대로 일직선으로 나타내지 못하는 방식이며, 그중 트리는 계층적 구조를 띄고 있습니다. 계층적 구조라 함은, 일반적으로 조직도를 나타내는 경우 자주 사용되죠. 트리도 그와 비슷합니다. 자료구조를 학습할 때, 사람들이 가장 많이 포기하시는 경우가 선형 자료구조를 어렵게 어렵게 배우고, 비선형 자료구조로 넘어갈 때라는 것 아시나요? (윤성우의 열혈 자료구조 내용) 일반적으로 저희는 나란히 자료가 저장되고, 삭제되는 메커니즘에 익숙합니다. 그런데 갑자기 익숙하지 않게 계층적으로 자료를 저장하고 삭제하려니 난이도가 급증했음을 느끼게 되고, 곧 포기하게 되는 거죠. 부족하지만, 이 게시글이 조금이라도 도움이 되시길 바랍니다... 구조 아까 말씀..
Stack/Queue Stack과 Queue는 통상적으로 List 자료구조를 배운 이후에 학습을 진행하기 때문에, 자료구조라는 말 뜻을 아실 거라고 생각합니다. 두 자료구조 역시 선형 자료구조 중 하나인데, 스택과 큐는 오직 한 방향에서의 데이터의 삽입과 삭제를 진행하는 자료구조입니다. 두 자료구조를 가장 잘 나타낼 수 있는 말이 있죠. Stack : 후입선출(後入先出) Queue : 선입선출(先入先出) 말 그대로, 스택은 가장 마지막에 삽입한 데이터가 가장 먼저 추출되고, 큐는 가장 먼저 들어온 데이터가 가장 먼저 추출되는 형식입니다. 실생활을 예로 들자면, 후입 선출 알고리즘은 실행 취소(Ctrl+z, undo)로 예를 들 수 있고, 선입선출은 일반적으로 음식점에서 채소 및 재료를 꺼낼 때 먼저 들어..
자료구조 List는 자료구조의 일종으로, 자료구조란 자료의 집합을 의미하며, 더 나아가 저장, 삭제, 조회 등을 할 수 있도록 표현한 것이다. 자료구조는 선형 자료구조와 비선형 자료구조로 나뉘게 되는데, 그중 List는 선형 자료구조이다. 전체 자료구조 리스트는 다음과 같다. List List는 대표적인 자료구조 중 하나이며, 이후 학습할 내용인 Tree, Graph 등 다른 자료구조에 비해 통상적으로 난이도가 쉽다고 할 수 있다. 배열과 비슷한 구조를 띄고 있지만, 배열의 치명적인 단점인 크기가 고정적이라는 점을 해결할 수 있는 방법이다. 시간 복잡도 - 조회 O(n) - 삽입, 삭제(가장 앞, 뒤) O(1) 시간 복잡도에서 나타내는 것과 같이, 조회는 느리지만, 단순히 맨 앞 또는 뒤에 값을 추가하고..