RUBY

출처:: https://www.acmicpc.net/problem/11053 1. 문제 이해 및 해결과정 2. 풀이방법 1. LIS #가장 긴 증가하는 부분 수열 #https://www.acmicpc.net/problem/11053 import sys sys.stdin = open("input.txt","r") n=int(input()) arr=list(map(int,input().split())) arr.insert(0,0) dp=[0]*(n+1) dp[1]=1 res=1 for i in range(2,n+1): # 1다음수부터 찾으려는 값까지 max=0 for j in range(i-1,0,-1): #내 앞의 수 까지 최대값 찾기 if arr[i]>arr[j] and dp[j]>max: max=dp[..

출처:: https://www.acmicpc.net/problem/1261 1. 문제 이해 및 해결과정 - Floodfill 대로 BFS를 쓰되, 최단거리를 저장할 때 0이면 거리가 0더해지고 1이면 1더하면 최적의 경로에 1의 개수가 몇개인지 구할 수 있다. - 우선순위를 높이기 위해서 0이라면 왼쪽으로 append하여 우선순위를 높였다. -입력이 붙어있을 때 아래코드로 하면된다. board = [list(map(int, input())) for _ in range(n)] #붙어있는 입력 받기 : input=sys.stdin.readline 때문에 오류가 났었다. 입력이 붙어있을경우, 이 코드를 쓰면 안된다. 2. 풀이방법 1. 가중치가 다른 BFS #알고스팟 #https://www.acmicpc.ne..

출처:: https://www.acmicpc.net/problem/13913 1. 문제 이해 및 해결과정 - 최적의 이동경로까지 출력해야한다. - path[다음위치] = cur(현재) , path에 방문했던 위치를 저장한다. - k에 도착하면 backtracking 해서 출발위치까지 p 에 최적 이동경로를 저장한다. - p는 backtracking 한 것이므로 출발위치 추가해서 reverse해야한다. - if cur==k: print(time[cur]) p=[] print(path) while cur!=n: p.append(cur) cur=path[cur] print(p) 2. 풀이방법 1. BFS #숨바꼭질4 #https://www.acmicpc.net/problem/13913 import sys fr..

출처:: https://www.acmicpc.net/problem/13549 1. 문제 이해 및 해결과정 - 우선순위 를 생각해야한다. - 이 문제는 가중치가 있는 BFS이다. - 0초로 이동하는 것은 X-1,X+1 (1초) 보다 우선순위를 가진다. - 순간이동을 하면(2X) , deque의 뒤에 추가한다. - X-1,X+1, deque의 앞에 추가한다. - 이 순서로 추가하면, popleft로 인해 앞에서 부터 pop하여 cur을 찾으므로 우선순위에 따라 이동할 수 있다. 2. 풀이방법 1. BFS #숨바꼭질3 #https://www.acmicpc.net/problem/13549 import sys from collections import deque sys.stdin = open("input.txt"..

출처:: https://www.acmicpc.net/problem/1707 1. 문제 이해 및 해결과정 - 이분그래프의 개념이 문제만 보고 제대로 이해되지 않았다. - 이분 그래프는 인접한 정점끼리 서로 다른색으로 칠해서 모든 정점을 두가지 색으로만 칠할 수 있는 그래프이다. - 즉, 그룹은 두그룹으로 나누어진다. 1. 정점에 1~n까지 차례로 방문하고 색칠한다. (1과 -1로 칠했음) 2. 방문하지않았다면 check==0 ,이전의 정점과 다른색을 색칠한다. 3. 방문했었는데 새로운 곳이 내 색깔과 같다면 이분그래프가 아니다. - BFS로 풀 시, 주의할 점 DFS에서는 깊이순으로 color / -color 로 색깔을 칠할 수 있지만 BFS에서는 레벨별로 색깔을 칠하는 것이다. 그러므로 현재 칠해진 색깔..

출처:: https://www.acmicpc.net/problem/13023 1. 문제 이해 및 해결과정 - DFS의 깊이를 구하는 문제 - 깊이가 4이상인가? 2. 풀이방법 1.DFS #ABCDE #https://www.acmicpc.net/problem/13023 import sys sys.stdin = open("input.txt","r") input=sys.stdin.readline sys.setrecursionlimit(10**6) def DFS(v,depth): global flag visited[v]=1 if depth>=4: #깊이가 4이상이면 참 flag=1 return for i in adj[v]: if visited[i]==0: DFS(i,depth+1) visited[i]=0 #다음..

출처:: https://www.acmicpc.net/problem/7562 1. 문제 이해 및 해결과정 - 이동 횟수 기록하는 방법 visited[nh][nw]=visited[h][w]+1 2. 풀이방법 1.BFS #나이트의 이동 #https://www.acmicpc.net/problem/7562 import sys from collections import deque sys.stdin = open("input.txt","r") dh=[-2,-1,1,2,2,1,-1,-2] dw=[1,2,2,1,-1,-2,-2,-1] t=int(input()) def BFS(h,w): Q=deque() Q.append((h,w)) visited[h][w]=1 if h==eh and w==ew: return while Q:..

출처:: https://www.acmicpc.net/problem/15666 1. 문제 이해 및 해결과정 -중복조합 2. 풀이방법 #N과 M (12) #https://www.acmicpc.net/problem/15666 import sys sys.stdin = open("input.txt","r") def DFS(L,s): if L==m: for x in res: print(x,end=' ') #print(' '.join(map(str,res))) print() else: for i in range(s,len(a)): res[L]=a[i] DFS(L+1,i) if __name__=="__main__": n, m = map(int, input().split()) a = sorted(set(list(map(..