알고리즘
-
백준 1507번 궁금한 민호 [플로이드] :: 마이구미알고리즘 풀이/그래프 2017. 2. 3. 17:36
이번 글은 백준 알고리즘 문제 "궁금한 민호"를 다뤄본다.플로이드 와샬 알고리즘을 통해 해결한다.백준 알고리즘 1507번 궁금한 민호 - https://www.acmicpc.net/problem/1507 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 수 없는 경우는 존재하지 않는다.도시 A에서 도시 B로 바로 갈 수 있는 도로가 있거나, 다른 도시를 거쳐서 갈 수 있을 때, 도시 A에서 B를 갈 수 있다고 한다.강호는 모든 쌍의 도시에 대해서 최소 이동 시간을 구해놓았다. 민호는 이 표를 보고 원래 도로가 몇 개 있는지를 구해보려고 한다.예를 들어, 예제의..
-
백준 2146번 다리 만들기 :: 마이구미알고리즘 풀이/그래프 2017. 1. 24. 22:52
이번 글은 백준 알고리즘 문제 2146번 "다리 만들기" 를 다뤄본다.이 문제는 BFS DFS 활용 문제이다.하단에 비슷한 문제들이 나열되어 있다.DFS, BFS 관련 글.http://mygumi.tistory.com/102 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다에 가장 짧은 다리를 놓아 두 대륙을 연결하고자 한다. 가장 짧은 다리란, 다리가 격자에서 차지하는 칸의 수가 가장 작은 다리를 말한다. 다음 그림에서 두 대륙을 연결하는 다리를 볼 수 있다.물론 위의 방법 외에도 다리를 놓는 방법이 여러 가지 있으나,위의 경우가 놓는 다리의 길이가 3으로 가장 짧다(물론 길이가 3인 다른 다리를 놓을 수 있는 방법도 몇 가지 있다).지도가 주어질 때, 가장 짧은 다리 하..
-
백준 1068번 트리 :: 마이구미알고리즘 풀이/그래프 2017. 1. 24. 22:01
이번 글은 백준 알고리즘 1068번 문제 "트리" 를 다뤄본다.문제명 그대로 트리 문제이다.백준 알고리즘 1068번 트리https://www.acmicpc.net/problem/1068 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이 때, 1번을 제거한다고 하면, 다음과 같이 된다. 위 그림과 같이 1번을 제거한다면 리프노드는 2번 노드 하나밖에 남지 않는다.만약 3번을 제거한다면 2번, 4번 노드가 남아 2개의 리프노드가 남게 된다.그렇다면 0번이 제거된다면, 리프노드는 0개가 되는 것이다.즉 제거되는 노드의 자식들을 함께 제거한다. 문제는 생각보다 간단하다.결국 제거되는 노드와 연결되어있는 자식들을 제거하면 된다.다른 사람들은 쉽게 배열만으로 풀었지만, 본인은 머리가 잘 안돌아갔다. 본..
-
백준 10451번 순열 사이클 :: 마이구미알고리즘 풀이/그래프 2017. 1. 22. 15:28
이번 글은 백준 알고리즘 10451번 "순열 사이클" 을 다뤄본다.백준 알고리즘 10451번 순열 사이클 문제https://www.acmicpc.net/problem/10451DFS, BFS 관련 글.http://mygumi.tistory.com/102 위 그림처럼 사이클 개수를 찾는 문제이다. (방향이 존재함으로 방향 그래프)정점들이 연결되어 하나의 그래프를 이루는 것을 그래프의 연결 요소라고도 말한다.즉, 연결 요소의 개수가 순열 사이클의 개수와 같은 의미이므로, 연결 요소를 구하면 되는 문제이다. 이 문제의 이름이 보면, 순열 그래프이다.순열의 정의 상 숫자는 중복으로 입력되지 않는다고 한다.그렇다는 건, 그래프가 한개 이상이 존재하지만, 주어지는 그래프는 모든 정점에 연결된 사이클이 있는 그래프라..
-
백준 11403번 경로 찾기 :: 마이구미알고리즘 풀이/그래프 2017. 1. 20. 23:42
이번 글은 백준 알고리즘 문제 11403번 "경로 찾기" 를 다뤄본다.이 문제는 그래프의 DFS, BFS 를 활용하는 문제이다.DFS, BFS - http://mygumi.tistory.com/102백준 알고리즘 문제 11403번 경로 찾기 - https://www.acmicpc.net/problem/11403 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 친절하게 문제에서 어떤 그래프인지 말해주고 있다.가중치가 없는 방향 그래프라고 명시되어 있다.그래프에 대한 글에서 무방향 그래프를 기준으로 다뤘었다.차이는 단지 방향이 있고 없고 차이뿐이다. // 무방향 그래프 인접행렬a[v1][v2] = 1;a[v2..
-
백준 2493번 탑 [Stack] :: 마이구미알고리즘 풀이/스택, 큐 2017. 1. 18. 23:48
이번 글은 백준 알고리즘 2493번 문제 "탑" 을 다뤄본다.스택을 응용한 문제이다.백준 2493번 탑 문제 - https://www.acmicpc.net/problem/2493 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한..
-
백준 2579번 계단 오르기 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 16. 22:58
이번 글은 백준 알고리즘 2579번 "계단 오르기" 문제를 다뤄본다.일단 문제를 보자. 이 문제는 동적계획법으로 접근하는 문제이다.문제에서 친절하게 규칙 3가지를 알려주었다.먼저 3번 규칙을 보면, 마지막 계단은 무조건 밟는다는 것이 규칙이다. 그렇다면, 마지막 계단을 밟았을 경우, 이전의 경우를 2가지로 생각할 수 있다.1. 마지막 계단 전의 계단을 밟은 경우.2. 마지막 계단 전의 계단을 밟지 않은 경우. 1번의 경우에는 마지막 계단 전의 계단을 밟았음으로, 마지막 계단 전전의 계단은 밟지 못한다.2번의 경우에는 마지막 계단 전의 계단을 밟지 않았음으로, 마지막 계단 전전의 계단을 밟고 왔다. 위 경우를 통해 점화식을 도출해보자. 1. dp[n] = dp[n-3] + array[n-1] + array..
-
백준 1932번 숫자삼각형 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 3. 23:26
이번 글은 백준 알고리즘 문제 1932번 "숫자삼각형" 을 다뤄본다.이 문제의 풀이 방식은 DP(동적계획법)이다.문제를 한번 보자. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5위 그림은 크기가 5인 숫자 삼각형의 한 모습이다.맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.맨 위층을 0층으로 가정하겠다.1 층 : 7 -> 3 || 7 -> 82 층 : 7 -> 3 -> 8 || 7 -> 3 -> 1 || 7 -> 8 -> 1 || 7 -> 8 -> 0................