본문 바로가기

전체 글

 (191)
[Python] 위상정렬 - 14676. 영우는 사기꾼?(골3) https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net >>문제 포인트 1) 건물들은 중복으로 지을 수 있음을 고려 2) 치트키를 판단할 수 있는 상황을 잘 확인하여야 함 - 치트키 상황1. 건물 파괴할 때 : 파괴대상인 건물이 안지어져 있을때 - 치트키 상황2. 건물 지을때 : 모든 선행 건물이 안지어져 있을때 3) 선행건물의 판단여부(indegree) - 위상정렬의 indegree 행으로 선행건물 지음 여부를 판단 ..
[Python] 그리디- 1946. 신입사원 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net >> 문제 포인트 이 문제가 헷갈리는 이유는 기준점이 두개이기 때문이다. 즉, 서류심사의 랭킹과 면점심사의 랭킹을 동시에 고려해주어야 하기 때문에 문제 풀이에 막힘이 있었다. 따라서, 정렬을 통해 2가지 기준점을 한가지로 줄일 필요가 있다. 예를 들어 서류|면접 1 | 4 3 | 2 4 | 1 5 | 5 2 | 3 이렇게 정리되어 있는 표의 경우 두가지 기준에 조건을 고려해야..
[Python] 그리디- 1715. 카드 정렬하기(골4) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net >>문제 포인트(자료구조) : 작은 값부터 출력이 가능하도록 최소힙 사용 : 계산기 예제처럼 최소1+ 최소2를 더해주고 더한값을 다시 push : result값 출력 from heapq import heappush, heappop heap=[] n= int(input()) for _ in range(n): heappush(heap,int(input())) result=0 while(..
[Python] 자료구조 - 25192. 인사성 바른 곰곰이 (실4) https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net >>문제포인트 : 하나씩 처리하게 되면 시간 초과가 남 : ENTER가 될 때마다 고유 아이디 값의 수만을 바로바로 더해서 시간을 아끼자 n= int(input()) p=[] result=0 for _ in range(n): name= input() if name =='ENTER': result+= len(set(p)) p=[] else: p.append(name) resul..
[Python] 그리디-14916. 거스름돈 (실5) https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제포인트 - 5로 최대한 많이 나누어주고 나머지가 짝수인지 판별 - 짝수가 아니라면 5의 개수를 하나씩 줄이며 가능여부 판단하기 - range를 뒤로 가게 하여 가능여부 최대한 빠르게 판별하는 것이 관건 #14916 #최대한 5 로 많이 가져가고 하나씩 줄이며 2로 가능한지 보기 n= int(input()) result=-1 for i in range(n//5,-1,-1): if (n-i*5)%2==0: #나머지가 짝수라면 ->가능 result= i+ (n-i*5)//2 break print(result)
[Python] 위상정렬 - 14567. 선수과목 (골5) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net >>문제 포인트 : 위상정렬 문제인데 위상정렬로 안품 : A
[Python] Kruskal - 2287. 행성터널[플5] https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net >> 문제 핵심 포인트 -n개의 행성간의 nC2 조합을 만들어 거리 구하기-> 메모리 초과 - 결국 cost로 주어진 |x1-x2|, |y1-y2|, |z1-z2|를 cost로 하여 각각의 간격을 넣어주어야 함 3(n-1)번만큼 - 가까운 행성별 정렬이 중요 => 이걸 문제를 보고 바로 떠올릴 수 있을까? def find_parent(parent, x): if pa..
[Python] 그리디 - 2212. 센서 (골5) https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net >>문제 포인트 - 이어진 간격에서 m-1개를 없애면 m-1개의 끊어짐이 생김= m개의 묶임이 생김 ex) 5 묶음 간에는 4개의 간격이 존재 => 먼 간격부터 기지국의 수만큼 끊어내어 기지국 수만큼 묶음을 만들기 #아이디어 : 가장 짧은 간격부터 n-1개를 택하면 됨 #=> 가장 긴 간격부터 n개를 제거함 n= int(input()) #센서 개수 m= int(input(..

티스토리툴바