boj

[백준 1238] 파티 C++

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 단순한 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것이지만 이 문제는 A->X로가는 최단거리 + X->A로 되돌아오는 최단거리를 구해야 한다. A->X로 가는 최단거리를 구해보자. 정점의 개수가 최대 1000개, 간선의 개수가 최대 10000개 이므로 O(|V||E|) = 10,000,000 이 되어 시간내에 풀 수 있다고 생각했다. 그래서 A->X로 가는 최단거리를 A의 개수만..

[백준 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 타잔 알고리즘을 사용해서 풀었다. 개인적으로 코사라주보다 직관적이..

[백준 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에 넣는다는 의미는 자신보다 먼저 수행되어야 할 정점이 없어서 현재 정점을 바로 실행해도 무방하다는 ..

[백준 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이라고 하면 ..

[백준 1688] 지민이의 테러 C++

1688번: 지민이의 테러 첫째 줄에 방어막의 꼭짓점의 개수 N(3 ≤ N ≤ 10,000)이 주어진다. 이어서 N개의 줄에는 꼭짓점들의 좌표가 순서대로 주어진다. 시계방향으로 주어질 수도 있고, 반시계방향으로 주어질 수도 있 www.acmicpc.net 기하학, 선분 교차, 레이 캐스팅 알고리즘 1. 문제 해결 아이디어 많은 예외 케이스 때문에 10번넘게 틀린 문제... 오래 고민한 만큼 정이 들어버린 문제다.. [백준 17387] 선분 교차 2 C++ 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 선분 교차 알고리즘 계산 기하학 알고리즘 중 선분 교차 알고리즘을....