코딩테스트
BFS&DFS_심화18) 괄호변환 _ python
문제링크 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 def divide(p): openP = 0 closeP = 0 for i in range(len(p)): if p[i] == '(': openP += 1 elif p[i] == ')': closeP += 1 if openP == closeP: return p[:i+1],p[i+1:] def check(u): stack = [] for i in u: if i == '(': stack..
BFS&DFS_심화17) 경쟁적 전염 _ python
문제링크 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 코드 # 경쟁적 전염 - bfs from collections import deque N, K = map(int, input().split()) graph = [] virus = [] for i in range(N): graph.append(list(map(int, input().split()))) for j in range(N): if graph[i][j]..
BFS&DFS_심화16) 연구소 _ python
문제 링크 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 코드 from itertools import combinations from collections import deque import copy n, m = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) virus = [] # 바이러스의 좌표 empty = [] # ..
BFS&DFS_심화15) 특정 거리의 도시 찾기 _ python
문제 링크 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 코드 # https://www.acmicpc.net/problem/18352 from collections import deque import sys f = sys.stdin.readline n, m, k, x = map(int, f().split()) graph = [[] for _ in range(n+1)] d..
백트래킹(Backtracking)
💡 백트래킹(Backtracking)이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 용어 설명 유망함(promising) : 진행 중인 경로가 해답을 찾을 가능성이 있음을 의미 유망하지 않음(non-promising) : 진행 중인 경로가 해답을 찾을 가능성이 없음을 의미 가지치기(pruning) : 유망하지 않은 하위 트리를 자르는 것 백트래킹 vs DFS ? 공통점 두 방법 모두 깊이 우선 탐색 (DFS, Depth-First Search)을 이용하여 탐색합니다. 재귀 함수를 사용하는데, 이 때 스택(stack) 메모리를 사용하여 작동합니다. 차이점 목적 DFS: 모든 노드를 방문하는 것이 목적입니다. 경로 ..
3주차 - DFS/BFS
그래프 탐색 알고리즘 : DFS / BFS 탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다. 대표적인 탐색 알고리즘으로 DFS와 BFS가 있다. 스택(Stack) 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출..