본문 바로가기

Algorithm98

BOJ 2250 - 트리의 높이와 너비(트리 순회방식) www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net - 트리 구현과 순회 방식을 잘 알고 있어야 풀 수 있는 문제이다. - 트리의 노드를 맨 왼쪽 열부터 순서대로 읽어야 각 레벨의 너비를 알 수 있다(in-order traversal). 이는 DFS 탐색으로 구현할 수 있다. 같은 레벨의 노드들을 담는 가변벡터를 선언해서 번호가 가장 작은 왼쪽 노드와 가장 큰 오른쪽 노드 간의 너비를 구한다. #include #include #include #.. 2021. 4. 12.
BOJ 11437 - LCA(Tree) www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net - 트리에서 제시된 노드 2개 간의 가장 가까운 공통 조상을 찾는 알고리즘을 LCA 알고리즘 라고 부른다. (lowest common ancestor) 딱히 이진트리가 아니므로, 가변벡터의 트리배열을 선언하고 여기에 노드들을 담는다. 해당 노드의 레벨, 부모 정보를 담을 벡터를 선언하고, 각각의 노드의 부모를 찾기 위한 bfs탐색을 위해 방문여부 체크벡터도 선언한다. - LCA 알고리즘은 생각보다 간단한데.. 2021. 4. 12.
BOJ 2019 - 순회강연(Greedy) www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net - 짧게 걸리면서 페이가 높은 순으로 강연을 해야 가장 높은 수익을 올릴 수 있다. 현재 소요기간을 카운트하기 위해서 우선순위 큐를 이용해서 시행한 강연만 페이에 대한 최대힙에 남도록 로직을 구현했다. #include #include #include #include using namespace std; int n, ans; vector a; priority_queue pq; .. 2021. 4. 12.
BOJ 16434 - 드래곤 앤 던전(시뮬레이션, binary search) www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net - 예제 입력과 출력값을 통해서 대충 이분탐색인 것은 파악할 수 있었는데, 방타입이 몬스터 방인 경우를 구현하기가 참 햇깔리는 문제였다. - 용사가 먼저 몬스터에게 선공을 한다는 것을 유의해서 구현을 해야된다. #include #include #include #include using namespace std; #define ull unsig.. 2021. 4. 11.

티스토리툴바