728x90 Algorithm98 [SWEA/Python] 5249. 최소 신장 트리 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 크루스칼 알고리즘을 사용해서 풀었다. 간선을 가중치를 기준으로 내림차순 정렬을 해준다. 노드1, 노드2의 조상 노드가 다르다면 사이클이 만들어지지 않으므로 연결해준다. 3번의 과정을 반복하며 가중치를 더해서 출력해준다. 📌 코드 import sys sys.stdin = open('input.txt') def find_set(x): if x != parents[x]: parents[x] = find_set(parents[x]) return parents[x] def.. 2021. 10. 14. [SWEA/Python] 5248. 그룹 나누기 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 하나의 조를 집합으로 생각하고 각 집합마다 집합을 대표하는 수를 parents에 저장한다. (초기값은 자기자신) 입력 값에 따라 union함수를 실행시켜서 집합을 합친다. 모든 조를 다 짠 후, 전체 원소에 대해 find_set 함수를 실행해서 대표 숫자를 업데이트 해준다. 대표 숫자를 set으로 만들어서 중복값을 없애주고 길이를 출력하면 완성된 조의 숫자가 된다. (parents에 0도 포함되므로 1은 빼준다.) 📌 코드 import sys sys.stdin =.. 2021. 10. 14. [SWEA/Python] 5247. 연산 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 bfs를 활용해서 각 계산값에 접근하는 방식으로 풀었다. 최대 재귀 깊이를 넘어가길래 가지치기를 해줬는데, 첫 번째 코드처럼 append하고 not in으로 탐색하는 방식은 시간초과가 났다. 그래서 두 번째 코드처럼 처음부터 모든 숫자만큼 리스트를 만들어주고 숫자가 중복되지 않도록 이미 나온 숫자는 1로 바꿔줬다. 📌 코드 from collections import deque def find_M(N): queue = deque() queue.append((N, 0.. 2021. 10. 14. [BOJ/Python] 14981. 톱니바퀴 📌 문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 📌 문제 접근 방법 톱니바퀴의 상태를 deque을 이용해서 받아서 원형큐라고 생각하고 코드를 구현했다. 시계방향으로 회전일 경우, 맨 마지막 원소를 빼서 맨 첫 번째에 삽입해줬다. 반시계방향으로 회전일 경우, 맨 첫 번째 원소를 빼서 맨 마지막에 삽입해줬다. 그리고 회전이 일어나는 경우, 앞 뒤 바퀴와 원소를 비교해서 맞물린 부분이 다르면 해당 바퀴도 재귀로 회전을 시켜줬다. 이 때,.. 2021. 10. 14. 이전 1 ··· 15 16 17 18 19 20 21 ··· 25 다음 728x90