https://www.acmicpc.net/problem/15684 이해 사다리를 모두 놓아보면서 판별해야하는 문제 DFS 를 통해 완전 탐색을 하되, 중간 가지치기를 이용한 시간을 단축해야함 구현 사다리 타기를 통해 i → i 가 모두 가능한 지 체크 하는 함수 DFS를 통해 사다리를 놓는 경로를 모두 탐색해야하는 함수 사다리 조작에 있어 사다리를 추가할 때, 추가한 사다리가 3개가 초과되면 가지치기 만약 이전에 확인된 사다리의 조작한 사다리 수가 현재 돌고 있는 사다리의 조작한 사다리 수 보다 높은 경우 가지치기 사다리를 놓음에 있어 만약 2개 혹은 3개째 사다리를 놓을 때는 이전에 놓았던 사다리 위치보다 위에 놓을 필요가 없음 코드 # 15684 사다리 조작 import sys input = sys..

개념 신장 트리(Spanning Tree) 모든 정점을 포함하면서 사이클이 없는 그래프 특징 원 그래프의 모든 정점을 포함 간선(node) 수 = 정점 수 - 1 노드 간 사이클을 형성하지 않음 한 그래프 내에서 여러 개의 신장 트리를 가질 수 있음 최소 신장 트리(Minimum Spanning Tree) 간선(node) 가중치의 합이 가장 작은 신장 트리 간선(node) 가중치가 가장 낮은 간선부터 탐색하여 신장트리를 구성하는 방식 대표 알고리즘 : Kruskal 알고리즘, Prim 알고리즘 차이점 Kruskal 알고리즘 : 간선(node)를 중심으로 하여 신장 트리를 구성 Prim 알고리즘 : 정점(spot)을 중심으로 하여 신장 트리를 구성 크루스칼(Kruskal) 알고리즘 가장 작은 가중치를 갖는..

개념 그래프 이론으로, 상호 배타적 집합(서로소집합:Disjoint-Set) 알고리즘이라고도 부름 주로 크루스칼(Krusckal) 알고리즘에서 사용하며, 순환하지 않는 트리 를 만들기 위해 사용 단계별로 이해하기 만약 아래 표와 같이 4개의 노드를 가진 서로소 집합이 있다면, 노드 번호 1 2 3 4 대표 번호 1 2 3 4 1번과 2번이 같은 집합이라면? 대표번호를 변경하여 같은 집합을 표현할 수 있음 Union 결과 노드 번호 1 2 3 4 대표 번호 1 1 3 4 아래 표와 같이 있을 때 2번은 어떤 집합에 있는지 알 수 없을까? 노드 번호 1 2 3 4 대표 번호 1 3 4 1 노드 번호를 따라가며 확인할 수 있음 2번 👉 3번 👉 4번 👉 1번 (모두 같은 집합) Find 다른 표현 노드 번호 ..

D2 Problem SW Expert Academy 새로운 버스 노선 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com Solution 1. 1번부터 1000번까지 버스정류장이 정해져 있으므로 버스정류장 리스트를 만들어 운용하자 2. 일반, 급행, 광역 버스 별 조건이 나눠져있지만, 결과적으로 지나가는 곳을 체크한 후 최댓값을 구하면 된다. 3. 조건을 확인하자. - 일반버스: 모두 지나감 - 급행버스: 시작이 짝수/홀수 에 따라 짝수/홀수 번만 지나간다. - 광역버스: - 홀수: 3의 배수이면서 10배수가 아닌 곳 - 짝수: 4의 배수인 곳 - 단, 시작점과 끝점은 반드시 포함된다! 따라서 시작과 끝점 조건을 ..

D4 problem SW Expert Academy 러시아 국기 같은 깃발 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com Solution 1. 흰색, 파란색, 빨간색의 범위를 반드시 나눠야하며, 이 중 변경할 곳의 최솟값을 찾는다. 2. 범위를 완전탐색을 통해 하나씩 수정할 곳을 확인하여 이 중 최솟값을 찾는다. Code def color(i,j,N): # White 범위 = 0 ~ i # Blue 범위 = i+1 ~ j # Red 범위 = j+1 ~ N-1 white = blue = red = 0# 각각의 개수(하나로 묶어도 됌) # white for k in range(i+1): for l in range..

D4 Problem SW Expert Academy Ladder1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com Solution 시작은 여러 곳일 수 있지만, 끝은 하나인 경우 끝부터 시작하면 편하다. 1. 시작 위치를 아래에서 찾는다. 2. 시작 위치를 기준으로 1을 따라서 간다. 3. 우선순위가 위보다 좌, 우에 있으므로 좌, 우부터 탐색한다. 4. 지나온 곳을 탐색할 수 없도록, 지나온 곳을 표시한다.(지워도 된다.) Code for test_case in range(1, 11): T = int(input()) # 인덱싱을 편하게 하기위한 0 패딩 ladder = [[0] + list(map(int, i..