개발일지

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번 풀이법은 옳..

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 (문제 조건..

개념 Floyd Warshall (플로이드 와샬) 알고리즘은 정점과 정점 사이의 최단 거리를 구하는 알고리즘이다. 플로이드 와샬 알고리즘의 특징은 모든 정점 사이의 거리를 구할 수 있다. 최단 경로를 찾을 때 중간에 한번 거쳐서 가는 경로 중 가장 가까운 경로로 업데이트 하면서 모든 정검들의 최단 거리를 구하는 알고리즘이다. 시간 복잡도가 O(V^3)이라는 꽤 오래 걸리는 알고리즘 이지만 모든 정점 사이의 최단 거리를 구할 수 있다. 작동원리 1. 중간 정점 K, 시작 정점 I, 도착 정점 J로 삼중 반복문을 순회한다. 2. distance[i][j]가 distance[i][k] + distance[k][j]보다 크면 경로를 업데이트 한다. -> distance[i][k], distance[k][j]가 ..

개념 LIS(Longest Increasing Subsequence)는 배열이 있을 때 일부 원소를 고른 부분 순열 중, 각 원소가 이전 원소보다 크고 그 순열의 길이가 가장 큰 순열을 LIS라 하고 최장 증가 부분 순열이라고 한다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 변형 문제로 LDS, 최장 감소 부분 순열이 있다. 작동원리 1. LIS라는 List를 만든다. 2. List가 EMPTY거나 제일 마지막 원소가 검사하는 원소보다 작은 경우 List뒤에 추가한다. 3. 검사하는 원소가 List 마지막 원소보다 작은 경우 lower_bound를 사용하여 찾은..

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..

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 ..

개념 충족 가능성 문제 중 하나로써 아래와 같은 형태를 2-SAT 문제라 한다. * 충족 가능성 문제 : Boolean으로 이루어진 식이 있을 때 해당 식이 True인 경우를 찾는 문제 f=(¬x1∨x2)∧(¬x2∨x3)∧(x1∨x3)∧(x3∨x2) 인 경우에 f를 true로 만드는 경우 ¬ : NOT ∨ : OR ∧ : AND 괄호 안의 OR 연산으로 이루어진 것을 절(Clause)이라고 표현하고 AND와 절로 이루어진 식을 CNF(Conjunctive Normal Form)라고 한다. 각 절의 변수의 개수가 2개면 2-SAT이라 하고 N개면 N-SAT이라고 한다. 2개 같은 경우 SCC 알고리즘을 사용하여 쉽게 해결할 수 있지만, 3개 이상의 SAT 문제에서는 NP-Hard 문제이다. 작동원리 1. ..

개념 파란점에서 빨간점까지 탐색한다고 생각할 때 파란점 기준으로 탐색하면 초록색 영역만큼 탐색해야한다. 하지만 파란점과 빨간점을 기준으로 만나는 노란색 점을 탐색하면 탐색해야 하는 불필요한 영역이 줄어든다. 이처럼 기준을 바꿔서 다르게 생각하면 좀 더 연산을 줄일 수 있다. 문제 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수이고, C는 10^9보다 작거나 같은 음이아닌 정수이고. 둘째 줄에 물건의 무게가 주어진다. 무게도 10^9보다 작거나 같은 자연수이다. www.acmicpc.net 코드 #include using namespace std; int n, c; vector input; vector..