RUBY

출처:: www.acmicpc.net/problem/2343 분류:: 이진탐색 1. 문제 이해 및 해결과정 - 블루레이에 들어갈 수 있는 최대 시간을 기준으로 이분탐색 - left 는 트랙에서 제일 긴 값 -> max(arr) - right 는 트랙을 전체 합친 값 -> sum(arr) 2. 풀이방법 1. python #기타 레슨 #https://www.acmicpc.net/problem/2343 import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) arr=list(map(int,input().split())) #이분탐색의 기준은 기타레슨시간의 합(블루레이의 크기) left=max(arr) right=sum(arr) while..

출처:: www.acmicpc.net/problem/4195 분류:: unionfind 1. 문제 이해 및 해결과정 2. 풀이방법 1. 유니온파인드 [python] #친구 네트워크 #https://www.acmicpc.net/problem/4195 import sys sys.stdin = open("input.txt","r") tc=int(input()) def find_parent(x): if parent[x]!=x: parent[x]=find_parent(parent[x]) return parent[x] def union_parent(a,b): #a가 b의 부모라는 것 전제 a=find_parent(a) b=find_parent(b) if a!=b: #a의 부모노드와 b의 부모노드가 같지않으면 par..

출처:: www.acmicpc.net/problem/1976 분류:: 유니온파인드 1. 문제 이해 및 해결과정 - 1,2,3이 같은 집합인지 확인하기 2. 풀이방법 1. 유니온파인드 [python] #여행 가자 #https://www.acmicpc.net/problem/1976 import sys sys.stdin = open("input.txt","r") n=int(input()) #도시 수 m=int(input()) #여행계획에 속한 도시 수 board=[list(map(int,input().split())) for _ in range(n)] plan=list(map(int,input().split())) #여행 계획 parent=[0]*(n+1) for i in range(1,n+1): #부모 초기..

출처:: www.acmicpc.net/problem/2467 분류:: 투포인터, 이진탐색 1. 문제 이해 및 해결과정 - 투포인터 => O(n) - 범위조심 -1,000,000,000 이상 1,000,000,000 이하의 수가 입력되는데, 산성이나, 알칼리성만으로 이루어진 입력이 들어올 수가 있으므로 최대가 2,000,000,000 이 될 수 있다. 2. 풀이방법 1. 투포인터 [python] #용액 #https://www.acmicpc.net/problem/2467 import sys sys.stdin = open("input.txt","r") n=int(input()) arr=list(map(int,input().split())) minv=2e10 l=0 r=n-1 while l < r: sum=ar..

출처:: https://www.acmicpc.net/problem/3079 분류:: 이진탐색 1. 문제 이해 및 해결과정 2. 풀이방법 1. 이진탐색 python #입국심사 #https://www.acmicpc.net/problem/3079 import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) arr=[int(input()) for x in range(n)] left=min(arr) right=max(arr)*m result=0 while left=m: #인원이 더 많다면 시간 줄입 right=mid-1 result = mid else: #인원이 더 적다면 시간 늘림 left=mid+1 print(result) 3. 오답원인 ..

출처:: www.acmicpc.net/problem/1948 분류:: 위상정렬 1. 문제 이해 및 해결과정 - 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다.=> 임계경로 - 임계경로는 전체 중에서 여러 경로가 동시에 이루어질 때, 가장 오래 걸리는 경로를 의미한다. - 가장 오래 걸리는 경로를 구하고 백트래킹을 할 때 중복된 도로를 제거해주어야한다 1->2 2->6 6->7 // 1->4 4->6 6->7 의 두가지 경우가 존재한다. 6->7은 중복된 도로이므로 한 번만 카운트 해주어야 한다 2. 풀이방법 1. python #임계경로 #https://www.acmicpc.net/problem/1948 import sys from collections import deque sys...

출처:: www.acmicpc.net/problem/14921 분류:: 투포인터 1. 문제 이해 및 해결과정 - 중복입력가능 - left -1 2. 풀이방법 1. python #용액 합성하기 #https://www.acmicpc.net/problem/14921 import sys sys.stdin = open("input.txt","r") n=int(input()) arr=list(map(int,input().split())) minv=1e9 left=0 right=n-1 while left

출처:: www.acmicpc.net/problem/1717 분류:: 유니온파인드 1. 문제 이해 및 해결과정 2. 풀이방법 #집합의 표현 #https://www.acmicpc.net/problem/1717 import sys sys.stdin = open("input.txt","r") n,m=map(int,input().split()) #n+1개의 팀, 연산횟수 parent=[] def find_parent(parent,x): if parent[x]!=x: parent[x]=find_parent(parent,parent[x]) return parent[x] def union_parent(parent,a,b): a=find_parent(parent,a) b=find_parent(parent,b) if a