본문 바로가기

CS45

트리 순회(Tree Traversal)란? 트리 순회 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말합니다. 하나도 빠뜨리지 않고, 정확히 한 번만 중복없이 방문해야 하는데, 노드를 방문하는 순서에 따라 세 가지로 나뉩니다. 전위순회(preorder) 중위순회(inorder) 후위순회(postorder) 전위 순회 [Preorder] 루트 노드에서 시작해서 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회하는 방식입니다. 깊이 우선 순회(depth-first-traversal) 이라고도 합니다. 위 예시 트리에 전위 순회 방식을 적용하면, 1 - 2 - 4 - 5 - 3 이 됩니다. 중위 순회 [Inorder] 루트 노드에서 시작해서 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로 순회하는 방식입니다. 대칭 순회(symmet.. 2022. 4. 22.
우선순위 큐 (Priority Queue) 란? 우선순위 큐란? 각 요소가 우선순위를 갖고 있는 자료구조를 말합니다. 일반적인 큐와는 다르게, 입력된 순서와 상관없이 우선순위가 가장 높은 데이터를 가장 먼저 출력하게 됩니다. 우선순위 큐는 Heap을 이용하여, 구현된 자료구조입니다. 우선순위는 배열과 연결리스트로도 구현할 수도 있지만, 최악의 경우에 우선순위 찾기 위해 인덱스의 끝까지 탐색할 수 있기 때문입니다. Heap을 사용한다면, 새 데이터 삽입 시, O(log2N) 그리고 데이터 삭제 시, O(log2N) 입니다. 👇 배열, 연결리스트, 힙 시간 복잡도 비교 더보기 배열 : 우선순위가 높은 순서대로 배열의 가장 앞 부분부터 넣는다면, 우선순위가 높은 데이터를 반환하는 것(삭제)은 맨 앞의 인덱스를 바로 이용하면 되므로 어렵지는 않습니다. 시간 .. 2022. 4. 22.
HashMap & HashTable Hash Algorithm 데이터를 다루는 기법 중에 하나로, 검색과 저장이 아주 빠르게 진행되는 자료구조입니다. 해쉬는 데이터를 검색할 때, 사용할 key 와 value(실제 데이터)가 한 쌍으로 존재하고, key 값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도는 O(1)에 수렴하게 됩니다. 해시가 왜 생겼을까요? 가장 기본적인 자료구조인 배열의 경우, 내부 인덱스를 이용하여 자료의 검색이 한 번에 이루어지기 때문에 빠른 검색 속도를 보이는 반면 데이터의 삽입, 삭제 시 많은 데이터가 밀리거나 빈 자리를 채우기 위해 이동해야 하므로 많은 시간이 소요됩니다. 또한, 연결리스트는 삽입, 삭제 시 인근 노드들의 참조 값만 수정해줌으로 써 빠른 처리가 가능했지만? 처음노드와 마지막 노.. 2022. 4. 18.
HTTP1 vs HTTP2 (두 프로토콜의 차이) HTTP는 1989년에 만들어진 웹의 통신 표준입니다. 97년도에 HTTP/1.1 이 릴리즈 되면서 프로토콜이 거의 수정된 적이 없었습니다. 그러나, 2015년에는 HTTP2 가 나오면서 사용되기 시작했습니다. HTTP2 는 모바일 플랫폼, 서버 집약적인 그래픽과 비디오를 다룰 때, 레이턴시를 줄일 수 있는 여러가지 방법을 제공 했습니다. 또한 그 이후에 점점 더 인기가 많아지면서 현재에는 모든 웹사이트의 1/3 정도 이상이 HTTP2를 지원하는 것으로 알려져 있습니다. 이 설명에선 HTTP 설명을 하기보단, ver1 과 ver2 의 차이점을 위주로 설명할 예정입니다. HTTP 가 무엇인 지를 보고 싶다면, 아래 제가 정리해놓은 글을 한 번 읽고 오시며 좋습니다. https://devnuts.tistor.. 2022. 4. 18.
HTTP 란? HTTP(HyperText Transfer Protocol)는 인터넷에서 데이터를 주고 받을 수 있는 프로토콜입니다. 이번 주제를 알아보기 전에, 프로토콜에 대해서 먼저 설명하도록 하겠습니다. 프로토콜 공통 데이터 교환 방법(의사소통) 및 순서에 대해 정의한 형식, 약속, 규역, 규칙 체계 혹은 프로그램을 일컫는다. 통신 프로토콜은 컴퓨터나 원거리 통신 장비 사이에서 메시지를 주고 받는 양식과규칙의 체계를 말합니다. 즉, 통신 규약 및 약속입니다. 컴퓨터 네트워크 규모가 증가되고, 네트워크를 이용한 정보 전송 수요가 다양화되면서 소프트웨어와 하드웨어 장비가 계속 증가되는 최근의 환경에서 효율적인 정보 전달을 하기 위해서 프로토콜의 기능이 분화되고, 복잡해질 수 밖에 없어졌습니다. 이러한 환경적인 요구를 .. 2022. 4. 17.
이분 그래프(Bipartite Graph)란? 이분 그래프 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프입니다. 다시 말해서, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 합니다. 위 그림을 보면 빨간색, 파란색의 정점이 서로 인접하고 있으며, 같은 색끼리는 인접하지 않습니다. 그리고, 간선이 아예 없고 정점만 있는 경우도 이분 그래프가 됩니다. 이분 그래프는 현실에서도 굉장히 많이 사용하게 됩니다. 몇 가지 예시를 들자면, 학생 - 수업 : 학생들이 어떤 수업을 듣고 있는 지를 관계로 나타낼 수 있습니다. 영화 예약 사이트 회원 - 좋아하는 장르 : 각각의 회원들이 어떤 장르의 영화를 선호하는 지를 나타낼 수 있습니다. 구직자 -.. 2022. 4. 15.
그래프, 인접행렬과 인접리스트 그래프 (Graph) 수학적 정의로 그래프는 객체들의 쌍들이 서로 연관되어 객체의 집합을 이루는 구조를 의미합니다. 쉽게 설명하면? 사물이나 추상적인 개념 간의 연결 관계를 표현한 것이라고 할 수 있습니다. 도시를 연결하는 도로망이나 사람들 간의 관계, 웹 사이트 링크 관계 등이 이에 해당하는 예시입니다. 그래프의 구성 요소 정점 (Vertex / Node) : 그래프에서 위치를 나타냅니다. 간선 (Edge / Link / Branch) : 그래프에서 위치 간의 관계를 나타냅니다. 즉, 각 정점(노드)를 연결하는 선(line)을 의미합니다. 인접 정점 (Adjacent Vertex) : 간선(Edge)에 의해 직접 연결된 정점을 의미합니다. G(V, E) : 그래프는 정점과 간선의 집합이므로 이건, 그래.. 2022. 4. 13.
버퍼(Buffer) 와 캐시(Cache) 캐시(Cache) 캐시는 속도가 빠른 장치(CPU)와 느린 장치(메인 메모리) 사이에서 속도 차이에 따른 병목 현상을 줄이기 위한 범용 메모리를 뜻합니다. 즉, 어떤 시스템 내에서 데이터의 집중적인 사용으로 인해 전체 시스템에 절대적인 영향을 미치는 부분의 사용 빈도가 늘어나 그 부분의 성능이 저하되어 전체 시스템이 마비되는 현상을 줄이기 위한 것압니다. 캐시는 자주 사용하는 데이터나 값을 복사해 놓는 임시 저장소라고 생각할 수 있습니다. 캐시의 접근 시간에 비해 원래 데이터를 접근하는 시간이 더 오래 걸리는 경우 또는 값을 다시 계산하는 시간을 절약하고 싶은 경우에 사용합니다. 캐시는 저장 공간이 작고 비용이 비싸지만, 빠른 성능을 제공합니다. 보통 L1, L2, L3 캐시로 나뉘어지는데, CPU에 가.. 2022. 4. 6.

티스토리툴바