전체 글 (6) 썸네일형 리스트형 [BOJ] 11976 최소 스패닝 트리(크루스칼 알고리즘) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 주제: 크루스칼 알고리즘 시간복잡도: O(e*log(e)) //boj 1197 최소 스패닝 트리 //알고리즘: 크루스칼 알고리즘 //시간복잡도: O(elog(e)) /* MST를 공부하는 과정이고, prim 알고리즘도 써봐야겠다 priority_queue를 사용하는 방법도 있다 -> 그것돟 알아보긴 할거다 python으로 풀면 굉장히 빠르게 풀린다 -.. [BOJ] 1865 웜홀(벨만 포드) https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 주제: 벨만포드 알고리즘 시간복잡도: O(|V|*|E|) //boj 1865 웜홀 //알고리즘: 벨만포드 //시간 복잡도: O(|V||E|) //오래 걸렸다. /* 틀린 이유 -> if(d[From] == INF) continue; 이 부분은 모든 그래프가 연결 되어 있을 때만 의미가 있지, 그래프가 연결 되어 있지 않다면, 없어야 하는 조건이다. 그래야지 떨어져 있는 그래프에서의 음.. [BOJ] 4095 최대 정사각형(DP) , 11660 구간 합 구하기 5(DP) www.acmicpc.net/problem/4095 4095번: 최대 정사각형 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 www.acmicpc.net www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 두 문제의 공통점은 사각형(행렬)에서 dp를 사용해.. [BOJ] 1516 게임 개발(DFS+DP or 위상 정렬+DP) www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 주제: DFS+DP or 위상정렬+DP 시간복잡도: O(|V| + |E|) 1) DFS, DP를 이용한 풀이(8ms, 간단함) 설명: 재귀 함수를 이용해서 TOP- DOWN 형식으로 DFS를 돌며 Critical Path(동시에 실행할 때 제일 시간이 오래 걸리는 경로)가 걸리는 시간을 구해낸다. 기준 노드로 들어오는 경로 중에서 가장 오래걸리는 경로를 선택한다. 즉, 다익스트라의 최대값 구하기 버전.. [BOJ] 1987 알파벳(DFS, 백트래킹) www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 범주: DFS, 백트래킹 시간복잡도: ?? 설명: 백트래킹을 진행하며 노드를 판단한다. 1) 다음 노드(4방향)는 현재 한번도 만나지 않은 알파벳이다 -> 재귀 2) 다음 노드(4방향) 중 어떠한 곳도 이동할 수 없다 -> 경로 길이를 얻은 후, 최대인지 평가 시도: 1) alpha 배열을 parameter로 보냈었다. -> 성공했지만 시간이 오래 걸림. 또한 배열의 크기가 컸을 경우(ex. 스도쿠, N.. [BOJ] 2206 벽 부수고 이동하기(BFS, 3차원 배열) www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 범주: BFS, 3차원 배열을 이용한 DP 시간복잡도: O(N*M) 설명: BFS를 진행하면서 2가지 상황에서 이동이 가능하다. 전제) 다음 노드는 한번도 접근되지 않은 노드이므로 최소 경로임이 보장된다. 1) 다음 노드는 벽이 아니다(pos[r][c] == 0). 2) 다음 노드는 벽이지만(pos[r][c] == 1), 현재 노드는 벽을 부수지 않고 진행했다. 시도: 1) 백트래킹 -.. 이전 1 다음
