99클럽 코테 스터디 22일차 TIL + Bruteforcing, Backtracking

비기너 문제

문제 설명

LeetCode 2558: Take Gifts From the Richest Pile

• 설명: 가장 큰 수의 제곱근의 내림을 $k$번 반복하고 남은 수의 합을 구하여라

풀이

• $n,k \le 10^3$이다.
• 만약 가장 큰 수를 찾는 것을 정렬을 통해 구하고 이 과정을 $k$번 반복하면 시간복잡도가 어떻게 될까?
  • 정렬 $O(n \log{n})$, 을 $k$번 반복하니 $O(kn \log{n})$이 된다.
  • 이는 충분하므로 단순히 구현하였다.

Code

class Solution:
    def pickGifts(self, gifts: List[int], k: int) -> int:
        for _ in range(k):
            gifts.sort()
            maximum = gifts.pop()
            gifts.append(int(maximum ** 0.5))

        return sum(gifts)

미들러 문제

문제 설명

Programmers: 피로도

• 설명: 각 던전의 최소 필요 피로도와 소모 피로도가 주어질 때 최대한으로 던전을 탐색하여라

풀이

• 기본적으로 던전의 크기는 $8$이다. 던전을 탐험하는 모든 경우의 수는 $8!$이므로 backtracking으로 충분히 돌아간다.

Code

# Programmers87946.py
def solution(k, dungeons):
    n = len(dungeons)

    ans = 0
    visited = [False] * len(dungeons)

    def solve(rest, explore):
        nonlocal ans
        ans = max(ans, explore)

        for i in range(n):
            if not visited[i]:
                if dungeons[i][0] <= rest:
                    visited[i] = True
                    solve(rest - dungeons[i][1], explore + 1)
                    visited[i] = False

    solve(k, 0)

    return ans

오늘의 회고

• 해커톤 준비 때문에 비기너 문제로 풀고 인증을 했다.
• 하지만 비기너 문제만 TIL 하기는 좀 그래서 미들러도 풀었다.
• 아마 수, 목은 해커톤 때문에 비기너만 TIL로 올릴수도...
• 리트코드도 오랜만에 써보니까 많이 달라졌다.
  • UI도 더 깔끔하게 바뀌었고
  • 무려 내 코드를 제출하면 AI가 시간 복잡도 분석을 해준다 ㄷㄷ