그리디

- 무지의 먹방 라이브(카카오 기출, 그리디): https://programmers.co.kr/learn/courses/30/lessons/42891

진짜 화남 90프로 이상 풀었는데 매달리는게 너무 시간낭비 같아서 그냥 포기하고 풀이봤음... 사실 그리디인지 아직 잘 안와닿기도... 난 그냥 풀어서... 나중에 다시 보고 다시 풀어볼 강력한 문제 중 하나 결국 못푼 문제이기 때문

 

다시 풀어봤는데, 예전엔 채점 결과 어땠는지 모르겠는데 이번엔 정확성은 모두 맞추고 효율성은 모두 틀렸다. 이전에 k에 대한 계산에서 효율성을 꾀했지만 이번엔 k에 대한 계산 효율은 꾀하지 않고 자료구조 면으로만 강점을 둠. 결국 정답은 둘다 맞아 떨어져야 한다는 것임. 예나 지금이나 k의 계산 측면에서 틀렸었고 여전히 이 부분 이해를 잘 못하고 있으니, 계산 중심 풀이로 재도전 필요

 

아래는 풀면서 작성한 메모 풀

<마지막 멈춤 지점 구하는 방법>

1 (양, 인덱스) 의 튜플을 원소로 갖는 배열을 오름차순 정렬한다. 아 정렬에 걸리는 시간도 좀 크겠는데… 그럴바엔 Min을 계속해서 구하는게 더 전략적이지 않?

 

2 앞에서 구한 최소값이 완주횟수보다 작은지 큰지 구한다

2-1 크면 모든 원소에서 그 값만큼 빼거나 뺼 준비를 마친 뒤 루프 종료하고 next stage로 간다.

2-2 작으면 우선 해당 원소를 두 배열에서 뺀다.

또한 length, round_length 값을 1씩 줄인다.

k에서 최소값*완주 횟수만큼 뺀다.

모든 원소에서 최소값만큼 빼는 일의 대체로 accumulated += 최소값 을 해서 그 다음 최솟값에 대한 연산에 써먹는다

 

일단 K가 음수가 되기 직전까지 위 과정을 반복 은 맞음

처음 나온 완주 횟수가 8번이잖아?

이때 원소들 중 8보다 큰 최초의 원소에서 멈추게 한다 (포인터 설정으로 하여금)

포인터 앞의 애들의 (원래 배열 즉 food_times에서의) 인덱스들을 관리 대상에 포함시킨다

length를 새롭게 업데이트하고, round_length도 업데이트한다 그리고 원소의 값들에서 기존 round_length 만큼 빼주는것도 한다(는 순회때문에 시간 복잡도 늘어나니까 공제해야 하는 값을 저장해두고 그때그때 계산해서 써먹는다!)

같은 방식으로 해보다가 결국 모든 원소의 크기가 roundlength보다 커서 이게 패스되어버리면, 이제 남은 k 만큼만 더 이동해보면 되는 것임

 

 

 

 

리트코드 2178(그리디): https://leetcode.com/contest/biweekly-contest-72/problems/maximum-split-of-positive-even-integers/

그리디의 특성을 띤 완전 탐색이라 생각해서 여기 붙임. 원래 무의식중에 배열에 append pop 하고 있었더니 시간 초과 떠서 deque로 바꿔주니까 70ms->49ms로 줄어드는 극적 효과 보임. 쉬운 문제였는데 난 푸는데 드럽게 오래걸림. 글고 다른 사람이 푼 숏코드는 더 대박임...내가 졸린 상태에서 봐서 이 로직 발상을 이해하지는 못함. 잠깨고 다시 보자. 아래는 푼다고 적은 메모 사항.

<28> [2,4,6,16] (26-22-16-0)

2로 시작. 2가 배열에 없는 것 역시 추가 조건이 된다. 없으니 2 추가한다 치자

이제 [2, 4, ~] 로 나눌수있는지 알아본다 그럼 28-(2+4)=22 에 대해 알아본다. 

22를 [6, ~] 로 쪼갤 수 있는지 알아본다 그럼 22-6=16이다

16을 [8, ~]로 쪼갤 수 있는지 알아본다. 이 경우 [8, 8]이 되고 이때 같은 수가 2번 들어가니 이렇게 쪼개는건 불가능하다. 따라서 16을 그대로 쓸수 있는지 알아본다. 사용된 숫자 중 16이 없으니 [2,4,6,16]이 답이고 이를 반환한다.

 

<12> [2,4,6] (10-6-0)

2추가

이제 12-2=10에 대해 [4, ~] 로 시작해서 나눌 수 있는지 알아본다. 그럼 이제 6을 [6, ~]로 나눌 수 있는지 알아보면 되는데 6으로 나누고 나면 더이상 나눌 수가 없음 0임. 그러니 다 가능하다는 이야기고, 그대로 반환하면 된다.

 

<10> [2,8] (8-4-2-0)

뭔가를 2로 시작한다 2는 ans 에 없으니 추가

그럼 8을 2보다 2만큼 큰 4로 쪼개기 시작해서 배열을 반환하는게 가능한지 알아본다.

그럼 [2, 4, (4 쪼개보기)] 가 된다.

4는 6부터 쪼개봐야만 하는데 그게 불가능하니 3번째의 4 그대로를 반환할 수 있는지 알아본다 하지만 이미 4는 배열에 있으니 불가능하다. 즉 [2, 4, ~] 로 쪼개는건 불가능하단 거다.

그럼 이제 [2, 6, ~]로 쪼갤수 있는지 알아본다. [2, 6] 으로 쪼개면 나머지 남은 숫자는 2다. 근데 2는 더이상 나눌 수 없는 수 즉 이미 배열에 존재하는 수이므로 결론은 6으로도 못나눈다는 말이다.

그럼 [2, 8, ~]로  나눌수있는지 알아보는데 이미 저건…끝.

 

<8> [2, 6]

2로 시작. 2가 배열에 없는 것 역시 추가 조건이 된다. 없으니 2 추가한다 치자

그담에 6을 2보다 2만큼 큰 4부터 나누기 시작해서 검사한다고 치는거다

그럼 4를 ans에 추가한다치자 그럼 남은 수가 2잖아

근데 이 나눠야 하는 수인 2는 더이상 나눌 수 없는 애잖아? 가 아니고 얘는 6부터 시작했었어야 했는데 그게 불가능한거잖아 이미 크기가 더 작기 때문에? 2를 앞에서 추가했는지 봐야한다 근데 있잖아? 그럼 6을 4+~ 로 쪼개는건 불가능하다는 거다.

그럼 ans=[2, 4, ~] 하는게 불가능하단 이야기이니 [2, 6, ~]이 가능한지 봐야한다

근데 이미 2, 6만으로 합이 8이므로 더이상 쪼갤 수 없다는 의미이다. 따라서 리턴.

 

 

<검사할 조건>

- temp < finalSum

- temp not in ans

- finalSum > 0

 

————————————————————————

근데 문제가… 10에 10승 즉 엄청 큰 수가 되면 이게 힘들지않겠어? 뭔가 '횟수’만을 구한다는 점에 주목했을 때 더 빠른풀이가 나오지 않을까? 이분탐색, dp 등…?

이거 그… 조합… 이랑도 연결 지을 수 있는데…

그리고 음… 

근데 그렇다고 다른 좋은풀이가 생각나진 않는다

 

 

 

1744: https://www.acmicpc.net/problem/1744

골4임에도 어려운 문제가 아녔다. 단, 예시 입출력 보고 에지 케이스 처리 잘 해야 하고, 인상 깊은 건 나처럼 힙을 쓰는 것보다 그냥 배열에 지원하는 기본 sort 혹은 sorted()를 쓰는게 훨씬 시간이 짧게 나오는 문제라는 것. 실제로 시간 복잡도 상으론 힙보다 라딕스 소트가 훨씬 효율적일텐데, 막상 파이썬으로 알고 문제 풀어보면 정렬이 정말 필요한 경우 기본 정렬 쓰면 시간 초과 나거나... 하는 경우 많아서 이번에도 안 그럴 줄 알았는데. 그렇지 않았다. 도움 되는 숏코드+짧은시간 풀이는 1744_1에 실음