1. 문제1 18310번: 안테나 (acmicpc.net) 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 2. 풀이 수직선 위에 위치한 점 중에서 모든 점까지 거리 합이 최소인 점의 좌표는 어떻게 찾을 수 있을까 직관적으로는 점의 좌표를 오름차순으로 정렬하고 당연히 중앙에 위치한 점이 모든 점까지 거리 합이 최소인 점일텐데 왜 그런지를 한번 생각해본다면.. 수직선 위에 집이 있을때, 맨 왼쪽 집에서부터 시작해서 오른쪽으로 한칸씩 이동한다고 생각해보자 1부터 시작해서 오른쪽으로 이동한다고 해보면... 왼쪽 집 1개와 거리가 +1 하지..
1. 문제1 5052번: 전화번호 목록 (acmicpc.net) 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 2. 풀이1 한 번호가 다른 번호의 접두어인 경우가 없어야한다 번호를 트라이에 순차적으로 저장하다가, 마지막을 나타내는 플래그 '*'을 만난다면, 지금 저장하려는 번호는 다른 번호의 접두어가 될 것이다 class Trie: def __init__(self): self.head = {} def add(self,word): current_node = self.head #문자열의 ..
1. 문제 25947번: 선물할인 (acmicpc.net) 25947번: 선물할인 입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 100\,000$), 예산을 나타내는 양의 정수 $b$ ($1 ≤ b ≤ 10^9$), 반값 할인을 받을 수 있는 최대 선물의 수를 www.acmicpc.net n개의 선물 가격이 있고, 예산이 b원일때, 반값 할인을 a번 받을 수 있다면, 최대로 살 수 있는 선물의 개수는..? 2. 풀이 가장 먼저 생각한건... 가격표를 정렬하고 큰 가격부터 a개는 반값으로 할인시킨다음에, 다시 정렬하고 b원만큼 사는 것 from sys import stdin n,b,a = map(int,stdin.readline().split()) p..
1. 문제 1541번: 잃어버린 괄호 (acmicpc.net) 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 수식에 괄호를 쳐서 결과를 최소로 만드는 문제 2. 풀이 수식에 +,-만 나온다는 점을 생각하면.. 이 수식이 최소가 될려면?? +를 먼저 계산해서, 각 항을 최대로 만들어줘야한다. 그래야 -에 의해 최소가 되겠지 그래서 -로 수식을 split해주고... split된 리스트를 순회해서... 각 원소를 int()로 바꿔본다. int()로 바꿀때 에러가 나거나 나지 않거나 둘중 하나다. 에러가 나지..
1. 문제 2777번: 숫자 놀이 (acmicpc.net) 2777번: 숫자 놀이 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 양의 정수 N이 주어진다. (1 7: print(-1) continue else: prime[n] += 1 a,b = divmod(prime[2],3) if b == 2: b = 1 elif a == 2 and b == 0: a = 1 c,d = divmod(prime[3],2) answer = a+b+c+d+prime[5]+prime[7] print(answer) 2와 3의 경우에 2를 3번 곱한 8까지 압축시켜야하고 3의 경우 2번 곱한 9까지 압축시켜야하고 5,7은 그대로 두면 되고 근데 또 압축이 가능한 경우가 2*..
1. 문제 16562번: 친구비 (acmicpc.net) 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 2. 풀이 어렵게 생각하지 말고.. 먼저 union find 함수를 작성하자 먼저 parent를 찾는 find함수 def find_parent(x,parent): if x != parent[x]: parent[x] = find_parent(parent[x],parent) return parent[x] 다음 union을 수행하는 함수 def ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
