본문 바로가기

코딩 테스트124

DFS p.142 DFS(Depth First Search) : 깊이 우선 탐색 * 스택을 사용 = 재귀 함수 사용 * graph를 인접 리스트 사용 * visited로 방문했는지 여부 확인 [동작 과정] 1. 탐색 시작 노드를 스택에 삽입하고 방문처리 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼내기 3. 2번 과정을 스택에 남아있는게 없을 때까지 반복 (일반적으로 인접 노드 중 방문하지 않은 노드가 여러개 있을 시, 번호가 낮은 순서부터 처리) def dfs(graph, v, visited): visited[v]=True print(v, end=' ') for i in graph[v]: if.. 2021. 1. 25.
외벽 점검 p. 335 from itertools import permutations def solution(n, weak, dist): length = len(weak) for i in range(length): weak.append(weak[i] + n) answer = len(dist) + 1 # 0부터 length-1까지를 시작점으로 설정 for start in range(length): # 친구를 나열하는 모든 경우의 수 각각에 대해서 확인 for friends in list(permutations(dist, len(dist))): count = 1 # 투입할 친구의 수 # 해당 친구가 점검할 수 있는 마지막 위치 position = weak[start] + friends[count - 1] # 시작점부터.. 2021. 1. 23.
치킨 배달 p.332 from itertools import combinations N,M=map(int, input().split()) home=[] chicken=[] for i in range(N): data=list(map(int, input().split())) for j in range(len(data)): if data[j]==1: # 집 home.append((i,j)) elif data[j]==2: # 치킨집 chicken.append((i,j)) candidates=list(combinations(chicken, M)) def get_sum(candidates): result=0 for hx, hy in home: temp=1e9 for cx,cy in candidates: temp=min(tem.. 2021. 1. 22.
기둥과 보 설치 programmers.co.kr/learn/courses/30/lessons/60061 p.329 def possible(answer): for x,y,stuff in answer: # 기둥 확인 if stuff == 0: if y==0 or [x-1,y,1] in answer or [x,y,1] in answer or [x,y-1,0] in answer: continue else: return False elif stuff == 1: if [x,y-1,0] in answer or [x+1,y-1,0] in answer or ([x-1,y,1] in answer and [x+1,y,1] in answer): continue else: return False return True def solution(n.. 2021. 1. 20.
뱀 p.327 방법 1 N = int(input()) # 보드의 크기 K = int(input()) # 사과의 갯수 apple_p = [] # 사과의 위치 for i in range(K): apple = list(map(int, input().split())) apple_p.append(apple) L = int(input()) d = [] # 방향을 바꾸는 시간과 바뀔 방향 for i in range(L): td = list(map(str, input().split())) d.append(td) d.sort(key=lambda x: int(x[0])) dcount = 0 count = 0 # 시간을 세는 변수 dire = [(0, 1), (1, 0), (0, -1), (-1, 0)] # 동 남 서 북 (L.. 2021. 1. 19.
자물쇠와 열쇠 p.325 def rotated(a): n=len(a) m=len(a[0]) result=[[0]*n for _ in range(m)] for i in range(n): for j in range(m): result[j][n-i-1]=a[i][j] return result def check(new_lock): for i in range(len(new_lock)//3, len(new_lock)//3*2): for j in range(len(new_lock)//3, len(new_lock)//3*2): if new_lock[i][j]!=1: return False return True def solution(key, lock): key_len=len(key) lock_len=len(lock) # 자물쇠의 크.. 2021. 1. 19.

티스토리툴바