알고리즘/백준
-
BOJ 21921 블로그알고리즘/백준 2022. 2. 11. 16:06
21921번: 블로그 (acmicpc.net) 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 슬라이딩 윈도우 기법으로 풀면 간단하다. 맨 처음은 그렇게 생각해서 문제를 풀었는데 슬라이딩 윈도우 알고리즘이 잘 생각이 되지 않아서 다이나믹 프로그래밍(?) 기법으로 풀어냈다. 먼저 dp 배열의 각 index는 1~index까지의 합계이다. 여기서 구간 합을 구하게 되는데 구간의 크기가 고정되어 있다보니 점화식을 다음과 같이 만들 수 있었다. int num = dp[i] - dp[i-k]; 여기서 i < k인..
-
BOJ 1238 파티알고리즘/백준 2022. 1. 28. 20:00
1238번: 파티 (acmicpc.net) 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 처음에는 문제를 잘못 이해해서 단순히 x번 집에서 다른 집으로 가는 최소 거리를 구하면 된다는 생각에 그래프의 정보로 들어오는 시작점과 도착점을 반대로 해 Node를 생성하는 방식을 채택했다. 그리고 결과를 보고 나서 문제를 다시 한 번 봤는데 알고보니 갔다가 다시 돌아오는 것이어서 방법을 바꿨다. 그런데 생각을 해보니 기존에 했던 방식은 우리가 2번으로 도착했다가 다시 돌아갈 수 있는 경..
-
BOJ 9177 단어 섞기알고리즘/백준 2022. 1. 26. 19:29
9177번: 단어 섞기 (acmicpc.net) 9177번: 단어 섞기 입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어 www.acmicpc.net 오래전에 풀지 못했던 문제를 해결하는 과정에서 문자열인데 DFS를 사용한다는 것이 내 입장에서는 특이한 것 같았다. 이 문제를 맨 처음 풀었을 때, 나는 단순히 세 번째 단어의 길이만큼 조사하여 이러한 경우들을 그대로 반영했다. 1. 첫 번째 단어의 현재 위치의 문자와 같을 경우 2. 두 번째 단어의 현재 위치의 문자와 같을 경우 여기서 맨 처음 떠올랐던 건 두 단어 문자가 같을 경우는 어떻게 하지?라는 점이었고, ..
-
BOJ 1613 역사알고리즘/백준 2022. 1. 21. 23:55
10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 만약 이 저울 문제를 플로이드-워셜 알고리즘을 통해 풀었었다면 이번 문제는 간단한 응용이다. 저울 문제에서 기존의 플로이드-워셜 알고리즘을 이용한 부분은 상하관계를 설정하고, O(N^3) 동안 기존 거리를 구하던 공식을 바꾸는 것에서부터 시작하였다. for ( int i = 1; i
-
BOJ 11404 플로이드알고리즘/백준 2022. 1. 20. 23:21
11404번: 플로이드 (acmicpc.net) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 알고리즘을 가장 대표할 수 있는 문제다. 플로이드-워셜 알고리즘은 향후 블로그에서 다룰거지만 그래프 탐색에서 한 지점에서 다른 지점으로 갈 수 있는 모든 최단 거리를 알고 싶을 때 사용하는 알고리즘으로 O(N^3)의 시간 복잡도를 가지고 있으므로, 현재 보이는 n의 크기가 100 이상을 넘어가게 되면 사용하는 것이 까다롭다. 여기서 중요한 점은 한 지점에서 같은 지점으로 가는 버스는 없고, 한 지점에서..
-
BOJ 11051 이항 계수 2알고리즘/백준 2021. 12. 27. 16:22
11051번: 이항 계수 2 (acmicpc.net) 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항 계수 문제. 이항 계수는 (x+y)^n의 식을 세웠을 때 0과 n의 위치는 항상 1이고 나머지 1~n-1까지의 값은 임의의 값 k를 뒀을 때 (x+y)^n-1의 계수들 중 k-1, k 위치의 계수를 더한 값이 나온다. 이렇게 만들어낸 것을 파스칼의 삼각형이라고 부르며 다음과 같이 나오게 된다. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 ... 일단 조건을 먼저 파악한 결과 방정식의 최대 지수가 1000이라는 것을 먼저 파악했다. 여기서 최대..