[TIL] 99클럽 코테 스터디 20일차 TIL + DFS

🍀 오늘의 회고

알고리즘 스터디를 하면서 쓰기 시작한 TIL 마지막 날이다. 흠 사실 TIL을 이어서 작성할지는 고민이다. 주간 회고를 이어서 쓰고 싶은 마음이 커서 TIL은 정말 기록하고 싶은 하루 정도 작성하지 않을까 생각한다. 그리고 매일 오늘의 문제가 추천되지 않으니, 어떻게 꾸준히 문제를 풀 수 있을까 고민했다. 그런데 일단 한 달 문제 풀이를 하면서, 유형별로 바로 풀이 방법이 떠올리는 게 힘들었다. 이제 유형별로 학습하고 문제를 풀어보려고 한다. 아! 강의도 하나 들어보려고 한다.

 

✅ 오늘의 TODO

- 알고리즘

  - 오늘의 문제 ✅

  - Swift 프로그래머스 코딩기초트레이닝 3, 4, 5일 차 ✅

- Task 정리 ✅

 

🌼 오늘의 문제 - 백준 17265. 나의 인생에는 수학과 함께

문제 이름이 너무 내 인생 같지만, 문제는 그리 내 인생 같지는 않았다. ㅋㅋㅋ... 주어진 2차원 배열의 경로에서 오른쪽 혹은 아래로 내려가면서 계산한 값들 중 최소와 최대를 구하는 문제였다. 바로 DFS로 풀어야겠다고 생각했다. 그런데 문제는 어떻게 DFS를 써서 활용할지 생각이 나지 않았다. 모든 가능한 경로를 배열에 넣어둘까 고민하기도 했다. 하지만 연산자 우선순위를 고려하지 않으니, 바로바로 계산하는 것이 빠르다고 판단했다. 여기서 처음 써보는 파이썬 함수를 활용하게 되었는데, 바로 'eval'이다. 표현식의 결과를 바로 계산해 주는 함수이다. 그래서 즉각적으로 계산해 나가면서 DFS를 재귀적으로 활용했다. 다른 풀이를 찾아보니 DP를 활용한 경우도 있었는데, 나는 직관적으로 DFS가 더 이해하기 편하다고 생각해서 이렇게 풀었다.

n = int(input())
routes = [input().split() for _ in range(n)]


def dfs(x, y, expression):
    global min_answer, max_answer
    if x == n -1 and y == n - 1:
        min_answer = min(min_answer, eval(expression))
        max_answer = max(max_answer, eval(expression))
        return

    if 0 <= x + 1 < n:
        if (x + y) % 2 == 0:
            dfs(x + 1, y, expression + routes[x + 1][y])
        else:
            dfs(x + 1, y, str(eval(expression + routes[x + 1][y])))

    if 0 <= y + 1 < n:
        if (x + y) % 2 == 0:
            dfs(x, y + 1, expression + routes[x][y + 1])
        else:
            dfs(x, y + 1, str(eval(expression + routes[x][y + 1])))


min_answer = 5 ** 5
max_answer = -(5 ** 5)

dfs(0, 0, routes[0][0])
print(max_answer, min_answer)

 

🌼 프로그래머스 코딩 기초 트레이닝 Swift

이번 주에 하지 못했던 Swift 기본기 문제들 풀기를 연달아 했다. 문자열이나 Int, 고차 함수 다루는 방법을 조금 '안' 것 같다. 바로 생각하고 풀고 싶지만, 아직 바로 떠오르지 않는 경우도 많다. 하지만 Swift로 푸는 것도 재밌다. 파이썬보다 식이 복잡해지고, 프로그래머스 서버가 느리지만 뭐.. 적응되고 있는 것 같다.