목록Problem Solving (6)

개발일지

Algorithm in A..Z - Programmers 트리 트리오 중간값

https://programmers.co.kr/learn/courses/30/lessons/68937 코딩테스트 연습 - 트리 트리오 중간값 5 [[1,5],[2,5],[3,5],[4,5]] 2 programmers.co.kr 접근 1. 트리의 지름을 구할 수 있는 임의의 정점을 찾고 해당 정점과 다른 정점들 사이의 거리 중 2번째로 큰 값을 반환했다. => 12번 테스트 케이스에서 오답. 1번의 반례 위와 같은 그래프는 A-B를 통해 트리의 지금을 구할 수 있다. 해당 경우 A와 다른 정점들 사이의 거리 중 2번째로 큰 값을 반환한 값보다 (A, B, C)의 중간값이 더 크다. => 트리의 지름을 d라고 할 때 정점들 사이의 거리 중 d가 2개 이상 나올 수 있는 경우를 놓쳤기 때문에 1번 풀이법은 옳..
Problem Solving 2021. 9. 8. 10:56
Algorithm in A..Z - Programmers 몸짱 트레이너 라이언의 고민

https://programmers.co.kr/learn/courses/30/lessons/1838 코딩테스트 연습 - 몸짱 트레이너 라이언의 고민 4 5 [[1140,1200],[1150,1200],[1100,1200],[1210,1300],[1220,1280]] 4 programmers.co.kr 접근 그리디하게 최대로 사람이 몰리는 시점에 사람이 몇명인지 파악하고 격자판에 그 사람을 배치하면 된다. => 사람이 많은 시점이 사람이 적은 시점보다 거리가 멀기 때문 1) 규칙성 격자판으로 채울 경우((n*n + 1)/2 == people)인 경우) 거리가 2, 그 이상은 거리가 1이라고 할 수 있다. 그 외에 경우 규칙성을 찾으려 했지만 실패 2) 분할정복 & DP people이 1이면 0 (문제 조건..
Problem Solving 2021. 9. 6. 11:24
Algorithm in A..Z - 백준 3648 아이돌

https://www.acmicpc.net/problem/3648 3648번: 아이돌 각 테스트 케이스에 대해서, 상근이를 포함해, 다음 라운드 진출 목록을 심사위원의 의심 없이 만들 수 있으면 'yes'를, 없으면 'no'를 출력한다. www.acmicpc.net 접근 Tarjan 알고리즘으로 SCC를 구현하면 특성상 하위의 SCC가 먼저 결정된다. 그렇기 때문에 x < ¬x 를 만족하면 x가 참이된다. 상근이가 합격하려면 ¬x가 False면 합격이기 때문에 그래프를 구현할 때 역방향으로 그래프를 구현하여 ¬x가 False가 될 수 있는지 확인한다. (명제의 대우는 동치이기 때문에 가능하다.) 코드 #include using namespace std; constexpr int NONE = -1; int..
Problem Solving 2021. 7. 9. 18:16
Algorithm in A..Z - 백준 4013 ATM

https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 접근 1. SCC를 만들고 각 Component를 새로운 하나의 노드로 생각하고 Component의 구성 요소로 SCC Component간 연결할 수 있는 간선을 구하여 새로운 Graph를 구한다. 2. DP를 사용하여 최대로 인출할 수 있는 금액을 구한다. 코드 #include #include #include #include using namespace std; constexpr ..
Problem Solving 2021. 7. 9. 16:42
Algorithm in A..Z - 백준 2449 전구

www.acmicpc.net/problem/2449 2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 접근 1) dp[left][right][color] 재귀함수로 구간에 특정 color로 색칠하는 방법을 고민했다. => 실패 이유는 모르겠다. 2) dp[left][right] 하지만 구간을 나누고 특정 color로 색칠할 필요가 없었다. => left의 색이나 right의 색으로 칠하는 것이 자명하기 때문이다. dp[left][right] = min(dp[left][i] + dp[i + 1][righ..
Problem Solving 2021. 5. 9. 19:57
Algorithm in A..Z - 백준 3830 교수님은 기다리지 않는다

www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 접근 처음에 Disjoint-Set과 LCA를 고민했다. Disjoint-Set을 고민한 이유는 간선을 추가할(샘플을 측정) 때 Disjoint-Set의 Union연산을 통해 하나의 Set으로 만들고, Find연산으로 쉽게 UNKNOWN인지 알 수 있기 때문이다. LCA를 고민한 이유는 무게차이를 구할 때 공통 조상 노드를 찾아서 거리를 구하면 logN만에 쉽게 거리를 찾을 수 있기..
Problem Solving 2021. 4. 20. 20:30
Prev 1 Next