Hello World!

힙과 우선순위 큐 1. 우선순위 큐 Priority Queue(우선순위 큐)는 우선순위를 가진 원소들을 저장하고 우선순위가 높을수록 먼저 출력하는 자료구조이다. 우선순위 큐의 ADT를 살펴봤을 때 핵심적인 기능으로는 '삽입, (우선순위 제일 높은 원소) 삭제, (우선순위 제일 높은 원소) 반환'이 있다. 우선순위 큐는 여러가지 방법으로 구현이 가능하다. 1) 비정렬 시퀀스를 이용한 구현 우선순위 큐를 비정렬 시퀀스를 이용해 구현하는 경우 삽입은 간단하다. 비정렬 시퀀스이므로 시퀀스의 마지막에 삽입하고자 하는 원소를 담은 노드를 매달아 주면 된다. O(1)의 시간이 걸릴 뿐이다. n개의 모든 원소 삽입에 대해 O(1)이 시간이 걸리므로 총 O(n)의 시간이 걸린다. 하지만 우선순위 제일 높은 원소를 찾아 ..

Tree 1. Tree traversal Tree traversal(트리 순회)는 트리 구조에서 각각의 노드를 정확히 한번만, 체계적인 방법으로 방문하는 과정을 말한다. 앞서 살펴보았던 연결 리스트와 1차원 배열과 같은 선형 자료구조와 달리 트리는 순회에 많은 방법이 존재한다. 노드를 방문하는 순서에 따라 크게 4가지로 분류하여 설명할 예정이다. 1) preorder traversal(전위 순회) 전위 순회의 경우 노드 -> 제일 왼쪽 서브 트리 전위 순회 -> ... -> 제일 오른쪽 서브 트리의 전위 순회 순서로 진행된다. 위의 트리에서 전위 순회를 할 경우 a -> c -> h -> r -> l -> d -> x 의 순서로 노드를 방문하게 된다. 전위 순회는 depth-first traversal(..

Tree 1. Tree의 정의 및 관련 용어 Tree(트리)는 root라고 불리는 지정된 노드가 있고, root를 제외한 모든 노드가 유일한 부모 노드를 가지는 그래프의 일종이다. 관련 용어 - node(노드): 트리의 구성 요소 - edge(간선): 노드와 노드를 연결하는 연결선 - root node: 트리 구조에서 최상위에 존재하는 노드 - internal node(내부 노드): 잎 노드가 아닌 모든 노드 - leaf node(잎 노드): 자식 노드가 없는 노드 - depth(깊이): 자신을 제외한 조상 노드의 개수 - node의 height(높이): (해당 node가 leaf node면 0) 해당 노드의 자식의 height 중 가장 높은 값 + 1 - Tree의 height(높이): 해당 트리의 루..

Array and Linked List 1. Array Array(배열)은 동일한 자료형의 원소들을 순서 있게 저장하는 자료구조이다. 순서 있다는 말이 배열 안의 원소들이 정렬되어야 한다는 의미가 아니다. 배열은 선형 자료구조로 값의 번호가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다. 이를 '순서 있다'라고 표현한 것이고, 각 원소들은 index를 통해 접근 가능하다. 이는 O(1), 즉 상수시간이 걸리므로 원소에 대한 접근이 빠르다는 점이 배열의 장점 중 하나이다. 배열은 일반적으로 정적 할당을 하게 되는데, 이 경우 처음 배열 선언시 지정한 크기만큼만 사용할 수 있다. 만약 지정한 크기보다 더 많은 원소들을 저장할 필요가 있으면, 크기가 더 큰 새로운 배열을 선언 후 기존의 원..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 처음 bfs에 입문했을 때 풀었던 문제다. 상차가 h층만큼 존재하기 때문에 1층만 있는 문제와 다른점은 한 지점에서 이동할 수 있는 방향이다. 2차원에서와 다르게 위, 아래로도 이동할 수 있으므로 총 6가지 방향에 대한 배열을 선언해주었다. 개인적으로 tuple을 사용하면 값에 대한 접근 방식이 귀찮아서 구조체를 더 애용하는 편이다. /* 20200..

문제 링크: 백준/BOJ https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net LIS 문제였다. LIS에 대한 자세한 설명은 아래 글에 있다. https://hellooworld.tistory.com/21 [BOJ] 11053번: 가장 긴 증가하는 부분 수열 문제 링크: 백준/BOJ https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프..