📌문제 출처 솔브닷 클래스 4 https://www.acmicpc.net/problem/1238 ❓ 문제 📗 풀이 코드 ''' 1. x로 가는 경로 구하기 입력받는 간선 정보의 출발, 도착을 거꾸로 입력받는다. 이를 통해 x에서 각 노드간의 거리를 한번의 다익스트라로 구하여 리스트 형태로 저장 2. x에서 돌아오는 경로 구하기 x 노드부터 출발하여 각 노드까지 가는 거리를 다익스트라로 구하여 리스트 형태로 저장 3. 두 리스트를 합하여 최댓값 구하기 다익스트라 함수를 만들고 flag에 따라 반환하는 종류를 두가지로 나누자. ''' from heapq import heapify, heappush, heappop input = open(0).readline def solution(): n,m,x = map(..
📌문제 출처 솔브닷 클래스 4 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 트리 구조에서 임의의 한 노드로부터 가장 멀리 떨어진 노드는 반드시 트리의 지름 중 한 노드이다. 따라서 임의의 한 노드부터 가장 멀리 떨어진 노드를 구하고 그 노드로부터 가장 멀리 떨어진 노드까지의 거리를 구하자. 1) bfs 함수 생성 node로부터 가장 멀리 떨어진 노드를 반환하는 함수 def bfs(node,fla..
📌문제 출처 솔브닷 4 클래스 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' if 진실을 아는 사람이 없다면 -> 모든 파티 참가 가능하므로 return m for 문 : 진실 아는 사람 딕셔너리에 1로 업데이트 for 문 : 파티 개수만큼 반복 -> 최악의 경우 마지막 확인하는 파티에서부터 한명씩 진실을 아는 사람이 늘어날 수 있음 for 문 : 각 파티별 사람을 한명씩 확인하며 한명이라도 진실을 알 경우 전체 파티원들 ..
📌문제 출처 백준 단계별 문제풀이 : 투 포인터 https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' meet in the middle 알고리즘 활용 1. stuff를 반으로 나누어 각각의 모든 부분집합의 합을 구한다. (a_sum, b_sum) 2. 이분탐색을 위해 b_sum을 오름차순 정렬 3. a_sum에서 하나씩 꺼내어 c이하면 진행 b_sum의 원소 중 둘의 합이 c이하인 최대값을 이분탐색으로 찾는다 찾은 인덱..
📌문제 출처 백준 단계별 문제풀이 : 투 포인터 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 연속된 수들의 부분합을 확인하며 그 합이 s이상이 되는 것 중 가장 짧은 것의 길이를 구하면 된다. 1. 만약 nums의 합이 s보다 작다면 불가하므로 return 0 2. 투 포인터 초기화 : left=right=0 3. 최소 길이 min_len = n+1, 현재 합 cnt 초기 값 = nums[0] 4..
📌문제 출처 백준 단계별 문제풀이 : 투 포인터 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 두가지 용액의 특성값을 합했을 때 0과 가장 가까운 두 용액을 찾아야한다. 1. nums(특성값) 오름차순 정렬 2. 투 포인터 지정 : left = 0, right = n-1 (인덱스 값) 3. 최소값 min_sum = float('inf'), 두 용액 ans = [] 지정 3. wh..
📌문제 출처 백준 단계별 문제풀이 : 투 포인터 https://www.acmicpc.net/problem/3273 ❓ 문제 📗 풀이 코드 ''' 1. 입력받은 nums를 오름차순 정렬해준다. 2. 두개의 포인터를 left=0와 right=n-1로 nums의 양쪽 끝 인덱스로 지정해준다. 3. while문 : nums[left]+nums[right]가 x인지 확인 if x보다 작다면 : x보다 크거나 같아질때까지 left+=1, continue 위 if문 통과 시 if x와 같다면 정답 +1 x와 같던, 크던 포인터는 이동해줘야되므로 right-=1 ''' input = open(0).readline def solution(): n = int(input()) nums = sorted(list(map(int..
📌문제 출처 백준 단계별 문제풀이 : 최단경로 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ❓ 문제 📗 풀이 코드 input = open(0).readline def solution(n): for k in range(1,n+1): # 중간에 1~n까지의 정류장을 들렀다가는 경우 for i in range(1,n+1): # 출발 정류장 for j in range(1,n+1): # 도착 정류장 dp[i][j] = min(dp[i][j], dp[..
