4주차

코딩테스트와 실무 역량 모두 잡는 알고리즘 스터디(Python반)에 참여한 내용을 정리했다.

4주차는 sorting과 dp에 관련된 문제들을 풀었다.

2 x n 타일링

dp배열을 이용해 풀었다.

def solution(n):
    answer = 0
    dp = [1] * (n + 1)
    for i in range(2, n + 1):
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
        
    return dp[n] 

배열 대신 변수를 사용해 메모리 사용을 줄일 수 있었다.

def solution(n):
    prev1, prev2 = 1, 2
    for i in range(3, n + 1):
        prev1, prev2 = prev2, (prev1 + prev2) % 1000000007
    return prev2

영어 끝말잇기

deque를 이용해 하나씩 꺼내며 체크했다.

from collections import deque
def solution(n, words):
    spoken = []
    words = deque(words)
    cnt = 0
    while words:
        cnt += 1
        for i in range(n):
            try:
                word = words.popleft()
                if len(spoken) == 0: 
                    spoken.append(word)
                    continue
                if word not in spoken and spoken[-1][-1] == word[0]:
                    spoken.append(word)
                else:
                    return [i + 1, cnt]
            except:
                break
    return [0,0]

for문과 집합을 사용해 훨씬 간결하게 코드를 작성할 수 있었다.

def solution(n, words):
	check = {words[0]}
	for i in range(1, len(words)):
		if words[i - 1][-1] != words[i][0] or word[i] in check:
			return [i % n + 1, i // n + 1]
		check.add(words[i])
	
	return [0, 0]
		

코드리뷰를 정말 세심하게 해주셔서 놀랐던 마지막주 세션이었다.