분류 전체보기
-
JUNGOL...130일지 2021. 9. 4. 01:18
Intermediate_Coder/자료구조/히스토그램 문제 히스토그램이란 보통 분포의 정도를 알기 위해 사각형의 서열을 기준선에 맞춰 늘어놓은 다각형을 말한다. 만약 임의의 수열이 2, 1, 4, 5, 1, 3, 3일 경우 사각형의 너비를 1로 맞추어 히스토그램으로 만들면 다음과 같다. 우리가 하고자 하는 것은 임의의 히스토그램이 주어졌을 때 히스토그램 내에서 사각형으로 이루어진 가장 큰 면적의 크기를 알고자 한다. 왼쪽 의 히스토그램에서 가장 큰 사각형의 영역은 오른쪽에 밑줄이 쳐진 영역과 같다 입력 형식 입력 첫 번째는 히스토그램을 이루는 사각형의 개수 n(n≤100,000)이 입력되고 그 뒤로 히스토그램을 이루는 사각형의 높이가 순서대로 n개 입력이 된다. 사각형의 높이 k는 0 ≤ k ≤ 1,00..
-
JUNGOL...129일지 2021. 9. 3. 10:29
Intermediate_Coder/자료구조/탑 문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에..
-
JUNGOL...128일지 2021. 9. 2. 09:36
Intermediate_Coder/자료구조/빌딩 문제 N개의 빌딩이 있다. 빌딩은 1번부터 N번까지 번호가 붙어 있다. 빌딩은 X좌표 상에 위치해 있으며 i번 빌딩은 i좌표 상에 위치해 있다. 그리고 각 빌딩은 Hi 만큼의 높이를 가지고 있다. i < j 이고 Hi < Hj 일 경우, i번 빌딩에서 j번 빌딩을 볼 수 있다. 각 빌딩에서 현재 빌딩의 좌표보다 오른쪽에 있는 빌딩을 보고자 할 때, 가장 가까이 보이는 빌딩이 어딘지 찾는 프로그램을 작성하라. 입력 형식 입력의 첫 번째 줄에는 N이 입력된다(1≤N≤100,000). 그리고 그 다음 줄부터는 Hi(1≤Hi≤1,000,000)가 순서대로 한 줄에 하나씩 입력된다. 출력 형식 총 N개의 줄에 출력을 하게 되며, i번째 줄에는 i번 빌딩에서 보이는 ..
-
알고리즘...45일지 2021. 9. 2. 09:31
이진 탐색 트리 출력 이진 탐색 트리 구현 후 테스트를 위한 출력 함수를 만든다. 이때 다음과 같은 정보가 필요하다. 노드의 간격과 왼쪽 공백에 필요한 정보 루트 기준으로 최대 깊이를 파악하여 깊이에 따라 간격을 조절한다. 노드의 출력 순서 라인별로 출력이 되어야 하므로 BFS를 이용하여 출력을 진행한다. 깊이 파악을 위한 함수 struct BinarySearchNode { int GetMaxDepth() { int leftMaxDepth{ left != nullptr ? left->GetMaxDepth() : 0 }; int rightMaxDpth{ right != nullptr ? right->GetMaxDepth() : 0 }; return (leftMaxDepth > rightMaxDpth ? l..
-
JUNGOL...127일지 2021. 9. 1. 00:02
Intermediate_Coder/자료구조/불쾌한 날(Bad Hair Day) 문제 농부 시현이의 N(1≤N≤80,000)마리의 소들은 "bad hair day"를 맞이하였다. 각 소들이 자신들의 촌스런 머리 모양을 부끄러워 하자, 시현이는 소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지를 알고자 했다. i번째 소들은 키가 hi(1≤hi≤1,000,000,000) 이며, 동쪽(오른쪽)을 바라보고 서있다. 따라서, i번째 소는 자신의 앞 ( i+1, i+2,...)의 소들의 머리 모양만 볼 수 있으며, 앞에 자신의 키보다 작은 소들만 볼 수 있다. 다음 예제를 고려해보자: ()의 숫자는 키를 나타낸다. 1번 소는 2,3,4번소의 머리 모양을 볼 수 있다. 2번 소는 어떤 소의 머리 모양도 볼 수 없..
-
JUNGOL...126일지 2021. 8. 31. 02:14
Intermediate_Coder/자료구조/불쾌한 날(Bad Hair Day) 문제 농부 시현이의 N(1≤N≤80,000)마리의 소들은 "bad hair day"를 맞이하였다. 각 소들이 자신들의 촌스런 머리 모양을 부끄러워 하자, 시현이는 소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지를 알고자 했다. i번째 소들은 키가 hi(1≤hi≤1,000,000,000) 이며, 동쪽(오른쪽)을 바라보고 서있다. 따라서, i번째 소는 자신의 앞 ( i+1, i+2,...)의 소들의 머리 모양만 볼 수 있으며, 앞에 자신의 키보다 작은 소들만 볼 수 있다. 다음 예제를 고려해보자: ()의 숫자는 키를 나타낸다. 1번 소는 2,3,4번소의 머리 모양을 볼 수 있다. 2번 소는 어떤 소의 머리 모양도 볼 수 없..
-
알고리즘...44일지 2021. 8. 31. 01:28
AVL 트리 구현 AVLTree.h #pragma once #include "../Common.h" /// /// AVL 트리에 사용할 노드 /// struct AVLNode { AVLNode() : data{ 0 }, bf{ 0 }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} AVLNode(int data) : data{ data }, bf{ 0 }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} void Clear() { data = 0; parent = nullptr; left = nullptr; right = nullptr; } bool HasBalanceProblem() { return..