Processing math: 100%

본문 바로가기

Problem Solving12

백준 20444번 | 색종이와 가위 (C++ 풀이) 문제 https://www.acmicpc.net/problem/20444 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 풀이 사용 알고리즘 : 파라메트릭 서치 시간 복잡도 :

$O(log N)$ 파라메트릭을 활용한 재밌는 문제였습니다. 문제는 굉장히 단순합니다. 색종이를

$N$ 번 잘랐을 때,

$K$ 개의 색종이를 만들어낼 수 있는가? 를 구하면 되죠. 먼저 생각해 볼 만한 점은, 색종이를 잘랐을 때 몇 개의 색종이가 더 생겨나는지를 일반화시킬 수 있을까? 입니다. 이는 그림을 조금 그려보시면 아시겠지만, 가로로

$x$ 번, 세로로

$y$ 번 색종이를 자르면

$(x + 1) * (y + 1)$ 개의 색종이가 생.. 2023. 5. 28.

백준 1719번 | 택배 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1719 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 풀이 사용 알고리즘 : 다익스트라 시간 복잡도 :

$O(N*MlogN + N^3)$ 정점

$V_{1}$ 에서 정점

$V_{2}$ 로 향하는 최단 경로 중, 정점

$V_{1}$ 에서 바로 다음 정점이 어디인지 찾아야 하는 문제입니다. 문제를 풀기 위한 메인 아이디어는 최단 경로 역추적입니다. 최단 거리가 계산되는 시점에서 지나쳤던 정점들을 역추적한 뒤, 실제 최단 경로를 구성하고 두 번째.. 2023. 5. 14.

백준 3079번 | 입국심사 (C++ 풀이) 문제 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 풀이 사용 알고리즘 : 파라메트릭 서치 시간 복잡도 :

$O(N * log(M * min(T_{k})))$ 파라메트릭 서치로 풀 수 있는 문제였습니다. 이 문제에서의 큰 문제점은

$M$ 의 상한이

$10^{9}$ 이라는 점입니다. 완전 탐색 시 발생하는 시간은 대략

$O(N^{M})$ 정도일 테고, 당연히 터집니다.

$M$ 의 상한이 너무 크니, 이를 로그 시간으로 최적화시킬 필요가.. 2023. 4. 16.

백준 16724번 | 피리 부는 사나이 (C++ 풀이) 문제 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 풀이 사용 알고리즘 : Union-Find or DFS 문제를 잘 해석해 보면, SAFE-ZONE의 최소 개수는 결국 그래프의 컴포넌트 개수와 같다는 점을 이용해서 풀 수 있습니다. 단, 사이클이 존재하는 단방향 그래프이기 때문에 추가적인 생각이 필요했던 문제였습니다. 컴포넌트의 개수를 구하는 풀이는 Union-Find 나 DFS 정도가 있을 것 같고, 이.. 2023. 1. 25.

백준 16946번 | 벽 부수고 이동하기 4 (C++ 풀이) 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 사용 알고리즘 : DFS 시간 복잡도 : O(N^2) 문제의 해석은 어렵지 않으나, 시간 복잡도를 잘 생각해보며 풀어야합니다. Naive한 풀이는 이렇습니다.모든 벽인 칸에 대해서 BFS를 돌려 이동할 수 있는 칸의 개수를 구해주면 됩니다. 하지만 시간 복잡도가 너무 크죠.단순히 BFS 한 번 돌리는 데 발생하는 시간은 O(N^2)이 될 겁니다. 여기서 문제는 매 .. 2022. 10. 25.

이전 1 2 3 다음

티스토리툴바