https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net # 2017 삼성SW역량 테스트에 출제된 문제이다. # BT함수는 백트래킹을 이용해 N//2명으로 이루어진 '링크'팀을 구해서 answer에 append해준다. # lst는 전체 인원중에서 answer에 있는 '링크'팀을 빼면 '스타트'팀이 자동으로 구해지기 때문에 set자료형을 사용하였다. 1. lst에 1번부터 N번까지 선수들을 넣고 BT(1, 1, [0])을 실행해 answer에 '링크'팀이 될 수 있는 모든 경..
https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net # 이전에 푼 로또문제와 똑같다. # 단지 answer에 들어간 후보들 중 자음과 모음의 개수를 구해 자음이 2개이상, 모음이 1개이상인 후보들만 출력해주면 된다. import sys input = sys.stdin.readline def BT(prev, len, letters): if len == L: answer.append(letters.copy()) return for i in range(pre..
https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net # 백트래킹 문제이다. # k와 숫자들 num을 입력받은 뒤, BT함수로 백트래킹을 실행한다. # BT함수에서 len이 6이면, 숫자6개를 모두 뽑았으므로 answer에 nums.copy()를 append해주고 함수를 종료한다. # 이미 뽑은 숫자를 또 뽑을 수 없으므로, prev변수를 통해 현재 뽑은 숫자의 다음 인덱스부터 nums에 append되도록 했다. import sys inp..
https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net # 크루스칼을 이용한 MST로 풀었다. 1. 우선 N개의 좌표를 모두 입력받은 뒤, 좌표들끼리의 길이를 dist함수로 구한다. 2. graph에 (i, j, dist(i, j))를 넣어준다음 dist(i, j)순으로 오름차순 정렬해준다. 3. 이미 연결되어 있는 통로들은 union 해준 뒤 graph에서 연결이 안되어있는 통로들을 연결하며 answer에 길이를 더해준다...
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net # 무난한 MST문제이다. 마을을 두개의 마을로 분리하면서 남은 길들의 유지비가 최소가 되어야 하므로 크루스칼 알고리즘으로 최소 간선들로만 모든 집을 연결 한 뒤 가장 비용이 큰 길 하나만 없애면 된다. # 27 ~ 31줄 반복문에서 last는 항상 g[2]로 갱신되는데 graph가 비용순으로 오름차순 정렬되어 있으므로 결국 마지막 last에는 가장 비용이 큰..
https://www.acmicpc.net/problem/21870 21870번: 시철이가 사랑한 GCD 첫째 줄에 정수 $N$이 주어진다. ($1 \leq N \leq 200\,000$) 둘째 줄에 자취방의 매물번호를 의미하는 정수 $a_1, a_2, \cdots, a_N$이 주어진다. ($1 \leq a_i \leq 200\,000$) www.acmicpc.net # 유클리드 호제법의 응용과 분할정복을 이용해서 풀었다. # 흔히 유클리드 호제법을 사용한 최대공약수를 구하는 코드는 두 개의 수에 대해서만 최대공약수를 적용할 수 있었다. 하지만, 여기서는 선택한 원소들(2개 이상) 모두의 최대공약수를 구해야 한다. 따라서 gcd함수를 약간 변형해서 짰다. # 3번조건에서 선택하지 않은 원소들 S'에 대해..
https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr # 그리디문제이다. def solution(routes): # routes를 나간시간 순으로 오름차순 정렬 routes.sort(key = lambda x: x[1]) answer = 1 # camera = 현재 카메라가 설치된 위치 camera = routes[0][1] # 두번째 차량부터 마지막번째 차량까지 반복문을 돌며 현재 카메라가 설치된 시간보다 # 들어온 시간이 늦으면 camera에 현재 차량의 나간시간을 넣어주고 answer 1증가 for i in ran..
https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr # 문제를 보자마자 최소 스패닝 트리(Minimum Spanning Tree)가 떠올랐다. # 크루스칼 알고리즘으로 MST를 짰다. def solution(n, costs): answer = 0 # Union-Find함수 def find(c): if par[c] == c: return c else: par[c] = find(par[c]) return par[c] def union(a, b): a, b = find(a), find(b) par[max(a, b)]..
모르는 사이에 조금씩 조금씩..
