LeetCode 썸네일형 리스트형 [Leetcode] 2353. Design a Food Rating System, <Set vs Priority_queue> 문제를 처음 접했을 때는 Priority_queue를 사용하면 풀리는 문제라고 생각하기 쉽다. 그렇지 않은가? highestRated function은 cuisine 분류 별로 제일 높은 rating을 가진 식품의 이름을 요구한다. cuisine 별로 priority_queue로 작성해 두면 쉽게 뽑아 쓸 수 있다. 그런데 문제는 바로 changeRating 함수다. 이 함수는 food의 rating을 변경하여 저장하는 것을 요구하고 있다. Priority_queue는 사용할 수 없을 것 같다. 왜? Priority_queue는 우선 순위대로 값을 정렬하여 보관하고 있다. 기본값은 이다. 즉 내림차순으로 정렬된다는 이야기다. O(logN) operation에 삽입 정렬을 가능하게 해준다. 그런데 문제점은.. 더보기 [Greedy]Leetcode 1727, Largest Submatrix With Rearrangements 간만에 정말 재미있게 푼 문제다. 언제나 이야기 하듯이 Greedy 문제는 접근 방법을 생각하지 못하면 접근이 어렵다. 이 문제는 어떻게 접근해야 할까? 아래의 사실을 주의 깊게 생각해 한다. 1) Matrix의 크기가 $10^5$ 이하다. 계산량을 따져보았을 때 O(n), O(nlogn) 접근법을 떠올려야 한다. 2) Column 방향으로는 원소가 변화하지 않는다. column의 순서가 low 방향으로만 변화할 뿐이다. 3) Matrix에 접근할 때 접근 방법으로 현재 row 보다 큰 row 방향으로만 직사각형 넓이를 생각한다. 모든 row에 대한 탐색이 이루어 지기 때문에 위의 접근법은 유효하다. 접근 방법을 생각해 보자. 위의 사실을 유념해 두고 아래와 같이 column방향으로 1이 연속적으로 있을.. 더보기 Next Permutation Permutation(순열)은 프로그래밍에서 흔하게 사용되는 개념이다. 나무 위키에는 다음과 같이 정의되어 있다. 서로 다른 n개의 원소에서 r개를 중복없이 순서에 상관있게 선택하는 혹은 나열하는 것을 순열(permutation)이라고 한다. 위의 순열의 개념에서 "순서에 상관있게"를 "순서에 상관없게"로 바꾼 개념이 바로 조합(Combination)이다. n과 r이 일정한 수로 주어졌을 때, 어느쪽이 경우의 수가 더 많이 도출될까? 당연하게도, 순열이 그 경우의 수가 훨씬 많다. $_nP_r = n \times(n-1) \times (n-2) \times ... (n-r+1) =$ $n!\over(n-r)!$ $_nC_r = $ $_nP_r\over r! $ = $1\over r!$ $n!\over(n.. 더보기 이전 1 다음
