본문 바로가기
반응형

분류 전체보기111

트리의 순회 - 전위 순회, 중위 순회, 후위 순회 1. 트리의 순회 (Tree traversal) 트리 순회란 트리의 모든 노드를 방문하는 것을 말합니다. 방문 순서에 따라 다음 3가지 방법이 있습니다. 처음에는 헷갈리지만 몇 번만 연습해보면 매우 간단하다는 것을 깨닫게 되실 겁니다. 2. 전위 순회(preorder) - VLR 전위 순회는 먼저 자기 자신을 방문한 뒤, 왼쪽 자식-오른쪽 자식 순으로 방문합니다. 만약 자식에게 또 자식이 있다면 자식 노드를 방문하기 전에 자식의 왼쪽 자식 노드를 방문합니다. 즉, 자기 자신을 방문한 다음(V) 왼쪽 자식으로 이동하여 자식이 있는 지 확인하고, 있다면 자식이 없는 리프 노드(leaf node)를 만날 때까지 계속 왼쪽으로 이동합니다. 왼쪽 서브트리에 대한 방문을 모두 마친 뒤에야 (L), 오른쪽 자식에 대.. 2022. 10. 11.
[Java] 자료구조 - 트리(Tree) 만들기 1. 트리란 그래프는 정점과 간선으로 이루어져 있습니다. 정점들이 간선으로 연결되어 있는 그래프를 연결 그래프라고 합니다. 만약 한 정점에서 출발해 다시 자기 자신으로 돌아올 수 있는 경로가 있다면 사이클이 존재한다고 합니다. 트리는 사이클이 없는 연결 그래프입니다. 위 그림과 같이 트리는 자료를 계층적으로 표현하고자 할 때 사용됩니다. 각 노드는 상위 노드와 연결되어 있고, 부모-자식 관계를 가지며 같은 레벨에 있는 노드들은 형제라고 부릅니다. 자식이 최대 2명인 트리를 이진 트리라고 하며, 이진 트리가 가장 기본적인 트리의 형태라고 할 수 있습니다. 2. Java로 이진 트리 구현하기 트리에서 하나의 노드는 하나의 데이터 공간과, 왼쪽 자식에 대한 링크, 오른쪽 자식에 대한 링크를 가집니다. Tree.. 2022. 10. 8.
[Java] 자료구조 - LinkedList 1. LinkedList 연결 리스트는 각 요소가 사슬처럼 서로 연결되어 있는 형태의 자료구조를 말합니다. 배열처럼 미리 준비된 공간에 원소를 집어넣는 것이 아니라 그 때 그 때 메모리를 할당하여 기존의 원소와 연결하는 방식이므로 공간 활용 및 삽입, 삭제에 있어서 유리합니다. // 삽입, 삭제 연산 시간 - O(1) 하지만 배열처럼 인덱스를 이용하여 바로 원소에 접근할 수 없고 시작 지점부터 타고 타고 이동해서 원하는 원소에 접근할 수 있다는 것이 단점입니다. // 탐색 시간 - O(n) 연결 리스트에는 리스트의 시작점을 가리키는 포인터 (first)가 필요합니다. 그리고 각 원소들은 값을 저장하는 공간과, 다음 원소에 대한 주소를 저장하는 공간이 필요합니다. C에서는 노드를 data 필드와 link .. 2022. 9. 28.
스택과 (원형) 큐 Stack & Queue 만들기 1. 소개 스택과 큐는 쉽고 간단하지만, 운영체제의 시스템 스택이나 스케줄링 등 다방면으로 활용되는 중요한 자료구조입니다. 스택과 큐는 모두 원소를 하나씩 저장하고 저장된 원소를 순서대로 출력 및 삭제하는 방식으로 동작합니다. 차이점으로는, 스택은 가장 나중에 입력된 원소가 가장 먼저 출력되는 후입선출(Last In First Out, LIFO) 방식인 반면, 큐는 가장 먼저 입력된 원소가 가장 먼저 출력되는 선입선출(First In First Out, FIFO) 방식입니다. 2. 구성 스택과 큐는 기본적으로 원소들을 저장할 저장소와 현재 위치를 기억하는 포인터, 그리고 현재 상태를 체크할 2가지 메서드, 핵심 기능인 삽입과 삭제를 위한 메서드 2개가 필요합니다. 3. 구현 with Java (1) 스택.. 2022. 9. 27.
해피해킹 하이브리드 키보드 사용 후기 및 깨알팁 1. 해피해킹이 뭐냐 해피해킹은 pfu에서 만든 무접점 키보드입니다. 이 포스트를 검색해서 읽고 계시는 여러분들은 어느 정도 키보드에 관심이 있고 해피해킹을 사용 중이거나 구매를 고려하고 있는 분들이리라 생각되어 구체적인 설명은 생략하도록 하겠습니다. 종류가 생각보다 다양한데, 19년 이후 판매되고 있는 3세대 제품은 유선 클래식/ 무선 하이브리드 일반 / 무선 하이브리드 저소음(타입S) 가 있습니다. 저는 최신 제품으로 블루투스를 지원하면서 심심하지 않으면서도 보다 저렴한 것을 원했기에 하이브리드 일반 버전을 구매했습니다. (타입S는 몇 만원 정도 더 비쌉니다!) 국내 출시되지 않았기 때문에 직구를 하시거나, 네이버나 오픈마켓 등에서 구매대행 업체를 통해 구매하거나 당근시장에 가끔 올라오는 중고제품을 .. 2022. 9. 24.
[Java] 자료구조 - 큐(Queue) 1. 큐란 선입선출(First In First Out, FIFO) 방식의 자료구조입니다. 먼저 들어간 놈이 먼저 나온다는 뜻입니다. 21 32 13 24 54 16 즉, 위의 큐에서 삭제를 하면 21이 제거되고 새로운 값 16을 추가하면 54의 오른쪽에 저장됩니다. 2. Java 라이브러에서의 큐 Java에서는 Queue 인터페이스를 제공하고 있고, 이를 구현하는 클래스로는 AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, Priorit.. 2022. 9. 22.
반응형

티스토리툴바