본문 바로가기

전체 글

 (62)
백준 1439 : 뒤집기(그리디) www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net Input : 0,1 문자열 S 목표 : n번 뒤집어서 1-문자열 or 0-문자열로 만드는 것 규칙 : i 번째를 잡고, 그 이후를 모두 뒤집기만 가능 Output: 최소 n i=0을 잡느냐 안잡느냐가 문제인 듯 우선 반복되는 문자열을 제거, 01010, 10101 식으로 만들어도 뒤집어야 하는 횟수는 같음 (이유: 붙어있는 000 or 111은 형태가 같이 바뀌기 때문에 몇개가 붙어있어도 상관이 없음) len..
백준 17262 : 팬덤이 넘쳐흘러(그리디)*** www.acmicpc.net/problem/17262 17262번: 팬덤이 넘쳐흘러 선물 포장 공장을 말아먹은 욱제는 계곡에서 백숙을 파느라 학교에 자주 가지 못한다. 하지만 월클의 인생은 피곤한 법! 욱제는 지금처럼 힘든 시기에도 자신을 기다리는 5조5억명의 열렬한 팬 www.acmicpc.net Input : 만나야 하는 팬의 수 N [ s, e ] 팬이 머무는 시간의 수 Output: 머무르는 최소의 시간 풀이: 직관적으로 보면, start = 제일 일찍 집 가는 사람 ~~ end = 제일 늦게 오는 사람으로 하면 된다. 하지만, 위 문장을 그대로 코드화 하면 다음과 같은 경우에 문제가 생긴다. (start = 보라색 포인트, end = 파란색 포인트) 가 되어야 하는데, (start = 보라색 포..
Adam Optimizer Adam Optimizer 원래의 Gradient descent 는 항상 learning rate이 같음(step, 변수에 상관 없이) 이를 개선한 것이 Ada, RMSProp optimizer이다. 이 두개의 장점을 구현한 것이 Adam optimizer이다. 초기 설정 Objective function : $f(\theta)$ ​ $f(\theta)$ 를 최소화 시키는 것이 목적. gradient : $g_t = \nabla_{\theta} f(\theta)$ $$\beta_1 , \beta_2 $$ : Exponential decay rates for the moment estimates $m_t , v_t $ : momentum, 이전에 사용한 stepsize를 기억하는 역할, 물리의 관성과 비슷..
백준 17224 : APC는 왜 서브태스크 대회가 되었을까?(그리디) www.acmicpc.net/problem/17224 17224번: APC는 왜 서브태스크 대회가 되었을까? 2019년 올해도 어김없이 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)가 열렸다! 올해 새롭게 APC의 총감독을 맡게 된 준표는 대회 출제 과정 중 큰 고민에 빠졌다. APC에 참가하는 참가 www.acmicpc.net 프로그래밍 대회에 문제 N개가 다음 조건으로 주어진다. 1. 문제는 난이도 순으로 배열되어 있음. 2. 모든 문제는 easy/hard 버전으로 존재. (easy = 100점, hard = 40점) 3. hard를 풀 수 있는 경우, easy는 풀지 않는다. (득점 = 140점) 4. easy만 풀거나 hard만 푸는 경우 모두 한개의 문제를..
백준 159094 : UCPC는 무엇의 약자일까?(그리디) ** www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 정규표현식으로 대문자만 간추렸을 때, UCPC가 되면 되는 줄 알았는데 문제가 두개 있다. 1) set(['UCPC'])하면서 순서가 바뀐다는 것 2) 'UCCPC' 같은 것도 답이 된다는 것... que에 UCPC를 담아두고, for문을 돌면서 대문자열에 순서대로 나오는 지 지워줌. que가 empty가 될 때까지 or 대문자열을 다 돌 때까지 반복 import re if __name_..
백준 2839 : 설탕 배달(그리디) www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 설탕 N(kg) 배달, 봉지는 3kg짜리와, 5kg 짜리가 있음 최대한 봉지를 적게 가져가는 것은? 단, 정확하게 Nkg을 배달할 수 없으면, -1을 출력 거스름돈 문제와 비슷해 보이지만, 모든 경우의 수를 다 해봐야한다는 차이가 있음. 풀이: 5kg짜리 봉지를 많이 사용하는 순으로 --> 남는 양이 3의 배수인 지 체크하면서 갯수를 저장 ex. N=18 --> 5kg짜리를 3,2,1,0 순으로 사용하고--> 그때 남는 ..
백준 2828 : 사과 담기 게임(그리디) ** www.acmicpc.net/problem/2828 2828번: 사과 담기 게임 상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M R : dist = (point-R) L,R = L+dist, R+dist elif point < L : dist = (L-point) L,R = L-dist, R-dist else: continue ans+=dist return ans if __name__=='__main__': N,M = map(int,input().split()) num = int(input()) apples = [] for _ in range(num): apples.append(int(input())-1)..
백준 5585 : 거스름돈 (그리디) www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net # 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있다 def solve(charge): a = charge//500 charge -= 500*a b = charge//100 charge -= 100*b c = charge//50 charge -= 50*c d = charge//10 charge -= 10*d e = charge//5 charge -= 5*e return in..

티스토리툴바