분류 전체보기
-
BOJ 1395 스위치알고리즘/세그먼트 트리 2021. 3. 22. 10:31
www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 레이지 프로퍼게이션을 공부한지 한달 조금 안되었다. 구간합을 구하는 것에 더해서 구간 업데이트까지 가능하다고?? 정말 대단한 알고리즘이다. 하여간 이걸 연습해야 하는데.. 레이지 프로퍼게이션에는 오일러 경로 테크닉이 자주 따라오는 거 같다. 이건 모르는거니 필요없는 것중에 연습을 좀 하고 있는데 굉장히 멋있는 문제인것 같아서 풀어봤다. 보통 레이지프로퍼게이션 입문은 구간합..
-
스코페 2021 1차코테 후기일기장 2021. 3. 20. 18:30
scofe2021.goorm.io/assessment/25665/startup-coding-festival-2021 Startup Coding Festival 2021 - 구름DEVTH 대한민국 최초로 진행되는 'Startup Coding Festival 2021' 분야별 최고의 스타트업들이 모여 코딩 페스티벌을 개최합니다. 로켓성장하고 있는 스타트업의 개발 문화를 경험할 수 있는 이번 축제에 여러 scofe2021.goorm.io ... 신청해놓고 잊어버리고 있었는데 어젯밤에 메일을 읽다가 참가하라는 메일을 발견했다. 대회는 6문제 4시간이고 환경테스트 문제가 두문제였는데 하나를 못풀었다(...) 유명한 스타트업에서 진행하는 대회이니 그만큼 문제가 어려울거라고 생각하며 잠에 들었다. 그런데 막상 까보니..
-
BOJ 7812 중앙 트리알고리즘/트리 2021. 3. 18. 20:55
www.acmicpc.net/problem/7812 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net 굉장히 재밌는 문제같아서 언젠간 풀어보려 했는데 이번에 풀게 되었다. 그냥 모든점에서 다익스트라를 돌리고 싶은 생각이 드는데, 생각해보면 그래프라 다익말고 dfs로도 최단거리가 나온다. 그런데 dfs 시간복잡도가 O(v)라서 v개의 정점에서 모두 dfs를 한번씩 돌려보면 O(v^2) = 시간초과 이다. 당연히 다른 방법이 필요하다. 이런 스타일의 문제는 대부분 dfs를 활용하면서, 인접한 ..
-
BOJ 14570 나무 위의 구슬알고리즘/트리 2021. 3. 18. 08:48
www.acmicpc.net/problem/14570 14570번: 나무 위의 구슬 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어 www.acmicpc.net 이것도 처음 봤을 때는 못풀었다. 아니, 각 상황에 따라서 구슬이 내려가는 위치가 다른데, k가 10^18이라고? 분할정복도 아니고, 트리dp인가?? 하다가 못풀었던 문제인데 이제보니 이렇게 쉬울수가 없다... 규칙을 잘 생각해 보면 답이 나온다. 각 노드에서 구슬은 왼쪽 또는 오른쪽을 선택한다. 이 규칙에 의해서, 모든 상황에서 자식의 구슬개수는 1. 양쪽 자식의 자식의 구슬개수가 동일하거나 2. 왼쪽..
-
BOJ 2250 트리의 높이와 너비알고리즘/트리 2021. 3. 17. 19:01
www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 문제를 본 지는 좀 되었는데, 그당시에 뭔소린지 모르겠어서 못 풀었던 문제이다. 이번에 한번 더 보았는데, 너무 쉬운 문제였다. 왼쪽의 숫자는 노드의 깊이이고, 아래의 숫자는 inorder탐색을 했을때의 방문순서이다!! 따라서 이 문제는 그냥 노드의 깊이마다 inorder탐색을 제일 처음 만난 친구와 제일 늦게 만난 친구의 탐색순서의 차이를 출력하면 되는 문제이다. #include using ..
-
BOJ 12767 Ceiling Function알고리즘/트리 2021. 3. 17. 18:06
www.acmicpc.net/problem/12767 12767번: Ceiling Function Advanced Ceiling Manufacturers (ACM) is analyzing the properties of its new series of Incredibly Collapse-Proof Ceilings (ICPCs). An ICPC consists of n layers of material, each with a different value of collapse resistance (measured as a positive integer). www.acmicpc.net 영어 울렁증이 있는 나에게는 너무나 어려운 문제였다. 대충 트리를 구성하는 문제인건 알았는데, 트리 구성 조건이 다음과 같았다..