전체 글
-
[BOJ] 13549 숨바꼭질 3PS/BOJ 2020. 7. 16. 18:20
https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 알고리즘: BFS 시간복잡도: O(V+E) BOJ 1697 숨바꼭질의 다른 버전이다. https://moon323.tistory.com/16 X*2 연산은 1초가 아닌 0초가 걸린다. -> 그냥 X*2 연산은 시간을 증가시키지 않으면 된다. 더보기 #include #include using namespace std; int N, K, h, c[100001];..
-
[BOJ] 12851 숨바꼭질 2PS/BOJ 2020. 7. 16. 18:15
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 � www.acmicpc.net 알고리즘: DP, BFS 시간복잡도: O(V+E) BOJ 1697 숨바꼭질의 업그레이드 버전이다. https://moon323.tistory.com/16 N에서 K까지 이동하는데 걸리는 최단 시간뿐만 아니라 그 방법의 가짓수도 구해야한다. 접근: 1. 가짓수 구하기 -> 가짓수 구하는 문제이므로 Dynamic을 이용하면 된다. D[i]: i 좌표까지 가는 ..
-
[BOJ] 1697 숨바꼭질PS/BOJ 2020. 7. 16. 18:04
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 알고리즘: BFS 시간복잡도: O(V+E) -> E K까지 최단 거리로 위치 이동 2. 한정된 이동 경로 (X-1, X+1, X*2) -> 이 두가지 조건을 통해 BFS를 사용하면 된다는 것을 알 수 있다. N~K까지 각 위치를 정점으로 보고 X-1, X+1, X*2 연산을 간선으로 생각하면 된다. 참고) 이동한 점이 10^5 보다 크면 고려할 필요가 없다. 이게 문제의..
-
[BOJ] 1647 도시 분할 계획PS/BOJ 2020. 7. 16. 17:03
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 알고리즘: MST (Kruskal) 시간복잡도: O(MlogM) 접근: 1. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다. 2. 그 경로의 합은 최소가 되야 한다. 3. 분리된 마을은 2개 -> 1, 2번 조건을 통해 이 문제는 MST의 변형 문제라는 것을 알 수 있다. 다만 기존 MST 문제와 차이점은 두 마을로 만들어야 한다는..
-
[BOJ] 1644 소수의 연속합PS/BOJ 2020. 7. 16. 16:43
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 www.acmicpc.net 알고리즘: 투포인터, 에라토스테네스의 체 시간복잡도: O(N*log(logN)) 접근: 1. 소수 판별 2. 연속된 합, N 제한( 1번은 에라토스테네스의 체를 이용하면 O(NloglogN) 만에 해결이 가능하다. 문제는 2번인데, 구간 합 문제라고 생각하고 i~j까지 모든 조합을 계산하면, O(N^2)으로 TLE를 받게 ..
-
[BOJ] 1562 계단 수PS/BOJ 2020. 7. 16. 15:53
https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘: DP 시간복잡도: O(N^2 * 2^10) https://moon323.tistory.com/12 쉬운 계단 수의 심화문제이다. 0~9까지 모든 수가 자리수에 등장 이라는 조건만 추가되었다. 조합을 묻는 문제에서 on / off (등장, 비등장)을 묻는 문제는 비트연산을 이용해주면 빠르고 깔끔하게 해결 가능하다. 예를 들어, 이 문제 같은 경우 10bit를 만들어서 등장하는 수가 있으면 해당 bit를 1로 켜주면 된다. (or 연산) ex) b = 0000000000 1) 1 등장: b | (1
-
[BOJ] 10844 쉬운 계단 수PS/BOJ 2020. 7. 16. 12:21
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 알고리즘: DP 시간복잡도: O(N) 접근: 1. 계단 수가 총 몇 개 인지 구하기 (가짓수) 2. 계단 수 조건: 인접한 자리 수의 차이가 1 -> 1,2 번 조건 모두 Dynamic을 이용하기 좋은 조건들이다. 1번은 보통 DP 문제들의 패턴이고 2번도 부분문제로 접근할 수 있기 때문이다. 2번 조건을 DP로 접근해보면, N+1 자리수의 계단 수는 마지막 자리를 제외한 나머지 N 자리수도 계단 수를 만족해야한다. 따라서, N+1 자리수의 계단 수를 계산하려면 N 자리수 계단수부터 계산해야 하고 결국 bott..
-
[BOJ] 1520 내리막 길PS/BOJ 2020. 7. 16. 11:59
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 알고리즘: DP, BFS 시간복잡도: O(NM) 접근: 1. 지도가 주어지고 경로 탐색 2. 가능한(내리막길) 경로의 개수 구하기 -> 경로탐색은 보통 BFS로 접근하고, 가능한 가짓수를 구하는 문제는 보통 Dynamic으로 접근한다. D[i][j]: (i, j) 까지 가능한 경로의 가짓수 라고 하면, $$D[i][j] = \sum_{k=0}^N D[y_k][x_k]$$ $$(y_k,x_k):\..