분류 전체보기

https://www.acmicpc.net/problem/1167아.. 어렵다 처음 생각으로는 DFS 를 여러번 수행해서 각 노드에 대한 최대 길이를 구하려고 했지만N = 100,000 이고 DFS 를 각 노드에 대해 수행하면 빨라야 O(N^2) 이기 때문에 당연히 시간초과가 발생하는거였다.(* 10,000,000,000 번의 계산이 필요한데 일반적인 CPU 는 1억번의 연산 당 1초가 걸리기 때문에 100초가 걸린다.) 어쩔 수 없이 구글링을 해봤는데단 두 번의 DFS 만으로 트리의 지름을 알 수 있는 방법이 존재했다. 트리의 성질을 이용하면 가능한데, 자세한 증명은 아래 접은 글에 첨부해놓았다.더보기https://velog.io/@besyia0k0/Algorithm-diameter-of-tree [알..

0. 들어가기 전 Heap은 '우선순위 큐'에 사용되기 위해 필수적으로 알아야 하는 자료구조입니다. 추가적으로 흔히 동적으로 변수를 만들 때 해당 변수가 저장되는 공간인 Heap 과는 다른 의미입니다. 1. Heap Heap 은 최소값 또는 최대값을 빠르게 찾아내기 위해 완전이진트리의 형태로 만들어진 자료구조입니다. 이진 트리는 아는데 완전 이진트리는 무엇일까? 1.1 Complete Binary Tree 트리(Tree)는 계층 구조를 갖는 자료구조로서, 서로 연결되어 있는 노드들의 집합입니다. 트리에는 자식들과 가지의 형태로 연결되어있는 루트 노드가 있습니다. 이때 이진 트리(Binary Tree)는 자식 노드의 개수를 최대 2개로 정한 트리입니다.  사실 이진 트리는 우리가 일전에 살펴본적이 있습니다..

0. 2-3 Tree Likewise, 2-3 Tree is also a height balanced tree. The time complextity of search/insert/delete is O(logN)(* A 2-3 tree is a B tree of order 3) 1. Properties of 2-3 tree Nodes with two children are called 2-nodes. The 2-nodes have one data value(* one key) and two childrenNodes with three children are called 3-nodes. The 3-nodes have two data value(* two keys) and three childrenThat ..

0. 들어가기 전2024.05.02 - [자료구조 및 알고리즘] - 자료 구조 및 알고리즘 9 - AVL Tree   1. 구현 앞서 글을 통해 삽입이나 삭제를 통해 불균형이 생기는 경우 어떻게 AVL Tree 가 균형을 맞출 수 있는지에 대해 알아봤습니다. 요약하자면, 크게 4가지 case 로 불균형이 생길 수 있는데LL caseLR caseRL caseRR case입니다. 위 4가지 case 에 대한 구현이 가장 중요한 점입니다.    2. Node 노드는 이전 노드들과 달리 BF, height 요소를 추가적으로 가집니다. (* 해당 요소들에 대한 설명은 이전 글에 자세히 설명했습니다.) 또한 이전 노드 클래스와 달리 reValuing() 이라는 함수도 갖고 있는데, 삽입이나 삭제 이후 변화가 생긴 ..

KeyWord :호스트, 도메인, IP, HTTP 상태코드, Statefull, Stateless, 세션, 쿠키  0. 클라이언트 - 서버 웹 서비스를 예로 들어 설명하자면, 흔히 컴퓨터, 즉 데스크탑이나 노트북으로 자주 사용하는 사이트들이 웹 사이트입니다. 이때 클라이언트란 서버의 서비스를 받아 사용하는 장치 혹은 프로그램을 의미합니다. 그렇다면 서버는 무엇일까? 서버는 데이터를 포함하거나 네트워크의 다른 컴퓨터에서 엑세스하는 기능을 제공하는 컴퓨터입니다.   일반 서버의 유형으로는파일을 저장하는 파일 서버이름과 주소를 저장하는 이름 서버프로그램과 애플리케이션을 저장하는 애플리케이션 서버인쇄 작업을 해당 대상으로 스케줄하고 지시하는 인쇄 서버가 있습니다. 만약 www.naver.com  이라는 URL ..

0. AVL Tree AVL 트리는 발명자의 이름인 Adelson-Velsky and Landis 에서 따온 이름으로 자가 균형 이진 탐색 트리입니다. 자가 균형 이진 트리는 스스로 균형을 잡는 트리라는 의미로 삽입, 삭제와 같이 데이터 균형이 달라질 것 같은 수행에서 스스로 균형을 맞추도록 트리의 구조를 바꿉니다. 일반적인 이진 탐색 트리와 달리 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(logN) 을 보장합니다.(* BST 의 경우 최악의 경우 O(N) 입니다.)2024.04.20 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 8 - Binary Search Tree    1. Definition 1.1 Height-balance property 높이 균형 성질은 트리 T 에 대해 모든..

들어가기 전. 스택에 관해서는 이전 자료구조 수업 정리에서 충분히 설명했다고 생각하기 때문에 자세한 설명은 생략하겠습니다.2024.04.11 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack Stack 은 ArrayList 와 비슷하게 실제 JAVA 에서는 vector 를 기반으로 구현합니다. 이는 자료의 크기가 동적으로 변할 수 있음을 의미하고, 이에 관한 기능은 ArrayList 와 매우 유사합니다.2024.04.26 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 2 - ArrayList Stack 코드 import Interfaces.Istack;import java.lang.reflect.Array;import jav..

들어가기 전. Stack 이나 Queue 는 이전 자료구조 수업에서 설명한 바가 있으니 가볍게 넘어가겠습니다.2024.04.11 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack 0. Stack 스택은 컴퓨터에서 아주 많이 사용되는 자료구조입니다. 예를 들어, 웹 사이트의 "뒤로 가기" 기능, 가까이는 IDE 에서 Undo 기능 또한 스택으로 구현됩니다. 스택은 말 그대로 쌓아놓은 더미를 뜻합니다. 쉽게 이해하자면 벽돌을 쌓는 것과 유사합니다. 가장 먼저 쌓는 벽돌은 가장 아래에 위치할 것이고, 가장 나중에 들어온 벽돌은 가장 위에 위치할 것입니다. 벽돌을 다 쌓은 후 벽돌을 치운다고 했을 때, 가장 먼저 치워야 하는것은 가장 위에 있는 벽돌, 즉 가장 마지막에 올..