전체 글

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net [문제] [풀이] 탐색 + 다이나믹프로그래밍이 합쳐진 기초문제이다. dfs를 한번 수행하여 leaf 노드에서 부터 재귀로 호출한 dfs가 종료 되기 전에 정점의 수를 메모이제이션 기법으로 기록해두고 , 쿼리가 호출될 때 dp 테이블 값을 바로 반환하는 것. 특정 노드 i의 자식정점의 갯수가 아니라 특정노드 i 를 포함한 정점을 반환해야..

https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net [문제] [풀이] 굉장히 어려웠다 .. 뚝배기 갈리는 문제다. 우선 , 특정 i번째 노드 입장에서 생각해보자. i 입장에서는 2가지 경우가 있다. 1. i 노드와 i 의 자식들간에 시너지를 맺을 때. 2. i 노드가 이미 부모노드와 시너지가 맺혀 있을때. 그렇기 때문에 특정 i 번노드 입장에서는 시너지로 묶여있는지 아닌지에 대한 여부에 따라서 i 번 까지의 시너지 총..

https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net [문제] [풀이] 일단 알아야 할 것은 상사는 아래 직원들 중에 가장 전파가 오래걸리는 직원한테 먼저 전파해야함. 가장 오래걸리는 기준은 직접 탐색하면서 찾아야 하는데 자식수가 많거나 깊이가 깊다고해서 오래 걸리는것은 아님. 탐색할 때 가장 오래걸리는 부하직원을 정렬하고 그 부하직원들에게 차례대로 카운트를 붙여 늘려준 합산이 (상사의 부하직원이 많을 수 있기때문) 상사가 선택할 직원이라는 것. 가령 ,..

https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net [문제] [풀이] 물이 찰 예정엔 고슴도치가 이동불가 => 물 먼저 처리할 것. 즉 , 탐색을 하기위해 우선순위를 1. 진행일수 2. 처리순서 로 하기위해서 우선순위큐를 이용한 BFS로 탐색하였다. 물탐색 : map이 '.' 이거나 'S' 인 경우에만 진행후 , '*'로 마킹. 고슴도치탐색 : map이 '.' 이거나 'D' 인 경우에만 진행후 'S'로 마킹. 1 2 3 4 5 6 7 8 9 10 11 12 1..

https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net [문제] [풀이] 1. 다익스트라를 돌려서 N번 노드까지의 최단거리를 구하고 , 경로를 구한다. 2. 구한 경로의 edge를 하나씩 빼면서 다익스트라를 경로의 수 만큼 다시 돌린다. 3. 늘어난 시간 중 가장 긴 거리와 1번에서 구한 최단거리의 차이를 반환하면 끝. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 ..

https://programmers.co.kr/learn/courses/30/lessons/43164# 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr [문제] [풀이] 그래프 탐색문제이다. 처음엔 TreeMap과 같이 티켓과 정보를 한번에 저장해서 하려했으나 , 키중복에서 꼬이거나 다중 Map을 써야하는 상황이 나오는 등 쉽지 않았기때문에 티켓자체를 방문지점으로 써버렷다. 그래서 티켓의 사용여부를 boolean 타입의 visit 배열로 사용했고 그냥 완전탐색 + 백트래킹으로..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net [문제] [풀이] 문제의 조건을 만족하기위해선 데드라인을 만족과 동시에 컵라면을 제일 많이 받을 수 있는 쪽으로 해야한다. 현재 경과 일을 i 라고하면 , i 이상의 데드라인 문제들을 풀 수 있지만 i 이전의 문제들을 풀 수 없다. 즉 , i 이상의 데드라인 문제들을 보면서 컵라면이 제일 많은 순으로 가져가야함. 경과일마다 처리해야하는 문제들을 1부터 차례대로 보기위해 데드라인순으로 우선 오름차순정렬을 한..

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net [문제] [풀이] 정렬 , 그리디 문제이다. 책을 제자리에 놓기위해 그 만큼 전진을 해야하는데 , 최대 M권을 같이 들고갈수 있기 때문에 기준점으로부터 제일 멀리있는 지점을 고르면 m-1개는 가는길에 갖다 놓을 수 있기때문에 우선 제일 멀리있는 지점을 찾아야 한다. 그러나 제일 마지막에 놓는 책은 다시 돌아올 필요가 없기 때문에 편도로 한번만 가고 나머지는 왕복처리하면 끝. 우선순위 큐를이용해서 양수면..