넘치게 채우기

https://www.acmicpc.net/problem/1918BOJ - 후위 표기식문제 유형: 스택, 문자열 처리, 트리문제 난이도: Gold II시간 제한: 2초메모리 제한: 128MB 문제수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤..

https://www.acmicpc.net/problem/1167BOJ - 트리의 지름문제 유형: 최단 거리, 다익스트라, 트리, 그래프, 트리의 지름문제 난이도: Gold II시간 제한: 2초메모리 제한: 512MB 문제트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 ..

https://www.acmicpc.net/problem/5639BOJ - 이진 검색 트리문제 유형: 트리, 재귀, dfs, 이진탐색트리(BST)문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, ..

https://www.acmicpc.net/problem/1991BOJ - 트리 순회문제 유형: DFS, 트리, 재귀문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.예를 들어 위와 같은 이진 트리가 입력되면,전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 입력첫째 줄에는 이진 트리의 노드의 개..

https://leetcode.com/problems/cousins-in-binary-tree-ii/description/?envType=daily-question&envId=2024-10-23leetcode - Cousins in Binary Tree II문제 유형: 트리, bfs문제 난이도: Medium 문제Given the root of a binary tree, replace the value of each node in the tree with the sum of all its cousins' values.Two nodes of a binary tree are cousins if they have the same depth with different parents.Return the root o..

https://www.acmicpc.net/problem/11725BOJ - 트리의 부모 찾기문제 유형: 트리, bfs문제 난이도: Silver II시간 제한: 1초메모리 제한: 256MB 문제루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 풀이연결 관계만 주어지므로, 정확한 계층 관계를 알 수는 없다.그래서, bfs를 하면서 방문처리를 하며 부모자식 관계를 지어주어야 한다.1부터 bfs를 시작하면..

https://www.acmicpc.net/problem/6514BOJ - Expressions문제 유형: 스택, 큐, 트리문제 난이도: Silver I시간 제한: 1초메모리 제한: 128MB 문제Arithmetic expressions are usually written with the operators in between the two operands (which is called infix notation). For example, (x+y)*(z-w) is an arithmetic expression in infix notation. However, it is easier to write a program to evaluate an expression if the expression is writ..

https://www.acmicpc.net/problem/25601BOJ - 자바의 형변환문제 유형 : 해시, 그래프, 트리문제 난이도 : Silver I시간 제한: 2초메모리 제한: 512MB 문제자바의 클래스끼리는 상속을 통해 자신의 기능 일부를 다른 클래스에게 이식할 수 있다. 여기서 상속을 받은 클래스는 자식 클래스, 상속을 한 클래스는 부모 클래스가 된다. 클래스를 이용해서 만든 객체는 다른 클래스로 형태를 변환할 수 있는데, 이를 형변환(Casting)이라고 한다. 만약 자식 클래스에서 부모 클래스로 변환한다면 업캐스팅(Upcasting), 부모 클래스에서 자식 클래스로 변환한다면 다운캐스팅(Downcasting) 이라고 부른다. 즉, 자식 클래스와 부모 클래스 관계에 놓여있다면 형변환이 가능..

https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/description/?envType=daily-question&envId=2024-09-22leetcode - K-th Smallest in Lexicographical Order문제 유형 : 트리, dfs, 수학문제 난이도 : Hard 문제Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n]. 두 개의 정수 n과 k가 주어진다. 범위 [1,n]에서 사전순으로 k번째로 작은 정수를 반환하시오. 풀이순차적으로 k개를 찾는 것은 느리다.대신, 점프를 할 필요가 있다..

https://leetcode.com/problems/find-the-maximum-sum-of-node-values/description/leetcode - Find the Maximum Sum of Node Values문제 유형 : 수학, 비트마스킹, 트리문제 난이도 : Hard 문제There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 0-indexed 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree. You are al..