느낌표 공장

DFS 풀이 # (이전의 색, 여태까지 칠한 칸 수, 현재 인덱스) # 1행부터 n-2행까지 (마지막이 n-1행) 실행함 def paint(before, cnt, i): global answer # 지금까지 칠한 칸 수가 이미 answer에 들어있는 값보다 작으면 볼 필요 없다. 끊자 if answer 다음에 칠할 수 있는 색은 흰색, 파란색 if before == 'W': ..

Stack 활용하여 푼 코드 t = int(input()) for idx in range(1, t+1): # 노드 개수 v, 간선개수 e v, e = map(int, input().split()) # 인접행렬 만들기 (인덱스 사용 편하게 하기 위해 range(v+1) 해주었음) arr = [[0 for _ in range(v+1)] for _ in range(v+1)] # 인접행렬에 방향성 표시하기 for _ in range(e): # 출발노드 d, 도착 노드 a d, a = map(int, input().split()) arr[d][a] = 1 # 한방향이므로 반대로도 설정해주면 (arr[a][d] == 1) 안됨 # 경로 존재 확인할 출발 노드 s, 도착 노드 g s, g = map(int, inpu..

재귀 방식으로만 푼 코드 # 규칙 (입력 받은 숫자 n) # n-20 * 2 + n - 10 # 맨 처음, 즉 n = 10일때부터 구해나가서, 입력받은 숫자 n까지 도달할때까지 구한다. def paper_use(n): if n == 10: return 1 elif n == 20: return 3 else: return 2 * paper_use(n-20) + paper_use(n-10) t = int(input()) for t in range(1, t+1): n = int(input()) print('#{} {}'.format(t, paper_use(n))) DP 코드 (점화식 이용) # 점화식을 이용하기 위해 n의 크기마다 경우의 수를 저장할 리스트 만들기 # 규칙이 (현재의 수-2) * 2 + (현재의..

def dfs(s): global answer visited[s] = 1 # 현재 노드 방문 처리 for i in arr[s]: if i == 99: # 목표 노드 99까지 도달했으면 answer = 1 answer = 1 if answer: # 이미 목표 노드 도달했으면 재귀 들어가지마 return if not visited[i]: # 목표노드 가는 중이고, 방문한 곳 아니라면 재귀 dfs(i) for idx in range(1, 11): # 테스트 케이스 순서 idx, 순서쌍의 개수 n idx, n = map(int, input().split()) # 순서쌍 리스트 pair_list = list(map(int, input().split())) arr = [[] for _ in range(100)] #..

# 벡터설정 (좌우상) # 좌우는 상관없지만, 위로 가는 것이 마지막이어야 한다. # 사다리에서는 좌우 탐색이 우선이기 때문 dx = [-1, 1, 0] dy = [0, 0, -1] for idx in range(1, 11): n = int(input()) # 사다리 받아오기 ladder = [list(map(int, input().split())) for _ in range(100)] # 목표지점부터 시작하면 한번만 탐색하면 된다. x = ladder[99].index(2) # 목표지점(2)의 인덱스 찾기 y = 99 # 맨 밑에서부터 시작하는 y좌표 k = 0 # 방향 설정을 담당하는 K # y가 0인덱스까지 도달할때까지 반복한다. while y > 0: nx = x + dx[k] # 이동하고자 하는..

def solution(tickets): path = {} for (start, end) in tickets: path[start] = path.get(start, []) + [end] for r in path.keys(): path[r].sort(reverse=True) answer = [] stack = ["ICN"] while stack : now = stack[-1] if now not in path or len(path[now]) == 0 : answer.append(stack.pop()) else : stack.append(path[now][-1]) path[now] = path[now][:-1] return answer[::-1] 풀이 1. 딕셔너리로 변환한 tickets를 while문을 돌..

DFS & BFS 개념 ☞ 2021.06.20 - [Algorithm/개념] - DFS / BFS 1. DFS def DFS(n, com, visited, computers) : visited[com] = True for j in range(n) : if com != j and computers[com][j] == 1: if visited[j] == False : DFS(n, j, visited, computers) def solution(n, computers): visited = [False for i in range(n)] answer = 0 for com in range(n) : if visited[com] == False : DFS(n, com, visited, computers) answer ..

DFS(Depth-First Search) : 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘. 스택 자료구조 혹은 재귀 함수를 이용한다. ✔︎ 동작과정 탐색 시작 노드를 스택에 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 더 이상 2번의 과정을 수행할 수 없을 때까지 수행한다. ✔︎ 깊이 제한 : 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위함이다. 깊이 제한에 도달할 때까지 목표 노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다...