1회차(07.06)

m-inz 2021. 7. 6. 23:51

결과:

* 탐욕법(Greedy)

: 각 단계에서 가장 최선의 선택을 하는 알고리즘

=> 따라서 최적의 해를 보장할 수 없을 때도 많음!

(하지만 코딩테스트에서의 문제는 최적의 해가 종합적으로도 최적의 값이 되도록 출제됨)

ex) 활동 선택 문제, 거스름돈 문제

<프로그래머스 문제 풀기>

* 탐욕법(Greedy) - 체육복

탐욕법에서 체육복 문제를 해결하였다.

먼저 n+1 크기의 all 이라는 배열을 만들어주었다. 모든 사람에 대한 배열이다.

편의를 위해 크기를 n+1 로 잡고, 인덱스 0은 쓰지않는 것으로 하기로 했다.

먼저 reserve, 즉 체육복 여유분을 가지고 있는 사람 (빌려줄 수 있는 사람)을 값을 1 증가시켜 all 배열에 표시한다.

그 후 lost, 잃어버린 사람을 체크하여 값 1을 감소시킨다.

그렇게 되면, 빌려줄 수 있는 사람은 1의 값을 가지고 있을 것이고, 잃어버린 사람은 1씩 감소될 것이고, 나머지는 다 0으로 들어갈 것이다.

비교적 낮은 레벨에서 시간을 많이 소모한 것 같다.

오랜만에 문제를 푸는 것도 있고, 그동안 공부를 안해온 거에 대한 자기 반성의 시간도 가졌다.

다음 모각코 회차에서는 더 발전된 모습으로 나아가고자 한다.