취업 준비 및 일상

https://www.acmicpc.net/problem/24025 24025번: 돌의 정령 줄세우기 $4$, $1$, $5$, $2$, $3$으로 배치한다면 돌의 정령 무리들의 시야점수는 각각 $2$, $1$, $10^9$, $1$, $10^9$로 조건을 만족한다. www.acmicpc.net 풀이 전형적인 코드포스 스타일의 구성적/그리디 문제입니다. 쌩 브루트포스는 O(N!)일테니 절대 안되며, 적당히 가지치기한다고 해도 O(N^2) 이하로 줄이기가 쉽지 않아보입니다. 그러다 보면, '최적의 배치가 존재하지 않을까?'와 같은 생각에 도달하게 됩니다(그리디 말고는 생각나는게 없으니...). 그리디하게 찾아보도록 합니다. 1-based를 기준으로, 1 = 1이므로, 언제나 조건을 만족합니다. 그리고, N..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이 처음에는 별 생각없이 DP 식으로 접근했다가, 메모리 초과가 나왔습니다. 그래서 다른 방식으로 풀었습니다. 저울추를 오름차순으로 정렬합니다. 저울추가 0개일 때에는 잴 수 없는 최소 무게가 1이므로, 1에서 시작합니다. 저울추에 대해 for문을 돌면서, 만약 현재 저울추의 무게가 현재 잴 수 없는 최소 무게보다 클 경우 현재 잴 수 없는 최소 무게는 앞으로도 잴 수 없습니다. 반대로, 현재 저울추의 무..

https://www.acmicpc.net/problem/17451 17451번: 평행 우주 행성 1에 가기 위해 필요한 것보다 세 배의 속도로, 행성 2의 경우 두 배의 속도로 이동하면, 지구에서는 900의 속도만 쌓으면 된다. www.acmicpc.net 풀이 1. 이분 탐색 지구에서 올리는 속도 v를 이분 탐색을 통해 최솟값을 찾는 풀이입니다. 최소 속도의 최댓값이 얼마나 될지 살짝 감이 안 잡히나, 9억이 넘는 서로 다른 세 소수 a, b, c (a (int의 max 범위) 이므로 int 범위를 벗어납니다. 따라서, 일단 long으로 찾아야 한다는 사실을 발견할 수 있습..

https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 풀이 주어진 책의 위치를 양수와 음수로 나눕니다(0은 입력으로 주어지지 않으니 고려하지 않아도 됩니다.). 양수의 개수를 a개, 음수의 개수를 b개라고 하면, 세준이는 모든 책을 갖다놓기 위해서 양수 쪽의 위치로는 math.ceil(a/m)번, 음수 쪽의 위치로는 math.ceil(b/m)번 이동해야 합니다. 한 번의 이동에 최대 M개의 책을 가져다 놓을 수 있는데, 끝 위치에서부터 M개를 채운다고 생..

https://www.acmicpc.net/problem/3663 3663번: 고득점 현수는 조이스틱을 이용해 지렁이를 미로에서 탈출시키는 게임을 하고 있다. 최고 점수를 얻은 경우에는 조이스틱을 이용해서 이름을 입력해야 한다. 이름을 입력하는 과정은 다음과 같다. 가 www.acmicpc.net or https://programmers.co.kr/learn/courses/30/lessons/42860# 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 풀이 0) 글자 바꾸는건 별로 안 어렵..

https://programmers.co.kr/learn/courses/30/lessons/77886 코딩테스트 연습 - 110 옮기기 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 programmers.co.kr 문제 설명 0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다. x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다. 예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 ..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 풀이 1. 풀이 아이디어 그리디하게, 맨 앞의 숫자와 그 다음에 올 숫자를 비교하여 앞의 숫자가 다음의 올 숫자보다 작다면 ..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방..

문제 오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다. 총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.) 이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다. 공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..