힙(Heap) 힙의 특징은 다음과 같다. - 최대 원소에 즉각적으로 접근할 수 있다. O(1) - 원소 삽입과 삭제에 대해 O(logN)의 시간복잡도를 만족한다. 이러한 특징을 만족하기 위해 완전이진트리(Complete Binary Tree)를 이용한다. * 완전 이진트리: 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식이 있고, 마지막 레벨에서는 왼쪽부터 차례대로 노드 존재 위와 같은 완전 이진 트리 표현은 다른 노드를 가리키는 포인터를 저장할 필요가 없다. 그렇기 때문에 메모리 사용 측면에서 효율적이다. 부모노드에서 자식노드로 이동하는 것은 배열의 인덱스 계산으로 쉽게 이루어진다. 예를 들어, 부모 노드의 인덱스가 i라면, 자식 노드의 인덱스는 2 * i + 1, 2 * i + 2이다. 반대로 자..
https://dev-haram.online/67 [2. 트리, 힙, 그래프] 이진 검색 트리(Binary Search Tree) 이진 검색 트리 (Binary Search Tree) 이진 검색 트리는 다음과 같은 속성을 갖는 이진 트리이다. - 부모 노드의 값 >= 왼쪽 자식 노드의 값 - 부모 노드의 값 18, 15 < 18, 17 < 18 이기 때문에 위 그림처럼 17 dev-haram.online 앞선 게시글에서 이진 검색 트리에 대해 정리했다. 이진 검색 트리의 시간 복잡도에 대해 서술할 때, 트리의 삽입 순서에 따라 시간 복잡도가 달라진다고 언급했었다. 이를 조금 더 자세히 살펴보면, 위 그림에서 왼쪽 트리와 오른쪽 트리를 비교해보면, 오른쪽 트리가 더 균형이 잡혀있다고 할 수 있다. 균형 트..
이진 검색 트리 (Binary Search Tree) 이진 검색 트리는 다음과 같은 속성을 갖는 이진 트리이다. - 부모 노드의 값 >= 왼쪽 자식 노드의 값 - 부모 노드의 값 18, 15 < 18, 17 < 18 이기 때문에 위 그림처럼 17의 오른쪽 하위노드에 18이 삽입된다. BST에서 원소 삭제하기 BST에서 원소를 삭제할 때에는 단순히 노드를 삭제하는 것 뿐만 아니라, 노드 삭제 후 전체 트리가 BST 속성을 만족하도록 해야 한다. 이를 위해서 첫 번째단계로 삭제할 노드를 찾는다. 이후에는 해당 노드의 자식 노드에 따라 수행할 행동이 달라지게 된다. 1) 삭제할 노드의 자식 노드가 없는 경우: 단순히 해당 노드를 삭제하면 된다. 2) 삭제할 노드의 자식 노드가 하나인 경우: 노드 삭제 후, 부..
한 학기 동안 공들여서 진행한 프로젝트가 드디어 최종 발표로 끝을 냈다. 10/20 에 첫 주제 발표를 시작으로 2/2에 최종 발표를 마쳤으니까 대략.. 3달 반 정도 되지 않을까 싶다. 이번에 참가한 프로그램은 펄어비스와 경희대학교 소프트웨어융합학과에서 진행하는 펄어비스 인재양성 프로그램이다. 쉽게 말해 펄어비스에서 장학금을 제공하면서 경희대학교 소프트웨어융합학과 학생들을 키우고, 해당 학생들은 주제를 정하고 교수님의 피드백과 함께 프로젝트를 진행하면서 펄어비스의 기준에 걸맞는 최종 프로젝트 완성을 목표로 진행하게 된다. 물론 난 소프트웨어융합학과는 아니었지만 ㅎㅎ.. 대략 열명이 진행했는데, 이 중 나 포함 두 명이 컴퓨터공학과였다. 나는 전에 소융 수업인 게임 PX 디자인 수업을 들었었고, 해당 수..
Camera 1. Camera Array 카메라 여러대를 이용해서 3D Mesh Model을 얻는 기술이다. Static Objec는 카메라 한대로도 가능하다. 2. Lens Array (Integral Imaging) 여러 시점의 렌즈를 통해 3D 모델을 얻는 기술이다. 이를 위해서는 모두 같은 동률의 렌즈가 필요한데, 비싸다. 카메라 모듈 하나에 약 1000원 정도인데, 렌즈를 15개를 넣으면 15000원.. 사업성이 충분하지 않다. 3. Digital Holography (CGH) 레이저를 이용해서 사물의 Absolute Depth를 파악하여 3D 모델을 얻는 기술이다. Hologram Mark 다른 건 3D 모델을 2D 화면으로 3D 모델을 가져오는 기술이었는데, 이거는 3D 모델을 3D 환경에서..
선형 자료 구조로 표현할 수 없는 대표적인 문제로 계층적 문제(hierarchical problem)와 순환 종속성(cyclic dependency) 문제가 있다. 회사의 조직도, 대학의 교과 과정 계층도 등은 계층적으로 데이터를 표현해야 한다. 이 때 사용하는 자료 구조는 트리 (tree)이다. 위 그림처럼 트리는 계층을 구성한다. 데이터가 저장된 부분은 노드(node)라고 부르고, 노드와 노드 사이를 잇는 선을 edge라고 부른다. 가장 맨 위에 나타나는 노드를 root node라고 한다. 트리의 기본 구조에 대한 요약이었고, 트리의 원소를 순회하는 방법은 세 가지로 나뉜다. 전위 순회 (preorder traversal) 이 방법은 현재 노드를 먼저 방문하고, 그 다음은 현재 노드의 왼쪽 하위 노드..
문제 링크: https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기..
문제 링크: https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 전설카드 레드카드 오렌지카드 퍼플카드 블루카드 청록카드 그린카드 그레이카드 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의..
