본문 바로가기

공부하는 것들/알고리즘

(52)
백준 9440 : 숫자 더하기(그리디)*** www.acmicpc.net/problem/9440 9440번: 숫자 더하기 강민이가 초등학교 3학년일 때, 담임선생님이 이런 문제를 냈었다. 숫자 1, 2, 7, 8, 9 를 사용해서 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수는 무엇일까요? 강민이는 이 문제의 답이 2 www.acmicpc.net def solve(T): N = T[0] numbers = sorted(T[1:]) zeros = numbers.count(0) n, m = '','' for i in range(zeros,len(numbers)): if (zeros-i)%2==0: n+= str(numbers[i]) else: m+= str(numbers[i]) new_n = n new_m = m for i in range(z..
백준 4796 : 캠핑(그리디) www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net Input : L, P, V (연속하는 P일 중, L일 동안 사용 가능, V일 짜리 휴가) (1
백준 2891 : 카약과 강풍(그리디) www.acmicpc.net/problem/2891 2891번: 카약과 강풍 첫째 줄에 팀의 수 N, 카약이 손상된 팀의 수 S, 카약을 하나 더 가져온 팀의 수 R이 주어진다. (2 ≤ N ≤ 10, 1 ≤ S, R ≤ N) 둘째 줄에는 카약이 손상된 팀의 번호가 주어진다. 팀 번호는 중복되지 않 www.acmicpc.net 문제 요약: N개의 팀 중, 카약을 안 가져온 팀의 수 S, 여분의 카약이 있는 팀의 수 R. R 개의 팀은 앞뒤의 팀에게 카약을 빌려줄 수 있다. 카약이 없는 최소 팀의 수는? 안 가져온 팀의 번호를 que_S에 넣고, 여분이 있는 팀의 번호를 que_R에 넣는다. que_S를 최대한 조금 남기는 게 목적이므로, que_S안의 팀을 돌면서 빌릴 팀이 있나 탐색한다. 이때, que..
백준 1783 : 병든 나이트(그리디) **** www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 나이트가 움직일 수 있는 방법 1. (위2, 오1) 2. (위1, 오2) 3. (아1, 오2) 4. (아2, 오1) 나이트가 이동하면서 방문할 수 있는 칸의 최댓값은? 단, 이동횟수 4회 이상일 경우, 네 번 방법 모두 사용해야 함. --> 체스판이 작을 경우. 최대한 1,4를 많이 쓰는 것이 유리. Input : N, M = 체스판의 세로, 가로 Output : 방문할 수 있는 최대 칸 수 문제 풀이> 단순하게 생각했는데 케이스를 깔끔하게 나누는 게 생각보다 까다로웠다. 다..
백준 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 = 보라색 포..
백준 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_..