목차 최소 신장 트리 Prim 알고리즘 KRUSKAL 알고리즘 1. 최소 신장 트리(Minimum Spanning Tree) 그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 간선의 가중치의 합이 최소여야 한다. 사이클이 포함되어서는 안된다. 사용 사례 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우 표현 그래프 간선들의 배열 인접 리스트 부모 자식 관계와 가중치에 대한 배열 트리 2...

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net # 조건 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성 0

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net # 조건 사무실은 1x1 크기의 정사각형으로 나누어져 있는 N x M 크기의 직사각형으로 나타낼 수 있다. 총 K개의 CCTV가 있는데 5종류가 존재 한 쪽 방향 서로 반대방향인 두 방향 - 상하, 좌우 서로 직각인 두 방향 - 좌상, 좌하, 우상, 우하 세 방향 감시 네 방향 검사 검사할 수 있는 방향에 있는 칸 전체를 감시 가능 벽은 통과하지 못한다. 지도에서 0은 빈 칸, 6은 벽..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net # 조건 자연수 A를 B번 곱한 수를 알고 싶은데, 구하려는 수가 매우 커질 수 있으므로 C로 나눈 나머지를 구하여라 A, B, C는 2,147,483,647 이하의 자연수이다. # 접근 방법 일반적인 곱셈을 활용한다면 시간초과가 날 것이다. 분할 정복을 이용하여 지수를 짝수와 홀수 일 때를 나눠준다. 짝수인 경우 - 지수가 10이라면 A^10 = A^5 * A^5 홀수인 경우 A^5 = A^2 * A^2 * A b가 홀수 = 2^9 == 2^4 2^4 2 즉 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 N x N 모양의 지역에 디저트 카페가 모여있다. 칸의 숫자는 디저트의 종류를 뜻하며 카페들 사이에는 대각선 방향으로만 이동 가능 대각선으로 카페 투어를 떠난 후 다시 처음 카페로 돌아오면 된다. 이때, 한 번 먹은 종류의 디저트 카페는 갈 수 없고, 왔던 길도 돌아갈 수 없다. # 접근 방법 #1 dfs dfs를 이용하여 사각형을 그려주며 탐색할 수 있다. 회전 방향을 정하고, 카페와 디..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GKs06AU0DFAXB SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 8*8의 체스보드에 8개의 퀸을 서로 공격하지 못하게 놓는 문제는 잘 알려져 있는 문제 퀸은 같은 행, 열, 또는 대각선 위에 있는 말을 공격할 수 있다. 조금 더 일반화시켜 N*N 보드에 N개의 퀸을 서로 다른 두 퀸이 공격하지 못하게 놓는 경우의 수를 구하시오. # 접근 방법 및 Solution "모든 경우의 수"인 브루트 포스로 해결할 수 있지만 이후의 사건이 이전의 사건에 종속적이므..

다익스트라(dijkstra) 알고리즘은 일상생활에서, 지하철, 내비게이션 등 여러 분야에서 사용되는 알고리즘이다. 활용 예시를 보면 알 수 있듯이 최단 경로 알고리즘인 다익스트라 알고리즘을 알아보자. # 다익스트라 알고리즘 하나의 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘 자료 구조로는 그래프(graph) 사용 노드와 가중치를 가진 간선을 이용하여 실제 거리를 표시한다. 초기에 우선순위 큐를 사용하지 않은 다익스트라 알고리즘 O(V^2)의 시간 복잡도 우선순위 큐로 인한 개선으로 O(E log V) - V, E = 노드와 간선의 수 삽입 삭제, 최소 값 추출 - O(logV) 기본적으로 다익스트라는 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 사용 => 다이나믹 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 위 그림처럼 도로 곳곳이 파손되어 있다. 복구하기 위한 공병대는 상하좌우로 이동 가능하며, S(0,0)에서 G(N-1,N-1)까지 복구 작업을 하는데 가장 빠른 시간 내에 수행한다. 깊이 1에 시간 1이 걸리며 한 칸씩 움직일 수 있다. # 접근 방법 최단 경로 알고리즘이다. 다익스트라 알고리즘을 사용하며, heapq 대신 BFS를 함께 사용해주어도 될 것 같다. 내가 갈 좌표에 대해, 좌..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net # 조건 add x : S에 x를 추가한다. S에 이미 x가 있는 경우 연산 무시 remove x : S에서 x를 제거한다. S에 x가 없는 경우에는 연산 무시 check x : S에 x가 있으면 1을, 없으면 0을 출력 toggle x : S에 x가 있으면 x를 제거, 없으면 x를 추가 all : S를 {1,2,3,...,20} 으로 바꾼다. empty : S를 공집합으로 바꾼다. # 접근 방법 & Solution 조건의 함수들을..