본문 바로가기

Problem Solving

 (145)
백준 4008 - 특공대 (C++) 문제 문제 링크 BOJ 4008 - 특공대 문제 요약 병사 $N$명의 전투력과 조정 전투력 등식 계수가 주어진다. 문제에 정의된 전투력 측정 방식을 따를 때, $n$명의 병사들에 대해 얻을 수 있는 최대 조정 전투력을 구해보자. 제한 TL : $1$ sec, ML : $64$ MB $1 ≤ N ≤ 1,000,000$ $-5 ≤ a ≤ -1$ $|b| ≤ 10,000,000$ $|c| ≤ 30,000,000$ $1 ≤ xi ≤ 100$ 알고리즘 분류 다이나믹 프로그래밍(dp) 볼록 껍질을 이용한 최적화(convex hull trick) 풀이 CHT 대표 문제로 꼽히는 문제다. 물론 나도 CHT 태그를 타고 들어 왔지만 처음 내 반응은 "이게 왜 CHT?" 였다. 우선 연속 부분 수열 합을 고려해야 하므로 ..
백준 14948 - 군대 탈출하기 (C++) 문제 문제 링크 BOJ 14948 - 군대 탈출하기 문제 요약 $N*M$의 맵이 주어지고 $(1, 1)$에서 $(N, M)$으로 이동하려 한다. 최소 각 칸에 적힌 레벨만큼은 되어야 해당 칸을 지날 수 있고 딱 한 번 한 칸을 건너뛸 수 있을 때, 갖춰야 하는 최소 레벨을 구해보자. 제한 TL : $1$ sec, ML : $256$ MB $1 ≤ n, m ≤ 100$ $0 ≤ k ≤ 10^9$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 너비 우선 탐색(bfs) 이분 탐색(binary search) 매개 변수 탐색(parametric search) 풀이 문제 내용과 $k$의 범위만 봐도 파라매트릭 냄새가 솔솔 난다. 다음과 같이 결정 문제를 정의해보자. $f(x)$..
백준 13502 - 단어퍼즐 2 (C++) 문제 문제 링크 BOJ 13502 - 단어퍼즐 2 문제 요약 $5*5$의 맵과 미리 기록된 dict가 주어진다. dict에 속한 단어 중 맵에서 8방 탐색을 통해 찾을 수 있는 단어의 수를 구해보자. 제한 TL : $2$ sec, ML : $128$ MB 알고리즘 분류 자료 구조(data structures) 문자열(string) 트리(trees) 트라이(trie) 그래프 이론(graphs) 그래프 탐색(graph_traversal) 깊이 우선 탐색(dfs) 백트래킹(backtracking) 런타임 전의 전처리(precomputation) 풀이 문제 자체는 어렵지 않다. dict에 속한 단어들을 트라이에 다 때려 박은 다음 맵에서 백트래킹으로 찾아지는 단어의 수를 구해주면 된다. 처음에 dict를 str..
백준 27114 - 조교의 맹연습 (C++) 문제 문제 링크 BOJ 27114 - 조교의 맹연습 문제 요약 $3$가지 행동에 대한 에너지 소모량과 사용하고자 하는 에너지양이 주어진다. 정확히 사용하고자 하는 에너지양을 모두 소모하려할 때, 처음 바라보는 방향으로 돌아오는 행동 수행 횟수의 최솟값을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ A, B, C, K ≤ 1,000,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 결국 매 순간마다 표현되는 상태는 두가지다. 남은(소모해야 하는) 에너지양과 바라보고 있는 방향. 이에 따라 다음과 같은 정의를 내려보자. $dp[i][j]$ : 남은 에너지양이 $i$이고 $j$의 방향을 바라보고 있을 때 제식 수행 횟수의 최솟값. 각 방향을 기준으로 $3$가지의 변화를 고..
백준 2550 - 전구 (C++) 문제 문제 링크 BOJ 2550 - 전구 문제 요약 $N$개의 스위치 및 전구의 연결 정보가 주어진다. 이때 교차하지 않게 가장 많은 전구를 켤 수 있는 경우를 추적해보자. 제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N ≤ 10,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 가장 긴 증가하는 부분 수열 O(NlogN) 풀이 그림만 봐도 알겠지만, 기본적인 lis 역추적 문제이다. $N$의 범위에 따라 $O(NlogN)$ 솔루션이 강제되지 않기 때문에, 굳이 이분 탐색을 이용하지 않아도 널널해 보인다. 전체 코드 12345678910111213141516171819202122232425262728#include#define N 10001using namespace std; vect..
백준 5467 - Type Printer (C++) 문제 문제 링크 BOJ 5467 - Type Printer 문제 요약 출력해야 하는 $N$개의 단어 목록이 주어진다. 프린터로 $3$가지의 작업을 수행할 수 있을 때, 주어진 단어 목록을 모두 출력하는 최소 작업 경로를 추적해보자. 제한 TL : $1$ sec, ML : $128$ MB $1 ≤ N ≤ 25,000$ 각 단어는 소문자로만 구성되며 중복이 없고 20자를 넘지 않는다. 알고리즘 분류 자료 구조(data structures) 문자열(string) 트리(trees) 트라이(trie) 정렬(sorting) 풀이 결국 가장 긴 단어를 맨 마지막으로 출력해야 한다는 것은 자명하다. 단어들을 순회함에 있어서 트라이에 $N$개의 단어들을 모두 올린 뒤 이어진 max_size순으로 순회하면 될 듯 하다. ..
백준 20440 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 (C++) 문제 문제 링크 BOJ 20440 - 🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 1 문제 요약 $N$개의 모기 출입 정보가 주어진다. 이때, 모기가 가장 많이 있는 시간대의 모기 마릿수와 그 연속 구간을 구해보자. 제한 TL : $1$ sec, ML : $1024$ MB $1 ≤ N ≤ 1,000,000$ $0 ≤ T_E < T_X ≤ 2,100,000,000$ 알고리즘 분류 누적 합(prefix_sum) 정렬(sorting) 값 / 좌표 압축(coordinate_compression) 풀이 수직선 상에 $N$번의 업데이트 후 최종 상태 출력.. 전형적인 imos법의 형태이다. 그러나 주어지는 좌표 범위가 $N$에 비해 난감하다. 어차피 존재할 수 있는 좌표 상태는 많아봐야 $2,0..
백준 16947 - 서울 지하철 2호선 (C++) 문제 문제 링크 BOJ 16947 - 서울 지하철 2호선 문제 요약 $N$개의 정점과 간선으로 이루어진 그래프가 주어진다. 임의의 두 역 사이에 경로가 항상 존재할 때, 각 노드로부터 사이클 형상 까지의 거리를 구해보자. 제한 TL : $2$ sec, ML : $512$ MB $3 ≤ N ≤ 3,000$ 알고리즘 분류 그래프 이론(graphs) 그래프 탐색(graph_traversal) 깊이 우선 탐색(dfs) 너비 우선 탐색(bfs) 풀이 $N$개의 간선으로 이루어진 그래프에서 사이클을 떼네어볼 수 있는가를 묻는 교육적인 문제이다. 나는 개인적으로 indegree를 이용한 bfs를 이용해 사이클을 분리하는 방식을 선호한다. 다음의 과정을 보자. 간선 정보를 입력 받으면서 indegree를 카운트 해주면..

티스토리툴바