백준
-
백준 5567번 결혼식 [그래프] :: 마이구미알고리즘 풀이/그래프 2017. 4. 10. 14:21
이번 글은 백준 알고리즘 5567번 "결혼식" 을 다뤄본다.그래프를 통해 문제를 해결할 수 있다.DFS, BFS - http://mygumi.tistory.com/102Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 문제는 상근이의 친구와 상근이의 친구의 친구를 초대할 수 있다.상근이의 친구상근이의 친구의 친구위의 2가지의 조건에 ..
-
백준 2096번 내려가기 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 4. 4. 20:25
이번 글은 백준 알고리즘 2096번 문제 "내려가기"를 다뤄본다.이 문제는 동적계획법으로 해결할 수 있다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 문제를 이해하기에는 어렵지 않다.문제에서..
-
백준 2225번 합분해 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 3. 9. 20:11
이번 글은 백준 알고리즘 문제 2225번 "합분해" 를 다뤄본다.동적계획법으로 접근하는 문제이다.일단 문제를 보자. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 문제는 간단하다.하지만 점화식을 생각하기에는 어렵다.간단하게 먼저 2차원 배열로 생각해보자.DP[K][N] = K개를 더해서 합이 N일 경우를 생각할 수 있다.이어서 그림을 통해 알아보자. 그림을 설명해보자면, 합 N을 만들기 위해서는 0~N까지 정수가 다양하게 존재한다.그 중 마지막 수를 L라고 가정하자.L 이전의 수들의 합은 N-L 이라는 것을 알 수 있다.또한 K개..
-
백준 1068번 트리 :: 마이구미알고리즘 풀이/그래프 2017. 1. 24. 22:01
이번 글은 백준 알고리즘 1068번 문제 "트리" 를 다뤄본다.문제명 그대로 트리 문제이다.백준 알고리즘 1068번 트리https://www.acmicpc.net/problem/1068 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이 때, 1번을 제거한다고 하면, 다음과 같이 된다. 위 그림과 같이 1번을 제거한다면 리프노드는 2번 노드 하나밖에 남지 않는다.만약 3번을 제거한다면 2번, 4번 노드가 남아 2개의 리프노드가 남게 된다.그렇다면 0번이 제거된다면, 리프노드는 0개가 되는 것이다.즉 제거되는 노드의 자식들을 함께 제거한다. 문제는 생각보다 간단하다.결국 제거되는 노드와 연결되어있는 자식들을 제거하면 된다.다른 사람들은 쉽게 배열만으로 풀었지만, 본인은 머리가 잘 안돌아갔다. 본..
-
백준 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..
-
백준 3986번 좋은 단어 [Stack] :: 마이구미알고리즘 풀이/스택, 큐 2017. 1. 16. 21:00
이번 글은 백준 알고리즘 3986번 "좋은 단어" 를 다뤄본다.이 문제는 스택을 통해 접근하는 문제이다.백준 3986번 좋은 단어 - https://www.acmicpc.net/problem/3986 평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 갯수를 세는 것을 도와주자. 문제만 보면, 바로 쉽게 이해하기는 힘들 수 있다.먼저 예를 통해 문제를 이해해보자.ABAB 주어졌을 경우를 보자.1. ABAB => A와 A 위로 아치형 곡선을 그린다.2. ABAB => B와 B 위로 아치형 곡선을 ..