목록실버쥐 (23)

개발아 담하자

[백준/C++] 2468번 : 안전 영역 풀이

문제 2468번 : 안전 영역 문제 링크 : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어 www.acmicpc.net 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다...
👩‍💻 알고리즘 풀이/백준 2020. 2. 2. 03:41
[백준/C++] 2583번 : 영역 구하기 풀이

문제 2583번 : 영역 구하기 문제 링크 : https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다. www.acmicpc.net 문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어..
👩‍💻 알고리즘 풀이/백준 2020. 2. 2. 03:34
[백준/C++] 11724번 : 연결 요소의 개수 풀이

문제 11724번 : 연결 요소의 개수 문제 링크 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. www.acmicpc.net 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄..
👩‍💻 알고리즘 풀이/백준 2020. 2. 2. 03:29
[Algorithm] 플로이드 와샬 알고리즘

Floyd-Warshall (플로이드-워셜 알고리즘) 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. - '모든 정점' 에서 '모든 정점' 으로의 최단 경로를 구하고 싶다면 플로이드 워셜 알고리즘 을 사용해야 한다. - 핵심 아이디어는 '거쳐가는 정점' 을 기준을 최단 거리를 구하는 것이다. - 기본적으로 다이나믹 프로그래밍(DP) 기술에 의거한다. - 최단 경로를 찾기에 좋은 알고리즘이다. 위와 같은 그래프가 존재한다고 가정할 때, 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열의 형태로 출력한다면 다음..
🌟 자료구조+알고리즘 2020. 2. 2. 00:09
이전 Prev 1 2 3 4 5 6 Next 다음