RUBY

출처:: www.acmicpc.net/problem/1406 분류:: 스택 1. 문제 이해 및 해결과정 - 두 개의 스택을 이용해서 풀 수 있으며 스택의 top이 커서가 된다. 투스택 - 스택1번이 커서 왼쪽 , 스택 2번이 커서 오른쪽이 된다 - 1. 스택 두개를 만든다. - 2. 초기 문자열을 스택1번에 넣는다 - L : 커서 왼쪽으로, 첫번째 스택의 top을 두번째 스택으로 push - B : 커서왼쪽의 문자삭제 , 첫번째 스택의 top을 pop - D : 커서를 오른쪽으로 , 두번재 스택의 top을 첫번재 스택으로 push - P : 문자하나를 추가한다. => 스택1번에 append 2. 풀이방법 1. 투 스택 #에디터 #https://www.acmicpc.net/problem/1406 impor..

출처:: www.acmicpc.net/problem/10164 분류:: dp 1. 문제 이해 및 해결과정 - k가 0이 아니라면, 빨간 네모의 경우와 파란네모의 경우를 찾아 각각 곱해주면 되는데 - 파란 네모의 경우는 번호(8)를 기준으로 다시 초기화되어서 dp배열을 만들게 되므로 곧 다시 빨간 네모dp테이블과 같다 2. 풀이방법 1.dp #격자상의 경로 #https://www.acmicpc.net/problem/10164 import sys sys.stdin = open("input.txt","r") n,m,k=map(int,input().split()) dp=[[0]*(m+1) for _ in range(n+1)] dp[0][1]=1 cnt=1 for i in range(1,n+1): for j in..

출처:: www.acmicpc.net/problem/6118 분류:: 다익스트라 , bfs 1. 문제 이해 및 해결과정 - 간선의 비용이 모두 0이기 때문에 BFS로도 풀 수 있다 2. 풀이방법 1. 다익스트라 #숨박꼭질 #https://www.acmicpc.net/problem/6118 import sys import heapq sys.stdin = open("input.txt","r") n,m=map(int,input().split()) graph = [[] for _ in range(n+1)] visited=[False]*(n+1) INF=1e9 dist=[INF]*(n+1) for i in range(m): a,b=map(int,input().split()) graph[a].append((b,1)..

출처:: www.acmicpc.net/problem/1789 분류:: 1. 문제 이해 및 해결과정 2. 풀이방법 1. #수들의 합 #https://www.acmicpc.net/problem/1789 import sys sys.stdin = open("input.txt","r") n=int(input()) #x(x+1)/2 = n x=1 while(x*(x+1)/2 n: break num+=1 print(cnt-1) 3. 오답원인 4. 알게된 점

출처:: www.acmicpc.net/problem/2294 분류:: dp 1. 문제 이해 및 해결과정 - 문제 예시의 경우, dp[i - 1], dp[i - 5], dp[i - 12] 중 min값에 1을 더하면 된다 - dp[0]=0 2. 풀이방법 1. dp #동전2 #https://www.acmicpc.net/problem/2294 import sys sys.stdin = open("input.txt","r") n,k=map(int,input().split()) coin = [ int(input()) for _ in range(n)] INF=100001 #INF라면 만들수 없는 숫자 dp=[INF]*(INF) dp[0]=0 #꼭 필요, 0원을 만들 수 있는 방법은 0개 coin.sort() for i..

출처:: https://www.acmicpc.net/problem/1463 분류 ::: dp 1. 문제 이해 및 해결과정 2. 풀이방법 1. DP(dynamic programming) -bottomup #1로 만들기 #https://www.acmicpc.net/problem/1463 import sys sys.stdin = open("input.txt","r") n=int(input()) dp=[0]*(n+1) for i in range(2,n+1): #1뺴는 경우 dp[i]=dp[i-1]+1 #2로 나누어 떨어지는 경우 if i%2==0: dp[i]=min(dp[i],dp[i//2]+1) #3으로 나누어 떨어지는 경우 if i%3==0: dp[i]=min(dp[i],dp[i//3]+1) print(dp..

출처:: 유명알고리즘 대회 분류:: 1. 문제 이해 및 해결과정 - 메세지를 보내고자 하는 도시 C가 출발점이 된다. #input 3 2 1 1 2 4 1 3 2 #output 2 4 2. 풀이방법 1.다익스트라 #전보 # import sys import heapq sys.stdin = open("input.txt","r") input=sys.stdin.readline n,m,start=map(int,input().split()) graph=[[] for _ in range(n+1)] INF=1e9 dist=[INF]*(n+1) visited=[False]*(n+1) for _ in range(m): x,y,z=map(int,input().split()) #x에서 y로 이어지는 통로에서 메세지 전달시간이..

출처:: www.acmicpc.net/problem/14620 분류:: dfs 1. 문제 이해 및 해결과정 - 모든 경우 탐색 dfs - 가능한 열매 시작점은 1~n-2,1~n-2 까지임 - 아직 선택되지 않은 열매라면, 현재 열매에서 꽃잎까지 비용모두 저장하고(cost), sum(기존값)에 더해준다 - 선택되었던 것을 취소 - cnt==3 (모두선택되면), 가능한 값들 중 최소값 저장 2. 풀이방법 1. dfs #꽃길 #https://www.acmicpc.net/problem/14620 import sys sys.stdin = open("input.txt","r") n=int(input()) board=[list(map(int,input().split())) for _ in range(n)] #가격 v..