[ 코테python반 스터디 ] 4주차 후기

[스터디/10기] 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 학습 완료!

https://school.programmers.co.kr/app/courses/14135/dashboard

 

[스터디/10기] 코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반) 학습중!

https://school.programmers.co.kr/app/courses/14135/dashboard

 

드디어 마지막... 4주차 스터디가 마무리되었다.

 

이번주는 회사 업무가 바빠 마지막 1문제를 못풀고 스터디에 참가해 아쉬움이 남았다 ㅠ

가장 많은 도움이 되었던 부분은 바로 누군가가 부족한 능동성을 채워줄 수 있다는 점이었던 것 같고, 

두 번째로 도움이 되었던 부분은 문제에 대한 접근 방법을 배울 수 있는 점이었다.

마지막으로 도움이 되었던 부분은 커뮤니티인데, 솔직히 알아서 문제를 풀어내야 하는 스터디라 그런지 조금 활발한 느낌이 적어 아쉬웠던 것 같다. (하지만 함께 모각코를 할 수 있는 분이 한분 계셨어서 열심히 할 수 있었던 것도 사실!)

이제 프로젝트를 하나 준비하면서 이직 준비를 지속해야하겠지만, 가치있는 스터디였고 후에 코테 준비가 다시 필요할 때 한번 고려해볼 수 있을 서비스인거 같다.

 

이번 주는 Sorting과 DP 문제를 풀었다. Sorting은 괜찮았는데, DP는 수학바보라 그런지 문제에 접근하려는 시도 자체가 어려웠던거 같다.

 

1. 단어 퍼즐

---

문제 설명

단어 퍼즐은 주어진 단어 조각들을 이용해서 주어진 문장을 완성하는 퍼즐입니다. 이때, 주어진 각 단어 조각들은 각각 무한개씩 있다고 가정합니다. 예를 들어 주어진 단어 조각이 [“ba”, “na”, “n”, “a”]인 경우 "ba", "na", "n", "a" 단어 조각이 각각 무한개씩 있습니다. 이때, 만들어야 하는 문장이 “banana”라면 “ba”, “na”, “n”, “a”의 4개를 사용하여 문장을 완성할 수 있지만, “ba”, “na”, “na”의 3개만을 사용해도 “banana”를 완성할 수 있습니다. 사용 가능한 단어 조각들을 담고 있는 배열 strs와 완성해야 하는 문자열 t가 매개변수로 주어질 때, 주어진 문장을 완성하기 위해 사용해야 하는 단어조각 개수의 최솟값을 return 하도록 solution 함수를 완성해 주세요. 만약 주어진 문장을 완성하는 것이 불가능하면 -1을 return 하세요.

제한사항

• strs는 사용 가능한 단어 조각들이 들어있는 배열로, 길이는 1 이상 100 이하입니다.
• strs의 각 원소는 사용 가능한 단어조각들이 중복 없이 들어있습니다.
• 사용 가능한 단어 조각들은 문자열 형태이며, 모든 단어 조각의 길이는 1 이상 5 이하입니다.
• t는 완성해야 하는 문자열이며 길이는 1 이상 20,000 이하입니다.
• 모든 문자열은 알파벳 소문자로만 이루어져 있습니다.

입출력 예

strs	t	result
["ba","na","n","a"]	"banana"	3
["app","ap","p","l","e","ple","pp"]	"apple"	2
["ba","an","nan","ban","n"]	"banana"	-1

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
"ap" 1개, "ple" 1개의 총 2개로 "apple"을 만들 수 있으므로 필요한 단어 개수의 최솟값은 2를 return 합니다.

입출력 예 #3
주어진 단어로는 "banana"를 만들 수 없으므로 -1을 return 합니다.

---

DP는 동적 프로그래밍의 약어로 문제 구현력을 보는 문제이다. 쉽게 말해 문제를 그대도 코드로 바꿔보는? 느낌이라고 할 수 있다. DP문제의 핵심은 바로 다음 두 질문에 답하는 것이다.

# 가장 작은 문제는 무엇인가?
# 작은 문제로 큰 문제를 해결할 수 있는가?

입출력 예를 통해 생각해보자. 가장 큰 문제는 "banana"이다.

여기서 가장 작은 문제는 무엇일까? "b"이다.

t가 다음과 같을 경우 strs에서 얻은 결과값을 살펴보자.

이런 식의 문제를 직접 풀어봄으로써 알 수 있다.

"b" -> -1

"ba" -> 1

"ban" -> 2  # 여기서 "ba"는 앞서 구한 결과가 1이고, strs에 "n"이 있기 때문에 합쳐서 2가 된다는 것을 알 수 있다.

"bana" -> 2 # 앞서 "ban"이 2였기 때문에 strs에 "a"를 찾아 3을 리턴할 수도 있지만, 두 번째에서 "ba"가 1이었기 때문에 strs에서 "na"를 찾아 2를 리턴하게 된다. 즉, 이전에 구했던 값으로 다음으로 작은 문제를 풀 수 있겠다는 판단이 든다면 이 문제는 DP문제로 풀어도 된다고 생각하면 되는 것이다.

"banan" -> 3

"banana" -> 3

와 같다.

이 작은 문제로 큰 문제를 해결할 수 있을까? 코드를 구현해보자.

---

우선 dp 배열을 생성한다. 배열의 초기값은 -1로 저장한다. 하지만 리턴을 최소값으로 해야 하기 때문에 편의를 위해 무한값으로 배열을 초기화한다.

그리고 작은 문제들로 큰 문제를 푸는 것이기 때문에 배열 크기만큼 루프문을 돌린다. 

또한 이전 배열의 리턴값들과 마지막 리턴값을 비교해서 가장 작은 리턴값을 배열에 넣어준다.

이런식으로 문제를 정의하면 고민하던 dp문제를 풀어낼 수 있다.

def solution(strs, t):
    dp = [float('inf')] * (len(t) + 1)
    strs = set(strs)
    dp[0] = 0
    
    for i in  range(1, len(t) + 1):
        for j in range(1, min(i + 1, 6)):
            start = i - j
            end = i
            if t[start:end] in strs:
                dp[end] = min(dp[end], dp[start] + 1)
                
    return -1 if dp[-1] == float('inf') else dp[-1]