원

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 문제 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다. 출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. 두 노드가..

https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들어가는데, 일부를 소등하여 그만큼의 돈을 절약할 수 있다. 그러나 만약 어떤 두 집을 왕래할 때, 불이 켜져 있지 않은 길을 반드시 지나야 한다면 위험하다. 그래서 도시에 있는 모든 두 집 쌍에 대해, 불이 켜진 길만으..

https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 문제 그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임의의 두 정점..

https://www.acmicpc.net/problem/11365 11365번: !밀비 급일 당신은 길을 가다가 이상한 쪽지를 발견했다. 그 쪽지에는 암호가 적혀 있었는데, 똑똑한 당신은 암호가 뒤집으면 해독된다는 것을 발견했다. 이 암호를 해독하는 프로그램을 작성하시오. www.acmicpc.net END 입력 전까지 무한 반복문 내에서 입력한 문자열을 반대로 뒤집어서 출력해주면 되는 문제이다. 파이썬에서 제공하는 문자열 슬라이싱을 이용하여 쉽게 해결할 수 있는 문제이다. import sys while True: sentence = input() if sentence == "END": break answer = sentence[::-1] print(answer)

https://www.acmicpc.net/problem/3029 3029번: 경고 첫째 줄에 현재 시간이 hh:mm:ss 형식으로 주어진다. (시, 분, 초) hh는 0보다 크거나 같고, 23보다 작거나 같으며, 분과 초는 0보다 크거나 같고, 59보다 작거나 같다. 둘째 줄에는 나트륨을 던질 시간 www.acmicpc.net 문자열 문제이다. 시간을 계산해서 시간 차를 구하는 문제이다. 나는 초단위로 모든 시간을 구해주었다. 1시간은 3600초, 1분은 60초, 1초 이렇게 계산해주었다. 그리고 하나 주의해야할 점이 2개의 시간이 같은 경우 0시간 0분 0초 차이가 아닌 하루 차이가 난다는 것을 인지하지 못해서 한 번 틀렸었다. import sys first = input().split(':') se..

https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net LCA1도 있고 LCA2도 있는데 이 문제는 LCA2이다. 이유는 LCA1보다 시간효율성을 따져야하기 때문이다. 확인해야할 노드는 늘어났는데 시간효율성은 더 줄어들었다. 이 문제는 O(logn)으로 해결해야한다. 나도 이 알고리즘은 다른 분들의 블로그를 참고하면서 공부했다. 아직 불완전한 상태이다. https://justicehui.github.io/medium-algorithm/2019..

https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 분리집합 구현만 해주면 되는 아주 간단한 문제이다. 다른 부분을 고려할 필요없이 분리집합 구현만 해주면 되기 때문에 언급할 것이 없다,, #include #include #include #include #include #include #include #include #include #include #include #include #include #define CU..

https://www.acmicpc.net/problem/2902 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net 이 문제는 파이썬에서 제공하는 split()함수를 이용하면 쉽게 해결이 가능하다. split('-')문을 통해 -을 기준으로 나눠준 후 리스트로 변환하는 것이다. 그럼 각 리스트 안 원소의 첫번째 문자들만 합쳐주어 문자열로 만들어주면 정답이 된다. import sys from collections import * arr = sys.stdin.readline().split(..

https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 이 문제 분류가 DP로 되어있는데 값을 계속해서 기록하면서 최신화해서 DP인건가 아직 DP 개념이 안잡혀있어서 왜 DP인지 잘 모르겠다. 나는 재귀함수로 완전탐색을 구현했는데 어처피 맵의 크기도 매우 작기 때문에 완전탐색을 이용해서 해결하여도 충분하다. #include #include #include #include #include #include #include #include #..

https://www.acmicpc.net/problem/1595 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net 이 문제는 그래프 이론/탐색 문제이면서 트리의 지름과 비슷한 문제이다. 입력을 받고 난 후 하나의 시작점을 임의로 잡고 그 임의 시작점에서 다익스트라 알고리즘을 이용하여 모든 도로까지 떨어진 거리를 구해준다. 여기서 주의해야할 점이 이 문제는 문제의 조건에서 모든 도시는 다른 도시까지 이동할 수 있다는 전제를 주었기 때문에 다익스트라를 사용해도 무관하지만 만약 위 조건이 없다면 DFS나 BFS를 사..