본문 바로가기

Algorithm475

[파이썬] 백준 5567 : 결혼식 (실버2) [파이썬] 백준 5567 : 결혼식 (실버2) 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 문제 풀이 0. 방향성 생각 기준 노드인 1번 노드로부터 거리가 2 이하인 노드의 개수가 정답이다. visit을 통해 몇 번째로 방문했는지 업데이트 해주고 정답을 얻는다. 1. 입력 from collections import deque import sys input = sys.stdin.readline n = int(input()) graph = [[] for _ in range(n+1)] visit .. 2023. 7. 6.
[파이썬] 백준 1765 : 닭싸움 팀 정하기 (골드2) [파이썬] 백준 1765 : 닭싸움 팀 정하기 (골드2) 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 문제 풀이 0. 방향성 생각 친구 관계가 주어지면 항상 같은팀이 되므로 하나로 합치기. 적 관계가 주어지면 어떤 사람 P의 적 E1, E2... ,En에 대해서 모두 합쳐주면 된다. 1. 함수 정의 import sys input = sys.stdin.readline def find_parent(parent,x): if parent[x] != x : parent[x] = find_parent(parent,parent[x]) return parent[x] def union_paren.. 2023. 7. 5.
[파이썬] 프로그래머스 : 섬 연결하기 (Lv.3) [파이썬] 프로그래머스 : 섬 연결하기 (Lv.3) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0. 방향성 생각 최소 비용으로 모든 섬을 연결하는 문제. 최소 스패닝 트리랑 같은 맥락이다. 1. 함수 작성 def solution(n,costs): costs.sort(key=lambda x:x[2]) parent = [i for i in range(n+1)] def find_parent(parent,x): if parent[x] != x: parent[x] = find_parent(parent,parent[x]) return parent[x] de.. 2023. 7. 5.
[파이썬] 프로그래머스 : 거리두기 확인하기 (Lv.2) [파이썬] 프로그래머스 : 거리두기 확인하기 (Lv.2) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 0. 방향성 생각 전체 입력이 5x5이고 테케 5번처럼 사람이 최대한 많아봐야 13명이라 13C2 = 78로 이런 케이스 5개 들어와도 충분히 적은 케이스라서 완전탐색으로 구현했다. BFS로 인접거리 2인 부분까지 탐색하는 거로도 풀 수 있어보였는데 그냥 구현하는게 더 빠를거같아서 완탐 풀이. 1. 입력 받기 from itertools import combinations as C def solution(places): # 완탐 answer = [].. 2023. 7. 3.

티스토리툴바