9372번: 상근이의 여행

9372번: 상근이의 여행사용 언어: C++ 풀이모든 도시는 연결되어있고, 현재 위치가 중요하지도 않으므로, 그냥 간선의 수 - 1이 답이다.#include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while (T--) { int N, M; cin >> N >> M; for (int i = 0; i > a >> b; } // 모든 도시는 항상 연결되어있음 // -> 최소 간선 수는 항상 N-1 cout

6549번: 히스토그램에서 가장 큰 직사각형 (BOJ C/C++)

6549번: 히스토그램에서 가장 큰 직사각형 사용 언어: C++ 문제 히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다. 히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오. 입력 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사..

1991번: 트리 순회 (BOJ C/C++)

1991번: 트리 순회 사용 언어: C 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 ..

트리

트리는 지금까지 배운 자료구조(스택, 큐, 덱)과는 달리 비선형 구조다. 이러한 개념을 설명한 적이 없지만 스택, 큐, 덱 등은 선형 구조다. 사실 이미 비선형 구조를 가진 문제를 푼 적이 몇 번 있는데, 그것은 그래프 문제들이었다. 그래프 설명도 따로 했어야 했는데... 까먹었다. 사실 트리도 설명하기 귀찮아서.... 정말 간단하게 소개만 하자면 트리는 부모 노드와 자식 노드로 이루어져있다. 더 자세한 개념과 용어는 대부분 부모 노드와 자식 노드의 관계에서 파생된다. 간단한 트리 구현 코드는 '1991번: 트리 순회'에서 썼다. 연결리스트로 구현을 했다. 트리를 배열로 구현하면 힙(Heap)을 구현할 수도 있다.

10816번: 숫자 카드 2

10816번: 숫자 카드 2(BOJ C/C++) 사용 언어: C 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져..