분류 전체보기
BFS&DFS_심화19) 연산자 끼워 넣기 _ python
문제링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 코드 import sys input = sys.stdin.readline n = int(input()) num = list(map(int, input().split())) op = list(map(int, input().split())) maximum = -1e9 minimum = 1e9 def dfs(depth, total, p..
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: 모든 노드를 방문하는 것이 목적입니다. 경로 ..