PS/BOJ
-
[BOJ] 1987 알파벳PS/BOJ 2020. 7. 17. 17:00
https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 www.acmicpc.net 알고리즘: DFS, Backtracking 접근: 1. 경로 탐색 문제 2. 같은 알파뱃이 적힌 칸은 두 번 지날 수 없다 3. 최대한 몇 칸을 지날 수 있는가 -> 1, 3번 조건을 보면 이 문제가 DFS 문제라는 것을 알 수 있다. (경로를 탐색해가면서 최장경로 찾기) 이제 2번 조건만 해결해주면 된다. 2번은 조건은 알파뱃과 숫자를 하나씩 대응시켜 (A-0, B-1, C-2, ...,..
-
[BOJ] 1932 정수 삼각형PS/BOJ 2020. 7. 16. 20:14
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 알고리즘: DP 시간복잡도: O(N^2) 접근: 1. 이전 값들을 참고하면서 갱신하는 것이므로 Dynamic 문제 $$D[k]=MAX(D[k-i-1],\ D[k-i])+a_k$$ 주의) 각 층의 양 끝점은 한 쪽 대각선이 없으므로 이를 예외 처리해줘야 함. 더보기 #include int main() { int N, a, i, j, k, D[500*500], max..
-
[BOJ] 1912 연속합PS/BOJ 2020. 7. 16. 19:48
https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 알고리즘: DP 시간복잡도: O(N) 접근: 1. 연속합의 최댓값 구하기 수열의 특정 부분을 봤을 때, 이 수가 최대 연속합의 일부가 될 가능성이 있다는 것을 알 수 있을까? 일단 수열의 수들을 계속 더해나가자... 만약에 수가 양수일 시, 이들을 계속 더하다보면 최댓값에 도달할 것이다. 하지만, 이 문제는 중간 중간에 음수들이 섞여있다. 따라서 계속 더해 나가다가 부분합이 0보다 작아지게 되면, 차라리 다..
-
[BOJ] 1904 01타일PS/BOJ 2020. 7. 16. 19:37
https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 알고리즘: DP, Math (Fibonacci number) 시간복잡도: 1. O(N) 2. O(p) (p = 47244, Pisano Period) 접근: 1. 1, 00 타일로 만들 수 있는 길이가 N인 수열의 모든 가짓수 2. 타일을 붙여서 점점 길이를 확장 (부분문제) -> 1, 2번 조건을 통해 Dynamic으로 접근할 수 있음을 알 수 있다. D[N]: 길이가 N인 수열을 만들 수 있는 ..
-
[BOJ] 1806 부분합PS/BOJ 2020. 7. 16. 19:11
https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 알고리즘: 투포인터 시간복잡도: O(N) 접근: 1. 연속된 수들의 부분합 -> 연속된 수의 합을 묻는 문제이다. BOJ 1644 소수의 연속합 문제처럼 투포인터로 접근하면 된다. (시작점:st, 끝점:en) 부분합이 S를 넘기면 st++, 길이 갱신(길이의 최솟값 구하기) 부분합이 S보다 작으면 en++ 더보기 #include #include #define MIN(a, b) (((a)>(b))..
-
[BOJ] 1799 비숍PS/BOJ 2020. 7. 16. 19:01
https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 알고리즘: Backtracking (brute-force) 접근: N-queen 문제랑 비슷한 문제로 brute-force로 접근하였다. 이런 류의 문제는 항상 그렇듯 얼마나 가지치기를 잘하냐에 따라 정답이 갈린다. (오답의 대부분은 TLE 일 것이다.) 고로 비숍을 배치한다 했을 때, 왼쪽/오른쪽 대각선 모든 좌표를 일일히 확인하는 것은 상당히 비효율적이며 좀 더 효율적인 방식을 찾아야 한다. 그래서 각..
-
[BOJ] 13913 숨바꼭질 4PS/BOJ 2020. 7. 16. 18:26
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 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 이동하는 경로를 출력하는 부분이 추가되었다. 경로 추적은 이전에 BOJ 12852 1로 만들기2 https://moon323.tistory.com/6 에서 DP 경로 역추적을 하는 방식이랑 비슷하다. BFS에서 a->b로 ..
-
[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];..