Algorithm

[백준 1509] 팰린드롬 분할 C++

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일단 문자열의 모든 범위에 따른 팰린드롬 여부를 2차원 table로 만들었다. dp[st][ed]에는 st부터 ed까지의 문자열이 팰린드롬인지 확인여부가 담겨있다. dp table을 채울 때 str[st]와 str[ed]가 같고 dp[st+1][ed-1]이 팰린드롬이면 dp[st][ed]도 팰린드롬인 성질을 이용해서 O(n^2)으로 테이블을 구할 수 ..

[백준 3197] 백조의 호수

3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net BFS 1. 문제 해결 아이디어 2021.07.01 - [Algorithm/BOJ] - [백준 2636] 치즈 C++ [백준 2636] 치즈 C++ 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄 hyeo-noo.tistory.com 백조 문제에서 매일 얼음 표면을 찾고, 얼음을 녹이는..

[백준 2636] 치즈 C++

2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net BFS 1. 문제 해결 아이디어 치즈의 겉 표면을 찾기 위한 BFS + 겉표면을 녹이는 BFS 이렇게 2개의 BFS를 사용해서 풀었다. BFS를 2개 쓴거라서 아마 내 풀이가 최적의 풀이는 절대 아닐거라 생각한다. 먼저 공기와 맞닿아 있는 치즈표면을 BFS를 통해서 모두 구하면서 개수를 저장해 놓는다. 이때 치즈가 없다면 종료 만약 치즈가 있다면 겉표면 치즈들을 녹이는 BFS를 수행한다. 두 과정을 합칠 수 있을것 같다.. 2. 코드 1 2 3 4 5 6 7 8 9 10..

[백준 4196] 도미노 C++

4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 강한 연결 요소 1. 문제 해결 아이디어 강한 연결 요소 (SCC) - 타잔 알고리즘 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이.. hyeo-noo.tistory.com 타잔 알고리즘을 사용해서 풀었다. 개인적으로 코사라주보다 직관적이..

Sorting Game (SORTGAME)

algospot.com :: SORTGAME Sorting Game 문제 정보 문제 중복이 없는 정수 수열이 주어진다. 이 때, 우리는 이 수열의 임의의 구간을 선택해서 해당 구간을 뒤집을 수 있다. 이 뒤집기 연산을 통해 전체 수열을 정렬하고 싶다. algospot.com BFS, 최단거리 처음보는 유형의 문제. 신기한 문제 지금까지 백준에서 푼 bfs문제들은 그래프의 정점이나 좌표정도만 queue에 넣고 bfs를 수행했는데 이 문제는 순열 벡터를 que에 넣으면서 해당 순열을 몇 번째로 방문했는지 bfs를 통해서 체크한다. 1. 중복되는 숫자는 없기 때문에 숫자의 크기가 다르더라도 상대적인 크기가 같은 배열들에 대한 답은 항상 같다. ex) {37, 80, 12, 25}와 {3, 4, 1, 2}는 상..

[백준 1562] 계단 수 C++

1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 비트필드를 이용한 다이나믹 프로그래밍 1. 문제 해결 아이디어 현재 구한 계단 수의 자릿수, 마지막 숫자 위 2개의 정보를 가지는 2차원 배열로 문제를 해결하려 했었는데 당연히 답이 제대로 나오지 않았다. 0~9의 숫자가 각각 사용되었는지 아닌지 알아야 하기 때문에 (10개의 숫자 각각 사용되었는지 아닌지에 대한 경우의 수 2^10) 따라서 [1

[백준 2623] 음악프로그램 C++

2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상 정렬 1. 문제 해결 아이디어 indegree를 활용한 위상 정렬로 풀었다. 입력을 받을 때 각 정점마다 indegree가 몇 개 인지 배열에 저장해준다. 위상 정렬 bfs를 수행하면서 현재 정점의 자식 정점들의 indegree를 하나씩 빼준다. 만약 자식 정점의 indegree가 0이 된다면 현재 정점을 queue에 넣어준다. queue에 넣는다는 의미는 자신보다 먼저 수행되어야 할 정점이 없어서 현재 정점을 바로 실행해도 무방하다는 ..

강한 연결 요소 (SCC) - 타잔 알고리즘

[백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간.. hyeo-noo.tistory.com 학교 알고리즘 수업 때 코사라주 알고리즘을 활용한 SCC풀이법을 배웠다. 하지만 구글링을 해보니 코사라주 알고리즘보다는 타잔 알고리즘이 구현이 어렵지만 활용도가 더 높다고 해서 공부해 보았다. 타잔 알고리즘 1번 정점에서 dfs를 시작해 2, 3, 4번 정점을 순서대로 방문했다고 하자. 타잔 알고리즘에서는 방문할 때마다 임의의 sta..

[백준 11266] 단절점 C++

11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net Cut vertex, DFS 1. 문제 해결 아이디어 dfs를 통해서 정점들의 방문순서를 기록해주는게 핵심이다. 현재 노드의 자식중에서 자신보다 더 빠른 방문순서를 가진 정점을 방문하지 않은 자식이 하나라도 있다면 현재 노드는 단절점이 된다. 단절점을 구할 때 중요한 점은 root정점이 단절점인 경우는 따로 구해줘야 하는 것이다. root정점이 자식을 둘 이상 가지고, 자식간에 연결되어있지 않다면 root정점도 Cut vertex가 된..

[백준 1208] 부분수열의 합2 C++

1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 이분 탐색 1. 문제 해결 아이디어 N이 40개 이므로 모든 부분수열을 다 구하려면 2^40번의 연산이 필요하다. -> 1초안에 풀 수 없다. 주어진 수열을 절반씩 나누어서 계산해 보자 수열의 길이가 40이라고 가정하자. 20번째 수열부터 40번째 수열(이를 right수열이라고 하자)까지의 모든 부분수열의 합을 구해본다. 이때 시간복잡도는 O(2^20)이므로 시간은 충분하다. right 부분 수열의 합을 sum이라고 하면 ..