알고리즘
[BOJ / SCC] 4196 도미노
https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 4196 도미노 알고리즘 : 강한연결요소(SCC) SCC를 이용하여 사이클을 하나의 정점으로 만들어 위상정렬의 방식을 일부 따와서 푸는 문제입니다. 위상정렬은 사이클이 존재하면 풀리지 않으므로 SCC를 이용하여 사이클을 제거해주고 새로운 SCC에서 indegree가 0인 것을 카운팅 해주면 풀이됩니다. #include #include #include #include #include using na..
[BOJ / 휴리스틱(시뮬레이티드 어닐링)] 2582 동전 뒤집기 2
https://www.acmicpc.net/problem/2582 2582번: 동전 뒤집기 2 첫째 줄에 32 이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 2582 동전 뒤집기 2 알고리즘 : 휴리스틱(시뮬레이티드 어닐링) 시뮬레이티드 어닐링을 처음 공부할 때 풀었던 문제입니다. 첫 공부 시 다른 사람의 소스를 분석하여 풀이하느라 유사한 점이 많습니다. 밑 코드에서 주석으로 표기하였으니 이해하시는데 도움이 되었으면 좋겠습니다. 핵심 풀이 시 이해하여야 하는 것은 해당 줄에 앞면이 많은지 뒷면이 많은지는 중요한 것이 아니라 앞뒷면 수의 차이가..
[BOJ / 인덱스 트리] 1572 중앙값
https://www.acmicpc.net/problem/1572 1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1 www.acmicpc.net 1572 중앙값 알고리즘 : 인덱스트리 / 이분탐색 알고리즘 중에 힙 두개를 사용하여 데이터가 순서대로 들어올 때마다 현재 쿼리에서 중앙값을 구하는 중앙값 알고리즘이 있습니다. 이 알고리즘은 지금까지 받은 전체 범위에서 중앙값을 구하는 반면, 해당 문제는 범위를 주어주고 그 내에서 중앙값을 구해야 하므로 위 알고리즘을 활용해서 풀이할 수 없습니다...
[BOJ / 세그먼트 트리] 10999 구간 합 구하기 2
https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 10999 구간 합 구하기 2 알고리즘 : 세그먼트 트리 / 게으른 전파(Lazy Propagation) 세그먼트 트리 문제의 정석인 문제입니다. 구간 합 구하기 1에선 세그먼트 트리만 구현해도 되었지만, 2에서는 N이 커지고 쿼리가 많아져 할때마다 모든 연산을 다 해준다면 시간초과가 나게 됩니다. 이를 방지하기 위해 게으른 전파 ..
[BOJ / DP] 13398 연속합 2
https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 13398 연속합 2 알고리즘 : 누적합 / DP 일단 연속합의 최대를 구하는 sum을 이용해 연속합1 의 답을 구해준 뒤, - dp[0][i]에는 배열의 앞에서부터 i번째까지의 최대연속합 - dp[1][i]에는 배열의 뒤에서부터 i번째까지의 최대연속합 을 구해줍니다. 그 뒤, 1~n까지 돌며 dp[0][k-1] + dp[1][k+1]로 k번째 수를 제외하였을 때 연속합의 최대를 갱신해 답을 구해줍니..
[BOJ / 휴리스틱(시뮬레이티드 어닐링)] 16992 3-SAT
https://www.acmicpc.net/problem/16992 16992번: 3-SAT 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 100)과 절의 개수 M (1 ≤ M ≤ 1000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 세 정수 i, j, k (1 ≤ |i|, |j|, |k| ≤ N)로 이루어져 있으며, i, j, k가 www.acmicpc.net 16992 3-SAT 알고리즘 : 휴리스틱(시뮬레이티드 어닐링) 시뮬레이티드 어닐링(담금질 기법)을 이용한 휴리스틱 풀이입니다. 휴리스틱이란 정해를 구하기엔 시간이 충분하지 않거나 정보의 부족으로 인하여 합리적인 해를 제시할 수 없을 때, 빠르게 사용할 수 있는 확률에 의지하는 방법 입니다. SCPC에 자주 나오는 유형이라 이번에 ..
[BOJ / 플러드필 BFS] 2638 치즈
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 2638 치즈 알고리즘 : 플러드필 / BFS 바깥공기와 치즈, 안쪽 공기를 나누어 표기하고 첫 큐를 이용해 바깥공기를 처리, 공기에 맡닿은 치즈를 골라주고, 두번째 큐를 이용하여 다음 시간대에 녹을 치즈를 골라줍니다. 그렇게 골라서 만약 바깥공기와 안쪽 공기가 닿을 경우 첫 큐를 이용하여 처음과 같은 처리를 다시 이용해 주되, 메모이제이션을 통해 중복된 연산을 하지 않도록 합니다. ..
[BOJ / 메모이제이션 BFS] 2157 여행
https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 2157 여행 알고리즘 : 메모이제이션 / BFS 기본적인 메모이제이션을 이용한 BFS 풀이입니다. 인접리스트를 이용하여 각 도시간 항로를 만드는데 도착지가 출발지보다 작은 경우는 추가하지 않습니다. (시간 절약) 메모이제이션 테이블은 DP[A][B]=K를 - A : 현재까지 들린 도시의 수 - B : 현재 도시 번호 - K : 최대 ..