문제 링크 1. 어떻게 풀지 조금 고민하다가 문제에서 $N$이 10 이하의 자연수라고 하여서 몇 가지 예를 적어보고 규칙을 찾으면 풀 수 있을 것이라 생각했다. 한 5개 정도 직접 써보며 컴퓨터의 입장에서 어떻게 풀지 고민하였더니 풀렸다. 정답률 $56\%$의 문제로 난이도가 다소 낮은 문제이다. 2. 나는 이 예제를 기준으로 문제를 풀었다. input 5 3 3 0 1 0 output 3 5 4 1 2 1. 1번보다 키가 큰 사람의 수가 3이라면 위치가 3일 수 밖에 없다. (arr인덱스의 0부터 계산) arr 0 0 0 1 0 2. 2번보다 키가 큰 사람의 수가 3이라면 arr 인덱스의 0부터 3개의 빈칸을 두어야 한다. 왜냐하면, 3개의 빈칸에 2번보다 키가 큰 사람을 세워야 하기 때문이다. arr..
그리디
문제 링크 1. $(0,0)$부터 끝까지 변환 후 같은지 확인하면 될 것 같은데..라고 생각했지만, 그리디 문제라서 뭔가 좀더 그리디스러운 방법이 존재할 거라고 생각했다. 저 방법 말고는 떠오르지가 않아 방법이 맞는지 해설을 봤더니 맞았다.. 2. 내가 생각했던 데로 $(0,0$에서 부터 끝가지 변환하면 되지만 유의해야 할 점이 있다. $3\times3$ 크기의 부분 행렬을 변환하는 것이라서 $N\times M$ 모두 확인할 필요가 없다. $(0,0$ 에서부터 $(N-3,M-3)$ 까지만 변환하면 된다. 그 이상의 변환은 다시 원래대로 바꾸는 것이므로 불필요한 연산이 된다. 이것을 알았다면 구현은 쉽다. 1. $(0,0$에서부터 $(N-3,M-3)$까지 A와 B의 원소가 다르다면 $3\times3$ 크기..
문제 링크 1. 노트에 좀 끄적이다가 아이디어가 떠올라 코드를 쭉 썼다. 아무 생각 없이 제출했으나 시간 초과.. 나는 list를 이용해서 서류 성적을 기준으로 정렬하고 list를 순회하며 값을 비교하기 위해 이중 for문을 사용하였다. 하지만, 이중 for문을 사용하면 $O(N^{2})$ 인데 지원자의 최대 수가 $100,000$ 이므로 시간 초과가 날 수밖에 없다. 결국 이중 for문을 사용하지 않는 방법을 찾아야 하는데 찾지 못해 풀이를 참고하였다. 2. 그 방법은 생각보다 단순했다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다. 문제에서, 동석차가 없다고 하였으므로 사용자 정의 Class를 만들 필요 없이 배열의 인덱스 값을 석차로 설정하면 된다! 그러면 성적 정렬을 할..
문제 링크 1. 문제를 보고 답을 내는 메커니즘 자체는 쉽게 생각해냈다. 다만, 입력받은 문자열을 어떻게 쉽고 효율적으로 가공할지 몰라서 풀이를 참고하였다. 2. 그리디 알고리즘을 적용하면, 괄호를 넣어 식의 값을 최소로 만들려면 최대한 많은 수를 음수로 만들어야 한다. 즉, $-$가 나오고 다음 $-$가 나오기 전까지 괄호로 묶으면 되는데, 이 말은 곧 $-$와 $-$사이의 $+$를 $-$로 바꾸면 된다. 예를 들어보면, $1+2+3-4+5+6-7+8$ 이라면 $1+2+3-(4+5+6)-(7+8)$ 으로 괄호를 치는 것이 최소가 된다. 이는 곧 $1+2+3-4-5-6-7-8$과 같다. 이를 메커니즘으로 나타내면 다음과 같다. 1. 입력받은 문자열을 $-$를 기준으로 분리 2. 분리한 문자열을 차례대로 ..
문제 링크 1. 30분 소요. 머리속으로 어떻게 풀지 생각하면서 멍때리다가 노트에다가 막 끄적여보았는데 바로 아이디어가 떠올랐다. 써보면서 고민하자. 2. 문제의 예시의 답은 어떻게 나왔을까? 그리디 알고리즘답게 탐욕스러운 사고 기법을 해보았다. $10$만 선택했을 때는 최대 $10$만큼 들어올릴 것이다. $15$만 선택했을 때는 최대 $10$만큼 들어올릴 것이다. $10, 15$를 선택했을 때는 $30$이 아닌 $20$만큼 들어올릴 수 있다. 왜? $w/k$만큼 들어올릴 수 있으므로 $30$이 되면 $10$짜리 로프는 못버티기 때문이다. 즉, 들어올릴 수 있는 무게는 제일 작은 중량을 기준으로 선택해야한다. 다만 문제에서 모든 로프를 사용할 필요가 없다고 했으므로, 1. 내림차순 정렬 2. 1개, 2개..
https://www.acmicpc.net/problem/1931 1. 문제를 처음 보았을 때 저번에 프로그래머스에서 풀었던 단속 카메라 문제와 유사하다고 생각했다. 그러나 해당 문제의 풀이법을 잊었을 뿐 더러, 그 문제를 다시 풀어보았지만 이 문제에 적용시키기에 어려움을 느꼈다. 2. 이 문제를 풀기에는 다음과 같이 세 가지의 탐욕적 사고 방법이 있다. 회의 시작 시간을 기준으로 회의 종료 시간을 기준으로 회의 소요 시간을 기준으로 이 세가지 방법 중 첫 번째와 세 번째 방법은 반례가 존재하므로, 두 번째 방법을 선택한다. 회의가 빨리 종료되는 순으로 오름차순 정렬을 하여 선택을 하는데, 다음 선택할 회의의 시작 시간이 그 전 회의의 종료 시간보다 빠르면 선택하지 않는다. 3. import java.u..
