개구리의 개발 블로그 개구리의 개발 블로그

백준 10775번 공항 파이썬 문제 링크 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 한 번에 푼 문제는 아니지만 단계적으로 잘 풀어서 기분이 좋았다. 유니온 파인드를 이용해서 풀어야 하는 문제다. 처음에는 그리디하게 가능한 가장 번호가 큰 공항에 비행기를 배치했다. 새로운 비행기에 할당된 공항이 중복되면 기존에 있던 비행기는 왼쪽으로 한 칸씩 밀어서 배치가 가능하다. 이를 이중 반복문을 통해 구현했다. 1. 코드 (greedy, 시간 초과) # 공항 G, P = int(i..

백준 1765번 닭싸움 팀 정하기 파이썬 문제 링크 - https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net union-find 문제는 해당 카테고리의 문제라는 것을 알고 있다면 쉽게 풀 수 있다. 하지만 문제를 보고 union-find로 풀어야겠다는 아이디어를 떠올리는 것은 어려울 수 있다. 팀을 만들어야 되는 문제이고 팀의 개수를 물어보았기 때문에 union-find로 풀면 될 것 같았다. 1. 풀이 팀을 만들기 위해 친구는 입력값을 받을 때 모두 union 한다. 원수인 경우 인접 리스트를 통해 서로 원수 관계인 것을..