RUBY

출처:: 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

출처:: https://www.acmicpc.net/problem/2512 분류:: 이진탐색 1. 문제 이해 및 해결과정 2. 풀이방법 1. python 이진탐색 #예산 #https://www.acmicpc.net/problem/2512 import sys sys.stdin = open("input.txt","r") n=int(input()) a=list(map(int,input().split())) m=int(input()) left=1 right=max(a) while leftmid: sum+=mid else: sum+=x if sum>m: right=mid-1 else: result=mid left=mid+1 print(result) 3. 오답원인 4. 알게된 점

출처:: www.acmicpc.net/problem/3665 분류:: 위상정렬 1. 문제 이해 및 해결과정 - 정해진 순위에 맞게 팀들의 순서를 나열해야한다 -> 위상정렬 - 순위정보가 주어지면, 자기보다 낮은 등수를 가진 팀을 가리키도록 방향그래프를 만든다 - 상대적 순위가 바뀌면 간선의 방향을 반대로 바꾼다 - 위상정렬을 다시 수행하면 특이 케이스가 발생할 수 있다 - 1) 사이클이 발생하는 경우(IMPOSSIBLE) 2) 위상정렬의 결과가 1개가 아니라 여러가지인 경우(?) - 일반적인 위상정렬은 N개의 노드가 출력 노드가 N번 나오기 전에 큐가 비게 되면 ? 1번의 경우이다 => 큐의 원소가 0개 특정시점에 2개 이상의 노드가 큐에 한꺼번에 들어가면? => 정렬결과가 여러가지 => 큐의 원소가 2..

출처:: www.acmicpc.net/problem/1920 분류:: 이진탐색 1. 문제 이해 및 해결과정 2. 풀이방법 1. python #수 찾기 #https://www.acmicpc.net/problem/1920 import sys sys.stdin = open("input.txt","r") n=int(input()) a=list(map(int,input().split())) m=int(input()) find=list(map(int,input().split())) a.sort() def binary_search(x): left=0 right=n-1 while leftx: right=mid-1 else: left=mid+1 return 0 for x in find: sol=binary_search(..

출처:: www.acmicpc.net/problem/1516 분류:: 위상정렬, dp 1. 문제 이해 및 해결과정 2. 풀이방법 1. 위상정렬 #게임 개발 #https://www.acmicpc.net/problem/1516 import sys from collections import deque import copy sys.stdin = open("input.txt","r") n=int(input()) graph=[[] for _ in range(n+1)] indegree=[0]*(n+1) time=[0]*(n+1) q=deque() for i in range(1,n+1): data=list(map(int,input().split())) time[i]=data[0] for pre in data[1:-1]..

출처:: www.acmicpc.net/problem/2252 분류:: 위상정렬 1. 문제 이해 및 해결과정 1->3 2 -↑ - 사이클이 발생하지 않고 순서가 정해져 있는 작업을 수행해야 하므로 위상 정렬을 이용하면 된다. 2. 풀이방법 #줄 세우기 #https://www.acmicpc.net/problem/2252 import sys from collections import deque sys.stdin = open("input.txt","r") n,m=map(int,input().split()) #노드개수, 간선연결 graph=[[] for _ in range(n+1)] indegree=[0]*(n+1) #진입차수 q=deque() result=[] for _ in range(m): a,b=map(i..

출처:: www.acmicpc.net/problem/15685 분류:: 시뮬레이션 1. 문제 이해 및 해결과정 - 방향 0,1,2,3 = → ↑ ← ↓ - 0세대 -> 0 - 1세대 -> 0 1 - 2세대 -> 0 1 2 1 - 3세대 -> 0 1 2 1 / 2 3 2 1 - 0 1 2 1 을 거꾸로 하면 1 2 1 0 이 된다. +1을 하면 2 3 2 1 이 된다. 2. 풀이방법 1. python #드래곤 커브 #https://www.acmicpc.net/problem/15685 import sys sys.stdin = open("input.txt","r") board=[[0]*101 for _ in range(101)] dh=[0,-1,0,1] # -> 위

출처:: k 대회 기출 분류:: 그리디 1. 문제 이해 및 해결과정 1. 첫번째 풀이 1) 동전 오름차순 정렬 후 2) 모든 경우 다해보고 나온 sum을 set에 넣음 3) 1부터 차례대로 인덱스와 값이 다른 지점의 인덱스가 만들 수 없는 최소값이다 => n이 1000이므로 2^1000 이되어 시간초과가 날 수 밖에 없다. 2. 그리디 - 거스름돈 문제는 각 화폐 단위마다 무한 개의 동전이 존재한다고 가정했는데, 이 문제에서는 동전의 수가 한정적이라는 점이 다르다 - 동전을 화폐 단위 기준으로 정렬한 뒤에, 화폐 단위가 작은 동전부터 하나씩 확인하면서 target변수를 업데이트 하는 방법으로 최적의 해를 계산할 수 있다. ex) 1 2 3 8 네 개의 동전이 있다고 가정 1) 처음에는 금액 1을 만들 수..