나의 알고리즘 공부 여정8 - 마지막 편, 회고

20210317_TIL

 

• 알고리즘 문제를 집중적으로 다루어 보는 기간이 끝났다. 3월 5일부터 14일간 알고리즘의 바다에 풍덩 빠져있었다. 아직 만족할 만큼 알고리즘 문제를 막힘없이 풀어내지는 못하지만, 짧은 기간안에 알고리즘을 유형별로 흩어보고 풀이 경험을 쌓을 수 있었기에 의미 있는 시간이었다.

 

• 하루 하루 문제를 풀어나가면서, '내가 늘고 있는게 맞나?'라는 생각이 드는 날들도 있었지만 3월 5일 TIL 글을 읽고 바로 깨달았다. 2주 전에 비해 알고리즘 실력이 엄청나게 늘었다는 사실을.... 입력을 어떻게 받는지도 몰랐던 내가 자료구조와 알고리즘 문제들의 유형별 풀이를 전반적으로 익히고 적용하는 수준으로 성장했다.

 

• 특히, 1주차에 이해가 안되서 그냥 넘어간 문제들을 2주차에 다시 보니 쉽게 이해가 되서 조금 놀랐다. DP bottom up 방식이 특히 이해가 안됬었는데, 최적해 알고리즘 문제들을 풀면서 근본 원리에 대한 이해가 진행되니 DP bottom up 방식 역시 수월하게 이해할 수 있었다. 자유자재로 코드 구현하는 건 좀 더 연습해야 되지만...!

 

• 알고리즘 문제 풀이 주차는 끝났지만 알고리즘 문제를 꾸준히 풀어나갈 생각이다. 두 가지 방법으로 문제풀이를 진행할 생각이다. 1) 부족한 유형을 찾아 백준에서 관련 유형이 익숙해질 때까지 그 유형의 문제들만 풀 계획이다. 2) 코딩 테스트 환경에 익숙해지기 위해 프로그래머스 사이트에서 level 1부터 문제들을 하나씩 다 풀어나갈 계획이다. level 5문제까지 모두 풀 날이 얼른 오기를!

 

 

 

1. 부족하다고 생각되는 부분

1) 재귀 함수로 자료구조, 알고리즘 구현하기

 

항상 반복적인 연산을 코드로 구현해야 할 때면 while문, for문 등으로 최대한 돌려막기 했었다. 그래서 재귀 함수 사용이 많이 늘지 않은 것 또한 사실이다. 하지만 문제 난이도가 상승할수록 재귀함수 대신 while문, for문 등을 사용하는 데에 한계가 있다는 것을 뼈져리게 느꼈다. 따라서 백준 사이트에서 재귀함수 관련 문제들을 재귀 마스터가 될 때까지 풀 계획이다. 다음은 재귀함수 관련 문제들을 모아놓은 백준 사이트 링크이다. 

 

문제 - 1 페이지

 

2) 클래스 구현

 

알고리즘 문제를 풀다보면 사실 test case 한 두개 넣어볼 일밖에 없다. 따라서 프로젝트를 할 때 유용하게 쓰일 수 있는 클래스 구현을 연습하지 못했다. 사실, 알고리즘 문제도 클래스를 이용해 풀 수도 있다. 하지만 클래스를 안 쓰고도 문제를 못 푸는건 아니다보니 의식적으로 구현해보는 노력을 안했던 것 같다. 일단 Class를 구현해놓은 관련 코드들을 많이 봐서 익숙해지고, 구현해 보는 연습이 필요하다.

 

 

3) 풀이 양

 

확실히 푼 문제가 늘어날 수록, "아 저번에 푼 문제랑 비슷하다"라고 느껴지는 문제들이 많아졌다. 개념별로 분류 구조도 더 잘 그려진다. 따라서 매일 조금이라도 꾸준히 푸는게 중요할 것 같다. 다음주부터는 새로운 Java라는 언어를 배우면서 백앤드 개발의 길로 들어서는 단계인데, 가능하다면 잠깐이라도 짬을 내서 꾸준히 알고리즘 문제를 풀어야겠다.

 

 

 

2. 꾸준히 늘고 있다

 

- DP Bottom Up

 

11053번: 가장 긴 증가하는 부분 수열

 

DP Bottom Up 문제인데, 이 문제를 불과 8일 전인 3월 11일에 난이도가 있는 문제라고 소개하며 Bottom Up 방식의 DP 구현을 알아두어야 겠다고 적어두었다.

 

 

11054번: 가장 긴 바이토닉 부분 수열

하지만 11053 가장 긴 증가하는 부분 수열 문제를 응용해야 하는 가장 긴 바이토닉 부분 수열을 오늘 풀었다...! 아무래도 11053번 문제를 푼 경험치가 있고, 8일간 DP관련 문제를 7문제 정도 풀었기에 가능했던 것 같다. 역시 경험은 중요하다.

 

import sys

n = int(sys.stdin.readline().strip())
a = list(map(int,sys.stdin.readline().strip().split()))

dp = [0]*n # n개의 0을 가진 list 생성
for i in range(n): 
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1
print(dp)

a2 = a
a2.reverse()
dp2 = [0]*n # n개의 0을 가진 list 생성
for i in range(n): 
    for j in range(i):
        if a2[i] > a2[j] and dp2[i] < dp2[j]:
            dp2[i] = dp2[j]
    dp2[i] += 1
dp2.reverse()
print(dp2)

final_dp = []
for i in range(n):
    final_dp.append(dp[i] + dp2[i] - 1)

print(final_dp)
print(max(final_dp))

 

맨 처음 문제를 봤을 때, 주어진 상황 아래에서 "가장 긴"이라는 단어를 보고 최적해 알고리즘을 이용해 푸는 문제라 생각했다. 그리고 상위문제의 결과를 구하기 위해 하위 문제의 결과를 이용해야 하는 부분에서 DP를 이용할 포인트가 있음을 파악했다.

 

DP 문제는 일단 누적이 핵심인데, 지금 내가 누적하고 있는 게 어떤 걸 의미하는지 항상 생각하며 누적해야 한다. n번쨰 인덱스에 내가 어떤 값을 누적하고 있는지를 알고 그걸 수식으로 구현하는게 DP 구현이라 생각한다. 이 문제에서도 역시 시작점에서 시작해 가장 긴 올라가는 부분 수열과 끝점에서 시작해 가장 긴 올라가는 부분 수열을 DP 누적으로 구했다. 이렇게 누적한 DP 값들을 병합하는 과정이 미숙해 도움을 받기는 했지만.. 그래도 이만큼이나 해내 뿌듯하다.