동학 개발 운동

문제 출처 : www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 해석 : 트리의 지름을 구하는 문제이다. 트리의 지름이란 가장 긴 cost를 가지는 구간을 말한다. 문제 풀이 : 트리의 지름을 구하는 방법은 아무 정점에서 임의의 정점까지의 거리를 구하고 그 중 가장 먼 거리를 가지는 도착지를 시작지점으로 하여 다시 한번 거리를 구하여 가장 긴 것을 찾으면 된다. 이는 증명된 방법으로 항상 참이다. 즉 가장 긴 구간을 포함하는 도착지로 ..

문제 출처 : www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 문제 해석 : 중위 표현식을 후위 표현식으로 고치는 프로그램을 작성하는 문제이다. 문제 풀이 : 스택을 사용해서 각 상황에 맞게 행동을 해주면 된다. 후위 표현식을 만드는 방식을 문제에서 표현한 대로 하면 풀 수 있다. 다만 괄호가 있음에 유의해서 문제를 풀어야 한다. 풀이 코드 S = list(input()) answer = "" op = [] alpha = [] while S: tem..

문제 출처 : www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 해석 : 버스를 타고 이동할 때 출발지, 목적지가 주어진다. 이때 이동할 수 있는 최소 비용을 구하는 문제이다. 문제 풀이 : 다익스트라 알고리즘으로 풀이하면 풀 수 있다. 가능한 다른 풀이 : 플루이드 워셜 알고리즘을 적용해도 구할 수 있지만 시간 복잡도가 훨씬 높아 시간 초과가 날 수 있다. 풀이 코드 import sys, heapq input = sys..

문제 출처 : www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문제 해석 : 문자열을 탐색하는 것을 KMP 알고리즘으로 구현할 수 있는가를 묻는 문제이다. 문제 풀이 : 유명한 알고리즘인 KMP 알고리즘을 활용하여 풀이할 수 있다. - 다음 링크에 상세하게 알고리즘 동작 과정에 대해서 설명해 놓았다. LINK : bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 사용할 때 찾기 기능을 사용한적..

문제 출처 : www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 해석 : 웜홀은 시간이 거꾸로 흐른다. 이때 일반 경로와 웜홀을 통해서 자신이 출발했던 정점을 그 이전의 시간으로 돌아오는 것이 가능한지 구하는 문제이다. 문제 풀이 : 벨만-포드 알고리즘을 통해서 풀이가능하다. : 모든 정점에 대해서 자신의 정점까지의 거리가 적은 것으로 갱신되는 것을 N번 반복한다. : 이때 계속해서 반복된다면 이는 왕복할때마다 가중치가 줄어드는 곳이 있다는 ..

문제 출처 : www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제 해석 : 방향 그래프가 주어질 때 시작점에서 각 정점으로 가는 최단 경로를 구하여 출력하는 문제이다. 문제 풀이 : 모든 점에 대한 거리를 구할 때 1. 다익스트라 2. 플루이드 워셜 알고리즘을 활용할 수 있다. 이 문제에서는 정점의 개수가 20,000까지 주어지기 때문에 우선순위 큐를 활용한 다익스트라 알고리즘을 활용해서 풀어야 시간 초과를 피할 수 있다. 풀이 ..

문제 출처 : 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를 수행하면 시간 초과가 난다. 수학적인 접근이 필요하지만 pow에는 나누어 나머지를 구하는 연산이 포함되어 있기 때문에 이를 활용한다. (최적화가 적용되어 있음) 가능한 다른 풀이 : 실제로 문제가 의도한 것은 분할 정복이다. 예를 들어 200000 ** 2000000 은 굉장히 많은 시간이 소모 되기 때문에 수학적 풀이 방식으로 풀 수 있다. 다음과 같은 수식을 보..

문제 출처 : www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 해석 : 1에서 N 까지 이동할 때 항상 두 지점을 지나야한다. 이때 최단 경로로 움직일 때 그 거리를 구하는 문제이다. 문제 풀이 : 다익스트라 알고리즘을 적용해서 풀 수 있다. 가능한 경우의 수는 2가지 이다. : must1 -> must2 : must2 -> must1 이 둘 중에 최단 거리를 고른다. 이때 갈 수 없는 경로 일 경우에는 -1..

문제 출처 : www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 해석 : 어떤 정점에서 한 정점으로 왕복하는 거리가 가장 먼 것을 찾는 문제이다. 파티를 갔다오는 사람들은 항상 최단 경로로 왕복한다고 했기 때문에 최단 경로로 특수 정점을 왕복하는 문제로 해석 가능하다. 문제 풀이 : 다익스트라 알고리즘을 통해서 문제를 풀 수 있다. - 플루이드 워셜 문제로 풀 경우에는 10^9로 시간 복잡도가 너무 크기 때문에 시간 초과가 ..

문제 출처 : www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 문제 해석 : 트리의 정점과 정점 사이의 거리가 주어 졌을 때 한 정점에서 다른 정점까지의 거리가 가장 멀때의 거리를 구하는 문제이다. 문제 풀이 : 이 문제는 BFS, DFS로 풀이 할 수 있다. 이때 아래의 2가지를 주의하면서 차근차근 풀어야 한다. 1. 어떤 점에서 출발하는지를 정해야 한다. -> 항상 1에서 시작하는게 가장 길지 않을 수 있다. --> 따라서 1번 수행하면서 가장..