그래프, BFS/DFS 문제https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 💡 풀이코드 (성공 - MST Prim)import heapqdef solution(n, computers): answer = 0 graph = [[] for _ in range(len(computers) + 1)] # graph 만들기 for i in range(len(computers)): for j in range(len(computers)): ..

MST 문제https://www.acmicpc.net/problem/1647접근 방식문제 분석마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 임의의 두 집 사이에 경로가 항상 존재한다.-> N개의 노드와 M개의 간선을 가지는 양방향의 가중치 그래프일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다.-> MST (1. 불필요한 간선 제거 2. 최소 신장 ..

BFS 문제https://www.acmicpc.net/problem/9019시간 초과1. 문자열 변환 및 조작 연산은 느리다.문자열 변환문자열 변환(정수 -> 문자열 -> 정수)이 빈번하게 발생하면 누적된 비용이 상당히 커질 수 있다.문자열 슬라이싱슬라이싱 연산은 새로운 문자열을 생성하는 작업이므로, 메모리 할당 및 복사가 발생하며 매우 느린 작업이다.문자열 슬라이싱의 시간 복잡도는 O(k)로 비용이 크다. 이 때, k는 슬라이스된 문자열의 길이이다. 문자열 코드 (시간 초과 + 오답)while queue: val, dslr = queue.popleft() if val not in visited: visited.add(val) queue.append(((2 * val)..

그래프, BFS/DFS 문제https://www.acmicpc.net/problem/21736 💡 풀이코드 (성공 - DFS 1)import sys sys.setrecursionlimit(10 ** 9) r, c = map(int, sys.stdin.readline().split())graph = []start = []visited = [[False] * c for _ in range(r)]dy = [0, -1, 0, 1]dx = [1, 0, -1, 0]cnt = 0for i in range(r): l = list(sys.stdin.readline().strip()) for j in range(c): if l[j] == "I": start.append((i,..

그래프, BFS/DFS 문제https://www.acmicpc.net/problem/1967 트리의 지름 트리의 지름이란?어떤 두 노드를 선택해서 당겼을 때, 가장 길게 늘어나는 경우의 두 정점 사이의 거리를 말한다.즉, 트리의 지름이란 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다.위의 그래프에서 9 노드와 12 노드의 사이의 거리는 45이며, 이 경로가 트리의 지름이 된다. 트리의 지름을 구하는 순서1. DFS를 통해 임의의 정점(x)로부터 가장 먼 정점(y)를 구한다.2. DFS를 통해 구해진 (y) 정점으로부터 가장 먼 정점(z)를 구한다.3. (y) 정점과 (z) 정점을 잇는 경로가 트리의 지름이 된다.  💡 풀이코드 (성공 - DFS)# DFS# visited 초기화 주의 im..

BFS, DFS 문제https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 접근방식숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 구하기 -> DFS로 풀어 모든 경우의 수 탐색특정 숫자를 변환하였을 때의 타겟 넘버를 만족하는지를 비교하여 가짓수(경우의 수) 구하는 것이므로 return값 설정 풀이코드  (실패, 오답-cnt를 전역변수로 선언)import syssys.setrecursionlimit(10 ** 9)cnt = 0oper = [1, ..