[프로그래머스] Python 알고리즘 스터디 - 4주차 Sorting & Dynamic Programming

4주 차

Sorting & Dynamic Programming

Trie

---

< 1. 예산 소팅 >

def solution(departments, budget):
     departments = sorted(departments)
     cur_budget, cnt = 0, 0
     for department in departments:
         if cur_budget + department <= budget:
             cur_budget += department
             cnt += 1
         else: break
     return cnt

---

< 2. 최솟값 만들기 >

def solution(A,B):
     A = sorted(A)
     B = sorted(B)

     ans = 0
     for n1, n2 in zip(A, B[::-1]):
         ans += (n1 * n2)
     return ans

---

< 3. 가장 큰 수 >

from functools import cmp_to_key

def solution(numbers):
    nums = list(map(str, numbers))
    
    def compare_num(n1, n2):
        if n1 + n2 > n2 + n1:
            return -1
        else:
            return 1
        
    nums = sorted(nums, key = cmp_to_key(compare_num))
    return str(int(''.join(nums)))

 

---

< 4. 2 x n 타일링 > 

2 x n 타일링 문제는 처음 봤을 때는 블록들이 나와서 어려워 보였는데,

차근히 그려보니 DP 문제의 제일 기본이 되는 피보나치수열을 다르게 표현한 것뿐이었다.

 

n = 1일 때, 블록의 경우의 수 1개

n = 2일 때, 블럭의 경우의 수 2개

n = 3일 때, 블럭의 경우의 수는 3개...

def solution(n):
     n1 = 1
     n2 = 2
     for _ in range(3, n + 1):
         answer = (n1 + n2) % 1000000007
         n1 = n2
         n2 = answer
     return answer

 

다만 좀 생소했던 게 문제 조건에서 1,000,000,007로 나누라는데 왜 하필이면 저 수로 나눠야만 하는지 이해가 가지 않았다.

2 x n 타일링 코드 리뷰에서 다시 한번 리더분에게 질문을 하니 int 범위를 넘어서면 Big int 연산으로 넘어가기 때문에 임의로 나눠주는 것이라한다. (Modulo operation)

파이썬으로 문제를 풀 때는 범위 생각은 할 필요가 별로 없어서 몰랐던 내용이다.

c나 java로 문제를 풀 때 범위 설정에도 애를 먹었던 기억이 다시한번 난다 ㅋㅋ

 

이 부분은 GeekforGeek에 자세히 설명된 부분이 있어서 참고했다.

 

Modulo 10^9+7 (1000000007) - GeeksforGeeks

---

< 5. 등굣길 > 

1) DFS로 풀이 -> 효율성에서 실패

def solution(m, n, puddles):
    roads = [[0] * m for _ in range(n)]
    shortest_road = float('inf')
    cnt = 0
    
    for puddle in puddles:
        roads[puddle[1]][puddle[0]] = float('inf')

    def dfs(x, y, road_len):
        nonlocal shortest_road, cnt
        if [x, y] == [n - 1, m - 1]:
            if road_len < shortest_road:
                  shortest_road = road_len
                  cnt = 0
            cnt += 1
            return
        for dx, dy in [(1, 0), (0, 1)]:
            Nx = x + dx
            Ny = y + dy
            if 0 <= Nx < n and 0 <= Ny < m and not roads[Nx][Ny]:
                  dfs(Nx, Ny, road_len + 1)
                  
    dfs(0, 0, 0)
    return cnt

등굣길은 신나게 DFS로 풀다가 효율성에서 막혔다.

눈물의 효율성..

열심히 짰는데 효율성에서 전부 다 실패해서 DP로 다시 접근했다.

 

2) DP 문제로 접근

def solution(m, n, puddles):
    roads = [[0] * (m + 1) for _ in range(n + 1)]
    puddles = set(tuple((puddle[1], puddle[0])) for puddle in puddles)
    roads[1][1] = 1
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if [i, j] == [1, 1]: continue
            if (i, j) in puddles: 
                roads[i][j] = 0
            else: 
                roads[i][j] = (roads[i-1][j] + roads[i][j-1])
    return roads[n][m] % 1000000007

 

 

3) 코드 리뷰받고 수정

def solution(m, n, puddles):
    roads = [[0] * (m + 1) for _ in range(n + 1)]
    puddles = set(tuple((puddle[1], puddle[0])) for puddle in puddles)
    roads[1][1] = 1
    
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if [i, j] == [1, 1]: continue
            if (i, j) in puddles: 
                roads[i][j] = 0
            else: 
                roads[i][j] = (roads[i-1][j] + roads[i][j-1]) % 1000000007
    return roads[n][m]

특별히 바뀐 건 없고, 원래는 return 부분에만 1,000,000,007를 나눠줬는데

리더분이 for문 안에서 연산을 할 때 나눠줘서 Big int 연산이 되는 걸 막는 게 효율이 좋다 해서 그 부분만 수정했다.

실시간 강의에서도 스터디 리더분이 for 문 안에서 나눠주는 것과 return에서 나눠주는 것 2개의 시간 비교를 했는데 확실히 for문 안에서 계속해서 나눠주는 게 더 빨랐다.

 

프로그래머스 등굣길 문제처럼 Matrix가 나오는 DP 문제를 leetcode에서 추가로 좀 더 풀어보았다.

62. Unique Paths

63. Unique Paths II

64. Minimum Path Sum

사용되는 아이디어는 동일하다.

---

< 6. 가장 긴 팰린드롬 >

def solution(s):
    ans = 0
    for i in range(len(s)):
        ans = max(helper(s, i, i), helper(s, i, i + 1))
    return ans

def helper(s, l, r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1; r += 1
    return len(s[l + 1:r])

 

---

후기

4주 차는 소팅 문제들은 난이도가 쉬웠는데, 역시 DP문제가 어려웠고 스터디 리더분이 추가로 Trie 문제도 넣어주셨는데, Trie 문제는 조금 생소해서 공부를 추가적으로 더 했다.

Big int 1,000,000,007로 나누는 부분이라던가 몰랐던 부분을 많이 배워가는 주였다.

 

이렇게 해서 한 달간의 알고리즘 스터디가 끝났다!

한 달 동안 스터디를 진행하면서 다시 알고리즘 개념들도 정리하고

코드 리뷰도 받으면서 보다 더 읽기 쉽고, 효율성이 좋은 코드를 짜려고 노력을 많이 해서 그런지 도움이 많이 되었다.

 

스터디는 끝나도 알고리즘 공부는 매일 계속할 생각이다.

스터디 리더분이 적어도 프로그래머스에 있는 3단계, 4단계까지는 풀어보는 게 좋다고 하셔서 적어도 3단계까지는 모두 풀어보는 걸 목표로 공부할 계획이다!

 

 

[스터디/9기] 프로그래머스가 직접 이끌어주는 코딩테스트 대비반(Python반)