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/1963 1963번: 소수 경로 문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 www.acmicpc.net 요즘 왜인지 무기력해서 문제 푸는게 힘들었는데 오랜만에 새로운 문제를 풀었다. 물론 쉬운 문제여서지만 첫 시도에 AC를 받으니 기분이 좋다. 제일 먼저 에라토스테네스의 체를 통해 네 자리수 소수를 모두 표시했다. 또한 비밀번호는 한 번에 한 자리만 변경할 수 있으므로 단계마다 최대 $9^4$가지의 경우의 수가 있는데, 그 경우의 수를 쉽게 구하기 위해 string을 이용했다. 현재..

문제 링크: 백준/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..