poksul_log

관련 알고리즘 : 누적합, 이분탐색 문제 링크 : https://www.acmicpc.net/problem/2141 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 문제 풀이 문제 조건을 살펴보면, 수직선상 N개 마을 i번째 마을 위치 : X[i] i번째 마을 사람 수 : A[i] |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 가능한 경우가 여러 가지 => 더 작은 위치 출력 ▶ 우체국 ..

관련 알고리즘 : 투 포인터, 슬라이딩 윈도우 문제 링크 : https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 문제 풀이 문제의 길이가 길기 때문에 조건들을 정리해보면, 원래의 회전 초밥 계산법과 달리, 벨트의 임의의 한 위치부터 k개의 접시 연속해서 먹기 => 할인된 정액 가격 제공 초밥 종류 하나가 쓰인 쿠폰 발행, 상기 연속해서 먹기 이벤트 진행 시 => 해당 초밥 하나 추가로 무료제공. 해당 초..

관련 알고리즘 : 다익스트라(Dijkstra) 문제 링크 : https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 풀이 ▶ 문제 조건 정점의 개수 V (1 e >> start; for(int i = 0; i > u >> v >> w; vertex[u].push_back(make_pair(v, w)); } for(int i = 1; i cost + next..

관련 알고리즘 : 유니온 파인드 문제 링크 : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 해결 방법 동혁이가 여행 계획을 위해 이동해야 하는 최단 거리를 구하는 것이 아니라, 같은 곳을 여러 번 경유한다 해도 도시들을 순서에 따라 여행할 수 있을 지에 대한 여부를 구하는 것이기 때문에 유니온 파인드를 사용하였다. 같은 그래프에 여행 계획을 세운 도시들이 모두 포함되어 있다면 경유하여 갈 수 여행할 수 있다는 뜻이므로 yes를, 도시들 중 ..

관련 알고리즘 : 그리디, 정렬 문제 링크 : https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 해결 과정 문제의 조건을 보면, 크레인에 무게 제한 G 존재 (G m; // 크레인 입력 받기 for (int i = 0; i > num; c.push_back(num); } cin >> n; // 박스 입력 받기 for (int i = 0; i > num; b.push_ba..

관련 알고리즘 : 플로이드 와샬 문제 링크 : https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 해결 과정 문제의 조건들이 눈에 잘 들어오지 않아 정리를 해 보면, 직접 연결 일방통행 통로보다 시간이 '덜' 걸리는 경유 노선 존재 가능 파티장 크기 N(5 손님이 현재 위치한 파티장 번호/ 다음 파티 열리는 파티장 번호 / 다음 파티가 열리기까지 남은 시간 즉, 파티장(정점)에서 다른 파티장(또다른 정점)으로 이..

관련 알고리즘 : 브루트포스, 재귀, dfs, 비트마스킹 비트마스킹으로는 못 풀어봐서 다음에 비트마스킹으로도 풀어봐야겠다. 문제 링크 : https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 해결 과정 김지민 선생님이 k 개의 글자를 학생들에게 가르치고, 학생들은 k개의 글자만 읽을 수 있다. 그런데 남극의 모든 단어들은 "anta"로 시작하고, "tica"로 끝나기 때문에 학생들이 남극의 단어들을 읽을 수 있으려면 a, c, i, n, t ..

관련 알고리즘 : 재귀, DP 문제 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 해결 과정 문제를 보면, 어떤 아이디어를 SNS에서 퍼뜨리고자 할 때 얼리 아답터가 아닌 사람은 모든 친구가 얼리 어답터여야 아이디어를 받아들임 얼리 어답터인 사람은 친구가 얼리 어답터인지 여부에 관계없이 아이디어를 받아들임 즉, 얼리 어답터가 X인 사람 => 연결된 친구들이 모두 얼리 어답터----------- 얼리 ..

관련 알고리즘 : 그리디, 정렬 문제 링크 : https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 해결 과정 문제에서 제공한 예시를 토대로 생각해보면, 책의 위치들을 {-39, -37, -29, -28, -6, 2, 11} 순으로 오름차순 정리할 수 있다. 어차피 모든 책들을 다 제자리에 갖다 놓아야 하고, 마지막 책은 놓고 나서 다시 0으로 되돌아올 필요가 없기 때문에 가장 먼 거리에 있는 책을 제일 마지막에 놓는 것이 이동거리를 줄일 수 있다. 예시..

관련 알고리즘 : DP, 배낭(Knapsack), 재귀 문제 링크 : https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 해결 과정 문제에서 주어졌던 예제를 통해 생각해보면, 1g, 4g짜리 추 2개가 주어진 경우 잴 수 있는 구슬의 무게는 1g과 4g을 같이 놓았을 때 무게 = 5g 1g과 구슬의 무게 = 4g일 때, 구슬의 무게 = 4g - 1g = 3g 추를 한개만 놓았을 경우, 각 1g과 4g 이렇게 3가지 경우로 나눌 수 있다. 정리하면, ..