RUBY

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

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

출처:: https://www.acmicpc.net/problem/15664 1. 문제 이해 및 해결과정 -중복되는 경우의 수를 제외한 조합 2. 풀이방법 1.조합 라이브러리 #N과 M (10) #https://www.acmicpc.net/problem/15664 import sys import itertools as it sys.stdin = open("input.txt","r") n, m = map(int, input().split()) a = list(map(int, input().split())) a.sort() for k in sorted(set(it.combinations(a,m))): #print(k) print(' '.join(map(str,k))) 2. 각 수의 개수를 이용하는 방법, D..

출처:: https://www.acmicpc.net/problem/15663 1. 문제 이해 및 해결과정 - 중복되는 경우의 수를 제외한 수열 2. 풀이방법 1. permutaion 라이브러리 이용 , set()이용 #N과 M (9) #https://www.acmicpc.net/problem/15663 import sys import itertools as it sys.stdin = open("input.txt","r") n, m = map(int, input().split()) a = list(map(int, input().split())) for k in sorted(set(it.permutations(a,m))): #print(k) print(' '.join(map(str,k))) 2. DFS, c..

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