import numpy as np 
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
import warnings
from sklearn.preprocessing import LabelEncoder
from sklearn.model_selection import train_test_split, KFold, cross_val_score
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score
from datetime import datetime
import warnings

%matplotlib inline 

def encode_features(dataDF):
    features = ['Gender','Tumour_Stage','Histology']
    for feature in features:
        le = LabelEncoder()
        le = le.fit(dataDF[feature])
        dataDF[feature] = le.transform(dataDF[feature])
    return dataDF

def calc (date_str1, date_str2):
    date_format = "%d-%b-%y"

    date1 = datetime.strptime(date_str1, date_format)
    date2 = datetime.strptime(date_str2, date_format)

    delta = date2 - date1

    return delta.days

BRCA_df = pd.read_csv(r"C:\Users\User\Data_Handling\BRCA.csv").head(333)
#경고무시 
warnings.simplefilter(action='ignore', category=FutureWarning)

#데이터 전처리
BRCA_df['Date_of_Surgery'] = pd.to_datetime(BRCA_df['Date_of_Surgery'], format='%d-%b-%y')
BRCA_df['Date_of_Last_Visit'] = pd.to_datetime(BRCA_df['Date_of_Last_Visit'],format='%d-%b-%y')
BRCA_df['Surgery_Visit_Between'] = BRCA_df['Date_of_Last_Visit'] - BRCA_df['Date_of_Surgery']
BRCA_df = BRCA_df[BRCA_df['Gender']!="MALE"]
BRCA_df = BRCA_df.dropna()
encode_features(BRCA_df)
BRCA_df = BRCA_df.drop(['Patient_ID','Surgery_type','Date_of_Last_Visit','Date_of_Surgery','Gender'],axis=1)
BRCA_df[["ER status","PR status","HER2 status"]] = 1 if "Positive" else 0
BRCA_df["Surgery_Visit_Between"].fillna(BRCA_df["Surgery_Visit_Between"].mean(),inplace=True)
BRCA_df["Surgery_Visit_Between"] = BRCA_df["Surgery_Visit_Between"].apply(lambda x : int(str(x).split()[0]))

#데이터 분류
Y_BRCA_df = BRCA_df["Patient_Status"]
X_BRCA_df = BRCA_df.drop(["Patient_Status"],axis=1)

#머신러닝
dt_clf = DecisionTreeClassifier()
rf_clf = RandomForestClassifier()
lr_clf = LogisticRegression(solver='liblinear')

X_train,X_test,Y_train,Y_test = train_test_split(X_BRCA_df,Y_BRCA_df,test_size=0.2,random_state=11)


#의사결정트리 
print("👨🏻‍⚕️의사결정트리")
dt_clf.fit(X_train,Y_train)
dt_pred = dt_clf.predict(X_test)
print("정확도:",accuracy_score(Y_test,dt_pred))
scores = cross_val_score(dt_clf,X_BRCA_df,Y_BRCA_df,cv=5)
print("Starified_KFold 교차검증 정확도:",scores.mean())
print()

#랜덤포레스트 
print("🌳랜덤포레스트")
rf_clf.fit(X_train,Y_train)
rf_pred = rf_clf.predict(X_test)
print("정확도:",accuracy_score(Y_test,rf_pred))
scores = cross_val_score(rf_clf,X_BRCA_df,Y_BRCA_df,cv=5)
print("Starified_KFold 교차검증 정확도:",scores.mean())
print()

#로지스틱회귀 
print("💻로지스틱회귀")
lr_clf.fit(X_train,Y_train)
lr_pred = lr_clf.predict(X_test)
scores = cross_val_score(dt_clf,X_BRCA_df,Y_BRCA_df,cv=5)
print("Starified_KFold 교차검증 정확도:",scores.mean())
print("정확도:",accuracy_score(Y_test,lr_pred))
print()

1806번 - 부분합

수열이 주어지면 S보다 크거나 같은 부분수열의 합 중에서 가장 크기가 작은 부분수열을 구하면 되는 문제입니다.

분석

일단 위 문제에 나온 수열을 그대로 가져왔습니다. 여기서 투포인터 개념을 적용할겁니다. lst.popleft()를 통해 값의 합이 15가 되기 전까지 원소를 계속 긁어옵시다. 그런데 긁어오다 보니 값의 합이 15를 넘은 24가 되었습니다! 이러면 조건에 만족하는 부분수열이니 해당 부분수열의 크기를 따로 기록하고 최종적인 목적은 15가 넘는 제일 작은 크기의 부분수열이니 quene를 pop해서 최대한 크기를 줄여봅시다. 5를 popleft해도 19가 되므로 이 수열 크기(4)또한 따로 기록해두고 더 빼봅시다. 1을 popleft해도, 3을 popleft해도 15보다 크거나 같으므로 부분수열의 크기를 따로 기록해두고 더 뺴봅시다. 드디어 10만 남게되어 조건을 만족하지 못합니다. 이제 윗부분으로 다시 돌아가서 합산 15이상이 될때까지 lst에서 원소를 다시 긁어옵시다.

투포인터란 이처럼 시작점과 끝점을 잡고 조건을 만족하지 못하면 끝점을 늘리고 조건을 만족하면 시작점을 빼는 형식의, 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘입니다.

출력값을 통해 과정을 살펴보면 위와 같은 느낌입니다.

코딩

위 과정을 코딩해봅시다.

from collections import deque
import sys

input = sys.stdin.readline

해당 문제는 시간제한이 0.5초로 매우 급박하므로 sysinput을 사용해줍니다.

N,S = map(int,input().split())
lst = deque(list(map(int,input().split())))

배열의 크기, 합산 조건, lst등을 받아주고

quene = deque([lst[0]])

투포인터를 사용할 que를 하나 만들어줍니다.

    cum_sum = lst[0]
    lst.popleft()
    min = 100000001

한가지 주의할 점이 있습니다. 부분배열의 합산값을 구할때 sum(부분배열)을 하게되면 sum 함수를 100000번 가까이 사용해야 하므로 시간제한에 거릴 확률이 굉ㅡ장히 높습니다. 따라서 누적합을 cum_sum을 통해 따로 기재해주겠습니다.

    while True:
        try:
            if cum_sum < S:
                tmp1 = lst.popleft()
                cum_sum += tmp1
                quene.append(tmp1)

만약 부분수열의 합이 위 예시에서 봤던 것처럼 15보다 작아 조건을 만족하지 못한다면 lst에서 원소를 긁어와 quene에 추가해줍시다.

            else:
                if len(quene) < min:
                    min = len(quene) 
                tmp2 = quene.popleft()
                cum_sum -= tmp2

만약 조건을 만족한다면 조건을 만족하는 quene의 길이 중에서 제일 작인 길이를 quene에 넣어주도록 합니다.

        except:
            break

quene을 다써서 예외가 날 경우엔 break으로 처리해주고

print(min)

마지막으로 min을 출력하면 끝날 것 같지만 골드의 벽은 그렇게 호락호락하지 않습니다...

반례

로직이 올바른데 틀리게 나온다면 항상 반례를 생각해봐야 합니다.

1. 테스트케이스가 10/10/11113211111 일때

한 가지 숫자가 조건 S를 만족시킬만큼 S보다 크게 나와버린다면 답은 무조건 1이 됩니다.

2. min이 제 역할을 못해서 그대로 나와버릴 경우

만약에 뭘 해도 합산 S가 만족되지 않는다면

            else:
                if len(quene) < min:
                    min = len(quene) 
                tmp2 = quene.popleft()
                cum_sum -= tmp2

구문 자체가 실행되지 않아 최솟값을 구하려고 둔 min값이 초기값 100000001로 그대로 유지되게 됩니다. 이 두 경우를 고쳐봅시다.

for values in lst:
    if values >= S:
        boolean = True
if boolean == True:
    print(1)
else:

투포인터 코드를 실행시키기 전에 원소들을 다 검사해서 S보다 크거나 같은 원소가 있으면 1을 출력해줍시다.

    if min >= 100000001:
        print(0)
    else:
        print(min)

min값이 초기화값 그대로 나와버린다면 S조건을 아예 만족시키지 못하는 경우이므로 0을 출력합시다.

전체코드

from collections import deque
import sys

input = sys.stdin.readline
N,S = map(int,input().split())
lst = deque(list(map(int,input().split())))
quene = deque([lst[0]])
sum_list = sum(lst)
boolean = False
for values in lst:
    if values >= S:
        boolean = True
if boolean == True:
    print(1)
else:
    cum_sum = lst[0]
    lst.popleft()
    min = 100000001

    while True:
        try:
            if cum_sum < S:
                tmp1 = lst.popleft()
                cum_sum += tmp1
                quene.append(tmp1)
            else:
                if len(quene) < min:
                    min = len(quene) 
                tmp2 = quene.popleft()
                cum_sum -= tmp2
        except:
            break

    if min >= 100000001:
        print(0)
    else:
        print(min)

프로그래머스 - 가장 먼 노드

DFS로 풀다가 한참 해맸습니다... 심지어 예전에 유사문제 한번 풀어봤던 것 같은데... 어쨋든 이 문제의 쟁점은 BFS로 level(depth)를 구할 수 있는가 없는가 입니다.

그림과 같이 노드의 간선이 2개 이상인 경우에는 DFS로 노드의 level을 구하기 매우매우매우 어렵기때문에 BFS로 레벨을 구하는 형식으로 접근해야 합니다.

from collections import deque
import sys

시간초과 방지용으로 sysinput 받아서

def solution(n, edge):
    input = sys.stdin.readline

solution 함수 내에 넣어줍시다.

    def bfs(n):
        level = 1
        que.append(n)
        visited[n] = 1

먼저 BFS 함수를 작성할껍니다. 초기 레벨 0은 따로 지정해줄꺼고 레벨 1부터 시작합시다. 지금 막 들어온 노드 1은 방문처리 해주고 que에 넣어줍시다.

        while que:
            for i in range(len(que)):
                a = que.popleft()

BFS level처리의 핵심입니다. BFS를 딱 que값만큼만 돌리면 해당 level값만큼만 노드를 탐색한 샘이 되기 때문에 BFS에서 level을 구할 수 있습니다. 자세한 건 제 예전 포스팅 첨부하겠습니다. https://velog.io/@ghost_dog/%EA%B3%B5%EB%B6%80-2024.01.19-%EC%98%A4%EB%8A%98%EC%9D%98-%EB%B0%B1%EC%A4%80-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4

                for i in range(len(graph[a])):
                    if not visited[graph[a][i]]:
                        visited[graph[a][i]] = 1
                        que.append(graph[a][i])

현재 탐색중인 노드를 인덱스 차원으로 접근하여 graph[노드] = 연결된노드 형식으로 짤껍니다. 만약 탐색중인 노드와 연결된 노드 중 아직 탐색을 안한 노드가 있다면 방문처리를 해주고 que에 추가하여 탐색 예비후보로 지정합시다.

                        ans[graph[a][i]] = level
                        print(graph[a][i],level)
            level += 1

ans라는 리스트에 해당 노드에 접근하면 level을 표시하도록 코딩해줍시다. 그리고 que에 해당하는 걸 다 돌았으면 (현재 level이 끝났으면) level을 1 올려주도록 합시다.

    graph = [[] for _ in range(n+1)]
    while edge:
        [x,y] = edge.pop() 
        graph[x].append(y)
        graph[y].append(x)

시간초과를 피하는 부분입니다. 원래 저는 그래프를 짤 때 습관적으로

    graph = [[0]*(n+1) for _ in range(n+1)]
    while edge:
        [x,y] = edge.pop() 
        graph[x][y] = graph[y][x] = 1

로 작성했었는데 이러면 정상적으로 작동은 하나 DFS는 물론이고 BFS에서까지도 [0]이 쓸데없는 공간을 잡아먹어 시간초과가 뜨곤 했습니다. 따라서 [0]으로 선언하기보단 아예 빈 리스트에 인덱스만 집어넣을 수 있도록 만들어주고 해당 인덱스에 접근하면 value 값으로 그와 연결된 노드만 표시하게끔 코딩했씁니다.

    visited = [0]*(n+1)
    que = deque([])
    ans = [0]*(n+1)
    ans[1] = 0
    bfs(1)

방문배열 초기화, que선언, ans 선언 등을 해주고 맨 첫 노드인 1은 level 0으로 설정해줍시다. 그리고 1을 시작으로 bfs를 돌리면 됩니다.

    return ans.count(max(ans))

마지막으로 level이 가장 큰 노드의 갯수를 구하라 했으므로 max(ans)로 가장 큰 레벨을 구해 ans에 얼만큼 있는지 count해줍시다.

프로그래머스 - 스킬트리

소마 1,2번에 구현 문제가 나온다길래 구현 문제 연습겸 풀어봤습니다.

스킬과 스킬트리라는 변수가 주어집니다. 이 스킬이라는 리스트에 A,B,C가 있으면 스킬트리라는 원소값 순서는 무조건 A가 먼저, 그다음 B, 그다음 C가 와야합니다. 뭐가 중간에 껴있어도 크게 상관없습니다.

이 문제의 핵심은 스킬 리스트에 빠진 원소가 존재하는 경우입니다. 예를 들어 A->K(아무거나)->C라면 A다음에 와야 할 B가 빠져있으므로 스킬트리가 될 수 없습니다.

    ans = 0
    skill = list(skill)

일단 ans를 0으로 선언하고 skill을 list로써 활용하기 쉽게 분리해주겠습니다.

    for i in range(len(skill_trees)):
        tmp = -1
        boolean = False

이제 스킬 트리를 탐색하여 스킬 리스트와 대조해줄 겁니다. tmp값은 기재하겠지만 해당 스킬 트리 어느 인덱스에 스킬이 위치하는가를 기재해줄 겁니다. 값을 작으면~ 이라는 조건으로 대조할거라 -1로 초기화하였습니다.

        for k in range(len(skill)):
            if boolean == True:
                break

스킬 리스트와 대조를 시작하겠습니다. boolean값이 true면 스킬 리스트 순서에 맞지 않다고 가정하여 루프를 깨겠습니다.

            elif skill[k] not in skill_trees[i]:
                tmp = 100
                continue

스킬 리스트가 A->B->C 라고 가정하고 스킬트리가 A->K->C라고 가정해봅시다. A조사는 무난히 넘어갔는데 스킬트리에 B라는 스킬 리스트가 없는 걸 확인할 수 있습니다. 이렇게 되버리면 B이후의 어떤 스킬 리스트도 스킬트리에 존재해서는 안되므로 tmp에 100이라는 고값을 대입해 무슨 값이든 튕겨버리도록 합시다.

            elif skill_trees[i].index(skill[k]) < tmp:
                boolean = True
                continue

만약 현재 조사중인 스킬 트리 내부의 스킬 리스트 위치가 이전에 조사한 스킬 트리 내부의 스킬 리스트 위치보다 작다면 스킬 리스트 순서에 맞지 않으므로 boolean = True를 유도해서 최종 답을 올리지 못하도록 합시다.

            tmp = skill_trees[i].index(skill[k])

다음 스킬 리스트와 비교하기 위해서 tmp를 저장해줍시다.

        if boolean == False:
            ans += 1
    return (ans)

위 과정을 걸쳤음에도 불구하고 boolean값이 False가 나왔다면 최종 답 + 1을 해주고 return 해줍시다.

프로그래머스 - 바탕화면 정리하기

from collections import deque

def solution(wallpaper):
    x = []
    y = []
    sum = 0

    wallpaper = deque(wallpaper)
    while wallpaper:
        tmp = wallpaper.popleft()
        if '#' in tmp:
            x.append(sum)

        for values in tmp:
            if values == '#':
                y.append(sum2)
            sum2 += 1
        sum += 1

    return [min(x),min(y),max(x)+1,max(y)+1]

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

def solution(begin, target, words):
global ans
words = list(sorted(words))

일단 정렬한 값과 정렬하지 않은 값이 다를 수 있기 때문에 단어 리스트 정렬부터 해줍시다.

   begin: hit target: cog words: [hot, dot, dog, lot, log, cog] return : 4 << 예제 1번
begin: hit target: cog words: [cog, log, lot, dog, dot, hot] return : 4

와 같은 경우에요.

       def dfs(begin):
        global ans
        if begin in words:
            visited[words.index(begin)] = 1 

DFS 작성을 시작합니다. 현재 탐색중인 단어를 방문처리 해줍시다.

        sum = 0
        for k in range(len(begin)):
            if begin[k] != target[k]:
                sum += 1
        if sum == 1:
            return ans

현재 탐색중인 단어와 타겟 단어가 문자 1개 차이로 틀리다면 타겟 단어로 갈 수 있다는 것을 의미하므로 재귀를 끝내줍시다.

        for i in range(len(words)):
            sum2 = 0
            for j in range(len(words[i])):
                if words[i][j] != begin[j]:
                    sum2 += 1
            if sum2 == 1 and not visited[i]:
                print(words[i])
                ans += 1
                dfs(words[i])
                return ans

words 리스트에서 하나씩 꺼내서 만약 현재 탐색중인 단어하고 문자 1개 차이로 틀린 단어가 있다면 해당 단어를 탐색에 넣어 재귀를 돌려줍시다. 상단 코드에서 타켓 단어로 가는 것이 증명되었다면(dfs(words[i]) 아래 부분) ans를 return 하여 함수를 끝내주도록 합시다.

    ans = 1
    visited = [0] * len(words)
    if target not in words:
        return 0
    else:
        return dfs(begin)

target이 리스트 안에 없으면 타겟단어를 아예 만들 수 없는 것이므로 0을 return 하고 아니라면 dfs(begin)에서 나온 ans값을 return 하면 타겟단어까지 가는데 걸리는 단어 수 출력이 가능합니다.

프로그래머스 - 등굣길

10억이 넘는 수로 나누라는 것을 보자마자 알았습니다. 네, DP 문제입니다. 물웅덩이로는 통행이 불가하며 집에서 학교까지 가는 최적의 값을 도출하는 문제입니다.

분석

저는 DP문제는 분석을 안하면 항상 푸는 데 난이도가 있더라고요. 해당 문제는 쟁점이 하나 있습니다. 바로 물웅덩이가 1열/1행에 생기는 경우입니다.

https://velog.io/@ghost_dog/%EA%B3%B5%EB%B6%80-2024.02.15-%EC%BD%94%EB%94%A9-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4

왜 1행/1열에 이해가 안가시면 이 게시물 한번 읽어보시면 도움되실 겁니다.

최단거리를 구하기 위해 1행과 1열을 전부 1로 초기화 시키고 있습니다. 근데 어라? 물웅덩이가 1행과 1열에 생겼습니다. 그럼 이 이후는 어떻게 처리해야 할까요? 정답은 장애물이 생긴 이후의 1행 또는 1열은 다 0으로 초기화해야 한다 입니다. 왜냐하면 장애물이 생긴 이후의 공간은 어차피 오른쪽 또는 하강만 가능하므로 방문을 해봐야 최단 거리를 구하는 데 있어 전혀 메리트가 없기 때문입니다. (학교가 맨 아래 오른쪽에 있으니까)

코딩

해당 내용을 생각하며 코딩을 해봅시다.

def solution(m, n, puddles):
    graph = [[0]*m for _ in range(n)]

    for a in range(len(graph[0])):
        if [a+1,1] not in puddles:
            graph[0][a] = 1
        else:
            break
    for b in range(len(graph)):
        if [1,b+1] not in puddles: 
            graph[b][0] = 1
        else:
            break

행,열,물웅덩이 위치를 받고 행열 크기만큼의 원소가 전부 0인 그래프를 생성해줍시다. 만약 웅덩이가 없는 1행/1열이라면 해당 인덱스는 1로 초기화해주고 행열 인덱스 값 1로 초기화중에 1행/1열 자리에 웅덩이가 발생했다! 하면 break로 나와서 원래 값인 0으로 냅둡시다.

    for i in range(len(graph)):
        for j in range(len(graph[0])):
            if i==0 or j==0:
                continue

이제 DP를 돌릴 준비를 합시다. 각 인덱스마다 탐색을 하면서 만약 1행 또는 1열에 접근했다면 점화식을 위한 초기값이므로 건들지 말고 continue를 해줍시다. (어차피 1행 또는 1열은 가는 경우의 수가 1가지밖에 없으므로)

            elif [j+1,i+1] in puddles:
                continue

웅덩이라면 건들지 말고 continue 해줍니다. 이러면 점화식 적용이 안되어 왼쪽+위쪽 이전위치 최단거리 점화식을 사용할 때 이전위치의 웅덩이는 최단거리값이 아예 없는 효과를 줍니다.

            else:
                graph[i][j] = graph[i-1][j] + graph[i][j-1]

마지막으로 최단거리 구하는 점화식 자기자신 최단거리 = 위인덱스 최단거리 + 왼쪽인덱스 최단거리 를 작성해주면 됩니다.

    return graph[n-1][m-1]%1000000007

출력은 DP 초과를 방지하기 위해 10억인가? 를 나눈 나머지를 출력하라고 문제에 명시되어있습니다. 문제 취지는 좋은데 웅덩이 행 열이 뒤바껴서 들어가는 등 좀 미흡한 부분이 존재하는 문제였던 것 같습니다.

*18353번 - 병사 배치하기 *

가장 긴 오름차순 수열 문제에서 한번 꼰 문제입니다. 분석을 할 수 있으면 어렵지 않게 풀 수 있습니다.

분석

위 수열에서는 2,5,3,2,15 라는 체크해둔 수열을 제외하면 병사의 수가 최대가 되도록 할 수 있습니다. 그런데 체크해 둔 수열을 제외하면 뭔가 규칙성이 보이실 겁니다. 맞습니다. 바로 최장 증가 수열입니다.

한마디로 lst를 reverse 시킨 다음 전체 수열의 길이 - 최장 증가 수열의 길이 를 구한 값이 결국 열외해야 하는 병사의 수가 된다고 보시면 될 것 같습니다.

코딩

N = int(input())
lst = list(map(int,input().split()))
lst = list(reversed(lst))
dp = [1]*len(lst)

lst를 선언해주고 뒤집겠습니다. 갯수를 세야하므로 dp값은 전부 1로 초기화하겠습니다.

for i in range(len(lst)):
    maximum = 0
    for j in range(i):

최장 부분 수열을 구해주기 위해서 maximum을 하나 선언해줍니다.

        if lst[i] > lst[j]:
            if maximum < dp[j] + 1:
                maximum = dp[j] + 1

현재 조사중인 인덱스가 이전에 조사중인 인덱스보다 크다면 이전 dp값들 중에서 가장 큰 값 ( 인덱스 전까지의 가장 긴 최장 증가 수열 길이 ) + 1을 maximum에 대입해줍시다.

dp값을 가시화하면 이러한 형태로 나오게 됩니다.

                dp[i] = maximum

그리고 해당 maximum에서 이미 수열 길이 + 1 처리를 해주었으니 dp값에 바로 넣어줍시다.

print(len(lst)-max(dp))  

마지막으로 전에 언급한대로 전체 수열의 길이 - 최장 증가 수열의 길이 를 출력하면 답이 나옵니다.

소마 서류지원에 합격했습니다.

프로젝트 경험이 적고 무언가를 만들어보고 싶은 제 입장에서 소마 연수생이 된다면 더없이 좋은 기회일 것 같습니다.

제 실력이 아직 미흡하고, 아마 합격되지 않을 것이라는걸 잘 알지만 여태 공부한 게 헛되지 않도록 열심히 풀어보겠습니다.

11048번 - 이동하기

미로가 주어지고 각 미로의 칸에 사탕이 놓여있다고 가정할 때, 리스트 (0,0) 에서 (N,M)까지 가는데 주울 수 있는 사탕의 최댓값을 구하는 문제입니다.

언뜻 보면 BFS류라고 생각할 수 있으나 DP로 해결 가능합니다.

분석

어제 저는 14494번을 통해 이차원 리스트에서 DP로 최단거리를 구하는 방법에 대해 익혔습니다. 이 문제도 그러한 방식으로 잘 생각해보면 풀이가 나옵니다.

위 그림에 적어놨듯이

리스트[i][[j]의 최대 사탕 갯수는 i,j의 옆까지 도달하는데 주워온 사탕의 최대 갯수(dp[i][j-1])와 i,j의 위까지 도달하는데 주워온 사탕의 최대 갯수(dp[i-1][j])를 대조해 더 큰값 + 리스트[i][j]의 사탕갯수

를 계산하게 되면 해당 점화식이 도출되게 됩니다.

코딩

N,M = map(int,input().split())
lst = []
for _ in range(N):
    lst.append(list(map(int,input().split())))

먼저 문제에서 주어진 미로를 받아줍시다.

dp = [[0]*M for _ in range(N)]
dp[0][0] = lst[0][0]

dp리스트를 미로 크기와 똑같이 생성하고 dp[0][0]을 점화식을 위해 lst[0][0]과 똑같이 설정해줍니다.

for i in range(N):
    for j in range(M):
        dp[i][j] = max(dp[i][j-1],dp[i-1][j]) + lst[i][j]

이제 분석단계에서 도출한 점화식을 적용하면 됩니다.

if N == 1:
    print(sum(lst[0]))
else:
    print(dp[N-1][M-1])

마지막 출력부분에서 한가지 주의할 점은 N이 1인 경우입니다. N이 1이면 세로길이가 1이 되어 점화식을 참고하여 도출하면 이상한 값이 도출됩니다.

세로길이가 1이라면 어차피 미로의 전체 합이 사탕의 최대 갯수가 되므로 미로의 합산을 출력하고 아니라면 도착지점의 dp값을 도출하면 됩니다.

14494번 - 다이나믹이 뭐에요?

이차원 배열이 주어질 때 시작점에서 끝점까지 가는데의 최단 경로의 수를 구하는 문제입니다. 문제에서 구체적으로 명시하지는 않았는데, 최단 경로가 맞습니다.

분석

먼저 최단 경로는 이러한 식으로 생겼습니다. 문제에서 친절히 맨 위에서 아래,오른쪽으로만 가는 최단 경로의 점화식은

dp[i][j] = dp[i-1][j] + dp[i][j-1]

이라고 언급이 되어있습니다. 하지만 문제는 아래와 오른쪽 뿐만이 아닌 대각선으로도 이동이 가능하다고 되어있습니다. 그래서 점화식에 대각선을 추가하게 되면

dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]

라는 점화식 도출이 가능해집니다.

이제 코딩에 들어갈껀데, 주의할 점은 세로축[0]과 가로축[0]은 위에 그림에 보시다시피 전부 1로 초기화를 진행해야 (해당 행/렬은 접근 가능한 경우의 수가 단 하나) 해당 점화식이 의미가 있습니다.

코딩

n,m = map(int,input().split())
dp = [[0]*m for _ in range(n)]
dp[0][0] = 1
for a in range(n):
    dp[a][0] = 1
for b in range(m):
    dp[0][b] = 1

이차원배열을 하나 선언하고 가로축의 0번째, 세로축의 0번째 행/열을 전부 1로 초기화해줍시다.

for i in range(len(dp)):
    for j in range(len(dp[i])):
        if i == 0 or j == 0:
            continue
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1] 

초기화한 라인을 제외한 구간은 전부 도출한 점화식을 적용시켜줍시다.

print(dp[n-1][m-1]%1000000007)

1000000007로 나눈 나머지를 문제에서 요구한대로 출력해줍시다.

2156번 - 포도주 시식

연속으로 3개를 고르면 안되고 마실수 있는 최대 포도주를 구하는 문제입니다. 전에 풀었던 계단 문제와 비슷한 감이 없잖아 있는데 조금 더 복잡합니다.

분석

본 문제는 세 가지 경우로 나눠서 풀 수 있습니다.

1. i번째 잔을 아예 고르지 않거나 2. i-3번째 잔 -> i-1번째 잔 -> i번째 잔을 통해 올라오거나 3. i-2번째 잔 -> i번째 잔을 통해 올라오는 경우

이렇게 세 가지로 정리할 수 있겠습니다. 자세한 풀이가 필요한 분들은

https://velog.io/@ghost_dog/%EA%B3%B5%EB%B6%80-2024.01.24-%EC%98%A4%EB%8A%98%EC%9D%98-%EC%BD%94%EB%94%A9%EA%B3%B5%EB%B6%80

를 참조하시면 원활하게 이해 가능하실 겁니다.

계단 오르기와 다른 점은 계단은 무조건 밟아야 하지만 이 포도주는 안마셔도 상관이 없으므로 안마시는 경우에는 이전까지의 최대 dp값 (dp[i-1])을 해당 dp에 넣어주면 되겠습니다.

코딩

n = int(input())
lst = []
for _ in range(n):
    a = int(input())
    lst.append(a)

리스트를 받아줍니다.

dp = [0]*n
if n>=1:
    dp[0] = lst[0]
if n>=2:
    dp[1] = lst[0]+lst[1]
if n>=3:
    dp[2] = max(lst[0]+lst[2],lst[1]+lst[2],dp[1])

점화식에서 dp[i-3]이 최소 참조 인덱스이므로 3까지 기본값을 설정해줍니다. 다만, 주의할 점은 lst의 값이 2 이하일 경우 list out of range exception이 발생할 수 있으므로 1과 2값을 직접 지정해주도록 합시다.

for i in range(3,n):
    dp[i] = max(lst[i]+dp[i-2],lst[i]+lst[i-1]+dp[i-3])
    if dp[i] < dp[i-1]:
        dp[i] = dp[i-1]

3부터는 아까 세운 점화식 중 최댓값을 dp[i]에 대입시켜주면 됩니다.

print(max(dp))

마지막으로 dp의 최댓값을 출력하면

정상적으로 해를 도출할 수 있습니다.

17216번 - 가장 큰 감소 부분 수열

가장 큰 감소하는 부분 수열의 합을 구하는 문제입니다.

import copy 
N = int(input())
lst = list(map(int,input().split()))
dp = copy.deepcopy(lst)

합의 최소는 자기 자신이므로 dp값은 기존 리스트 인덱스와 똑같이 초기화해줍니다.

for i in range(len(lst)):
    for j in range(i):
        if lst[i] < lst[j]:
            dp[i] = max(dp[i],dp[j]+lst[i])

각 인덱스마다 순회를 돌며 자기 자신보다 큰 인덱스가 존재하면 자기 자신의 dp값과 자기자신+큰 인덱스의 dp값 을 대조하여 더 큰 값을 넣어주도록 합시다.

print(max(dp))   

해당 dp값에서 제일 큰 값을 출력하면 됩니다.

11055번 - 가장 큰 증가하는 부분수열

가장 큰 증가하는 부분수열을 구하는 문제입니다. 이전에 풀었던 가장 긴 증가하는 부분수열을 응용한 문제라고 보시면 될 것 같습니다.

import copy

n = int(input())
lst = list(map(int,input().split()))
dp = copy.deepcopy(lst)

먼저 dp를 list와 똑같이 초기화해줍니다. 왜냐하면 현재 문제에서 제일 작게 나올 수 있는 값은 부분 수열의 합산이므로 결과적으로 자기 자신입니다.

for i in range(len(lst)):
    for j in range(i):
        if lst[i] > lst[j]:
            dp[i] = max(dp[i],lst[i]+dp[j])

그리고 현재 조사중인 인덱스가 이전 인덱스보다 더 크다면 현재 dp값과 그 이전 인덱스의 dp값 + 현재 인덱스의 합산을 대조하여 더 큰값을 현재 인덱스의 dp값에 대입해줍니다.

해당 문제 테케대로라면 이런씩으로 나옵니다.

print(max(dp))

마지막으로 dp 출력해주면 됩니다.

1965번 - 상자넣기

가장 긴 증가하는 부분수열을 문제화한 문제입니다.

n = int(input())
lst = list(map(int,input().split()))
dp = [1]*len(lst)

1이 수열의 최솟값이므로 받아주고(여기선 박스)

for i in range(len(lst)):
    for j in range(i):
        if lst[i] > lst[j]:
            dp[i] = max(dp[i],dp[j]+1)

현재값이 이전 값보다 크다면 현재값의 dp와 이전값의 dp + 1값을 비교해 더 큰 값을 현재값의 dp로 넣어 가장 긴 증가하는 부분수열을 구체화해줍시다.

print(max(dp))

max(dp)출력하면 됩니다.

15988번 - 1,2,3 더하기 3

시간초과를 피하기 정말정말 어려운 문제입니다.

분석

일단 추가 시간 없음을 보자마자 단순 재귀나 백트래킹으로는 절대 시간 안에 못맞춘다고 봐야합니다. 그리고 조건중에 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. 라는 말이 있으면 DP라고 보는게 타당하겠죠... 위와 같은 과정으로 dp[n] = dp[n-1]+dp[n-2]+dp[n-3]이라는 점화식 도출이 가능합니다.

첫 번째 시도

T = int(input())
ans = []
for _ in range(T):
    ans.append(int(input()))

테스트케이스를 받아 ans에 추가해주겠습니다.

memo = [0]*(max(ans)+1)
memo[0] = 1
memo[1] = 2
memo[2] = 4

memo[2]까지는 점화식에서 음수취급 될 수도 있으므로 2까지 초기화를 진행해줍시다. 시간을 아끼기 위해 테스트케이스 중 제일 큰 값만 돌리고 나머지는 메모 참고하여 답을 출력하려 했습니다.

recursion(max(ans))

이제 재귀를 돌려줍니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

시간 절약을 위해 sysinput과 재귀 depth 상한을 해제해주고

def recursion(n):
    if memo[n]:
        return memo[n]
    memo[n] = ( recursion(n-1) + recursion(n-2) + recursion(n-3) )%1000000009
    return memo[n]

메모이제이션에 있으면 memo[n]을 return, 아니라면 점화식에서 저 식을 나눈 값을 return 해줍시다. 1000000009를 지금 나눠주는 이유는 메모리 제한으로 인해 솔브가 안되는 상황을 방지하기 위해서입니다. (분배법칙 / 모듈러 성질에 의거해 저기서 나누든 답 직전에 나누든 값 출력에 차이는 없습니다.)

for values in ans:
    print(memo[values-1])

출력시켜주면 답은 제대로 나오는데 역시나...

두 번째 시도

재귀는 가독성이 좋지만 callstack을 불러오므로 for문에 비해 상대적으로 시간복잡도가 높습니다. 따라서 for문으로 다시 구현해보기로 했습니다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

sysinput및 setrecursionlimit 선언해주고

T = int(input())
ans = []
for _ in range(T):
    ans.append(int(input()))

테스트케이스를 받아 ans에 추가합니다.

memo = [0]*(max(ans)+1)
memo[0] = 1
memo[1] = 2
memo[2] = 4

DP 초기화를 진행해주고

for i in range(3,len(memo)):
    memo[i] = ( memo[i-1] + memo[i-2] + memo[i-3] )% 1000000009

초기화 다음 단계인 3부터 끝까지 DP를 돌려줍시다.

for values in ans:
    print(memo[values-1])

그리고 ans에서 가장 큰 값을 DP돌려 MEMO에 기록했으니 memo값을 참조하여 답을 출력하면 됩니다.

1463번 - 1로 만들기

세 가지 연산을 사용해서 주어진 수를 최대한 적게 연산하여 1로 만들때, 연산의 횟수를 구하는 문제입니다.

분석

이 문제는 점화식이 주어져 있다고 봐야합니다. 세 가지 연산, 3나누기, 2나누기, 1빼기를 점화식으로써 세울 수 있으면 풀이가 가능합니다.

** 1. 3나누기** dp(9) = dp(3) + 1 이라는 결과가 나오며, dp[i] = dp[i//3] + 1을 도출할 수 있습니다. 2. 2나누기 dp(4) = dp(2) + 1 이라는 결과가 나오며, dp[i] = dp[i//2] + 1을 도출할 수 있습니다. 3. 1빼기 dp[2] = dp[1] + 1 이라는 결과가 나오며, dp[i] = dp[i-1] + 1을 도출할 수 있습니다.

여기서 dp(N)의 결과값은 제일 적은 연산을 사용하여 N을 1로 만드는데 드는 연산수이므로, 저 세 경우 중 제일 적은 연산을 사용한 것을 하나 꼽아 현재 조사중인 수에 대입하면 되겠습니다.

점화식 : min(dp[i] = dp[i//3] + 1,dp[i] = dp[i//2] + 1,dp[i] = dp[i-1] + 1)

코딩

위의 점화식처럼 min으로 비교하여 넣는 것은 불가능하므로 하나씩 비교하며 코딩하면 됩니다.

dp = [0]*1000010

dp[1] = 0
N = int(input())

dp배열을 하나 선언해주고 N을 입력받습니다.

for i in range(2,N+1):
    dp[i] = dp[i-1] + 1

일단 1뺀 경우를 dp[i]에 넣어줍시다. 뭘 먼저하든 상관없습니다.

    if i%3==0:
        dp[i] = min(dp[i//3]+1,dp[i])

그리고 해당 3나눈 경우랑 1뺀 경우랑 비교해서 더 작은걸 dp[i]에 넣어줍니다.

    if i%2==0:
        dp[i] = min(dp[i//2]+1,dp[i])

마지막으로 2나눈 경우랑 방금 전에 dp[i]에 넣은 값이랑 비교해서 더 작은 걸 dp[i]에 넣어줍니다.

print(dp[N])

마지막으로 dp[N]을 출력해주시면 됩니다.

10844 - 쉬운 계단 수

쉽지않은 문제였습니다.

일단 위와같이 각 자릿수의 차이가 1인 수를 게단수라고 할 때, 자릿수가 주어지면 해당 자릿수에서 가능한 계단 수의 경우의 수의 합을 출력하면 되는 문제입니다.

분석

이 문제가 어려운 이유로는 두 가지가 있습니다.

일단 첫번째로 규칙이 까다로워서 점화식 세우는 거 자체가 쉽지 않다는 거고, 두 번째로 점화식을 두 경우로 나누어서 생각해봐야 한다는 점입니다.

일단 첫번째 경우는 위와 같이 N으로 시작하는 계단 수의 경우의 수를 나열해봤을 때 처음에 보고 어? 이거

dp[i][[j] = dp[i-1][j] + dp[i-1][j+1]인가? 또는 dp[i][[j] = dp[i-1][j-1] + dp[i-1][j]인가 싶었습니다.

한마디로 현재 조사중인 경우는 이전 자릿수의 인덱스 -1이거나 +1이라고 생각했습니다.

그러나 두 경우 다 오답이 나옵니다.

해당 문제는 그림의 하늘/초록 형광펜처럼 점화식을 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이라는 위 상대각선 형태로 찾아야 풀이가 가능합니다. 덧붙여서 상대각선 형태여야지만 0번 인덱스를 조사할 때 (파이썬의 경우입니다) -1과 1을 참조하여 점화식으로 0번째 인덱스를 정상적으로 참조하는게 가능합니다.

두 번째 경우는 9로 시작하는 계단 수의 경우입니다. 계단 수가 9로 시작하게 되면 다른 점화식이 적용되지 않습니다.

처음에는 dp[i][[j-1]을 참조하면 해결될까 싶었는데 역시 아니었습니다. 이 경우에는 그림의 노란 형광펜처럼 상 좌대각선의 수를 가져다 써야 정상적인 점화식이 가능합니다.

코딩

N = int(input())
dp = [[0]*9 for _ in range(N)]
for first in range(9):
    dp[0][first] = 1

dp배열을 만들어주고 첫번째 리스트는 다 1로 초기화해주겠습니다.

for i in range(1,N):
    for j in range(9):

2번째 리스트부터 1N까지의 자릿수마다 08로 시작하는 계단 수의 경우를 대입하겠습니다.

        if j==8:
            dp[i][j] = dp[i-1][j-1]

위에 분석한대로 현재 9로 시작하는 계단 수의 경우의 수를 대입해주려면 상 좌대각선의 숫자를 기입해줍시다.

        else:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

그 경우가 아니라면 상 좌우대각선의 수를 하나씩 뽑아 더한 값을 현재 계단 수의 경우의 수에 넣어주면 됩니다.

print(sum(dp[N-1])%1000000000)

마지막으로 문제 조건대로 해당 자릿수의 계단 수의 합산에 10억을 나눈 나머지를 출력하면 됩니다.

1932번 - 정수 삼각형

아래로 내려오면서 대각선으로 값을 합산할 수 있는데 최종적으로 내려왔을 때 가장 큰 값이 되는 수를 구하면 되는 문제입니다.

import copy
N = int(input())
lst = []
for _ in range(N):
    lst.append(list(map(int,input().split())))
dp = copy.deepcopy(lst)

일단 저 정수삼각형을 리스트로써 받고 DP 기록을 하기 위해 리스트를 deepcopy 해주겠습니다.

for i in range(len(dp)-1):
    for j in range(len(dp[i])):

그리고 위에서부터 끝-1 까지 합산을 위해 리스트를 순회하겠습니다.

        if lst[i+1][j] + dp[i][j] > dp[i+1][j]:
            dp[i+1][j] = lst[i+1][j] + dp[i][j]

첫 번째 경우부터 살펴보겠습니다. 현재 DP에는 나올 수 있는 최대값이 기록되어있다고 가정해야합니다.

바로 아래 있는 값 + 현재까지 기록된 최대값 이 바로 아래 기록될 최댓값보다 크다면 바로 아래 기록될 최댓값 = 바로 아래 있는 값 + 현재까지 기록된 최대값으로 표기해줍시다.

        if lst[i+1][j+1] + dp[i][j] > dp[i+1][j+1]:
            dp[i+1][j+1] = lst[i+1][j+1] + dp[i][j]

피라미드는 양 대각선 방향이므로 오른쪽에 있는 인덱스 하나 더 코딩해주시면 됩니다.

print(max(dp[-1]))

마지막으로 가장 아랫 값에서 가장 큰 값이 나올 수 있는 최대 경우의 수이므로 출력하시면 됩니다.

9184번 - 신나는 함수 실행

문제에 주어진 코드를 실행시키려고 하는데 문제에서 해당 코드를 실행시키면 시간이 너무 오래걸릴까봐 걱정이랍니다. 해당 코드를 시간초과가 나지 않게 실행시키는 코드를 작성하면 됩니다.

...보자마자 짐작이 갑니다. DP의 메모이제이션 기법을 사용하면 됩니다.

분석

보통 팩토리얼같은데서 메모이제이션을 사용하면 변수를 하나만 받아서 memo[해당변수] 라는 씩으로 기록하는데 이번에는 변수가 무려 세 개입니다.

보고 딱 떠오른 생각은 3차원 리스트로써 memo[a][b][c] 로 구현하는게 정해겠구나 생각했습니다.

그러나 저는 남들과 같은 길을 걷기는 싫어 조금 창의적으로 구현해봤습니다.

일단 메모이제이션으로써 딕셔너리를 하나 만들고, 3개 변수를 묶은거

(예를 들어 w(20,20,20) 이라면 dict['202020'] = 해당 재귀문 (w(20,20,20)이라던가 w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c) 와 같은 등등...) )

와 같은 형식으로 딕셔너리를 구성해준 후

    if str(a)+str(b)+str(c) in memo.keys():
        return memo[str(a)+str(b)+str(c)]

해당 값이 key값에 존재한다면 해당 값의 key에 해당하는 value를 내보내는 식으로 구현해도 될 것 같았습니다.

첫번째 시도

while True:
    a,b,c = map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    print('w(%s, %s, %s) ='%(a,b,c),w(a,b,c))

먼저 문제에서 -1,-1,-1이 들어오면 입력을 멈추고 그 전까지는 출력하라 했으므로 위와 같이 출력 형식에 맞추어 코딩해줍니다.

memo = dict()

def w(a,b,c):

다음으로 메모이제이션으로써 딕셔너리를 하나 선언하고 w함수 제작을 시작합니다.

    if str(a)+str(b)+str(c) in memo.keys():
        return memo[str(a)+str(b)+str(c)]

아까 말한대로 현재 탐색중인 값이 메모이제이션의 키값에 있으면 해당 value 값으로 return 해줍시다.

    if a>20 or b>20 or c>20:
        memo[str(a)+str(b)+str(c)] = w(20,20,20)
        return memo[str(a)+str(b)+str(c)]

나머지는 문제에 나온 코드 그대로 작성하되 메모이제이션 기법을 사용할 수 있게 메모이제이션에 넣어 해당 메모이제이션 값으로 return 해주도록 합시다.

    if a>20 or b>20 or c>20:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(20,20,20)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]

    if a<b and b<c:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]
    else:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]

나머지도 동일한 방식으로 작성하면 됩니다. 이제 출력해보니까 값은 잘나오는데 알수 없는 이유로 틀립니다.

오답 원인 분석

곰곰히 생각해보니까 메모이제이션 작성을 할때 w(11,11,11)과 같은 형식을 기재받게 되면 memo['111111']이 되는데

이게 나중에 메모 참고를 할때 w(1,111,11)이냐, w(1111,1,1)이냐 구분할 방법이 없기 때문에 나는 오류라고 생각이 됩니다.

그래서 w(a,b,c)사이를 구분해줄 문자를 아무거나 하나 넣어주기로 했습니다.

해결

memo = dict()

def w(a,b,c):

    if a<=0 or b<=0 or c<=0:
        return 1

    if str(a)+'empty'+str(b)+'empty'+str(c) in memo.keys():
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]

    if a>20 or b>20 or c>20:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(20,20,20)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]

    if a<b and b<c:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]
    else:
        memo[str(a)+'empty'+str(b)+'empty'+str(c)] = w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1)
        return memo[str(a)+'empty'+str(b)+'empty'+str(c)]

while True:
    a,b,c = map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    print('w(%s, %s, %s) ='%(a,b,c),w(a,b,c))

단순히 a와b사이, 그리고 b와 c사이 메모이제이션을 원활히 참고될 수 있도록 'empty'라는 문자열을 넣어 구분해주기로 했습니다.

11057번 - 오르막 수

위와 같이 자리수가 주어졌을 때 해당 자리수에서 나올 수 있는 오르막 수가 나오는 경우를 모두 구하는 문제입니다.

분석

일단 저 위에 0,1,2,3,4,5,... 는 마지막 자릿수입니다. 그러니까 수의 자리수가 1이라면 0으로 끝나는 오르막 수는 1개 (0), 수의 자리수가 2라면 1로 끝나는 오르막 수는 2개(수가 0으로 시작할 수 있댔으니가 00,01) 이런 씩입니다.

이렇게 쭉 나열해보면 규칙성이 보입니다. 위에 표기해둔 3자리수의 2로 끝나는 수(6) = 3자리수의 1로 끝나는 수(3) + 2자리수의 2로 끝나는 수(3) 라는 규칙성을 찾아볼 수 있습니다.

이걸 토대로 점화식을 세워보면

N자리수의 i로 끝나는 수 = N자리수의 i-1로 끝나는 수 + N-1자리수의 i로 끝나는 수

이런 형식일 겁니다.

DP느낌대로 1자리수는 죄다 초기 고정으로 박아두고, 2자리수부터는 위 점화식을 기반으로 풀이하면 될 것 같습니다.

코딩

dp = [[0]*10 for _ in range(1001)]
N = int(input())

자리수는 1001까지 나올 수 있다니까 0~9(끝나는 수) X 1001 짜리 이차원 리스트를 DP배열로써 제작해주겠습니다. 그리고 N자리수를 받습니다.

for i in range(10):
    dp[1][i] = 1

DP를 쓰기위한 초기 계산식 1자리수를 전부 1로 초기화해줍시다.

for i in range(2,N+1):
    for j in range(10):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

2자리수부터는, 0~9까지의 끝나는 수에 아까 세운 점화식 N자리수의 i로 끝나는 수 = N자리수의 i-1로 끝나는 수 + N-1자리수의 i로 끝나는 수 => dp[i][j] = dp[i-1][j] + dp[i][j-1] 을 넣어줍시다. 여기서 i는 자릿수, j는 끝나는 수라고 생각하시면 될 것 같습니다.

print(sum(dp[N])%10007)

마지막으로 N에 해당하는 배열 (0~9까지의 끝나는 수 기반 오르막 수의 개수들)의 합산을 10007로 나눈 값(문제 조건)을 출력하면 됩니다.

따라서 하던 DP 잠시 미뤄두고 소마 기출 푸는거에 집중하려 합니다. 기출에 DP도 포함되어 있으니 겸사겸사 공부하겠습니다.

1012 - 유기농 배추

BFS로 1이 뭉쳐있는 구역 갯수를 파악하는 문제입니다.

T = int(input())
que = deque([])
ans = []

테스트케잇,큐,답을 출력할 ans를 선언하겠습니다.

for _ in range(T):

    M,N,K = map(int,input().split())
    graph = [[0]*M for _ in range(N)]
    visited = [[0]*M for _ in range(N)]

테스트케이스만큼 루프를 돌려주고, 가로,세로,배추가 심어져 잇는 위치를 받아서

    for _ in range(K):
        a,b = map(int,input().split()) 
        graph[b][a] = 1

그래프에 표기해줍니다. 주의할 점은 이곳 그래프의 표기 방식은 열과 행이 반대라서 a와 b를 거꾸로 입력받아야 정상적으로 출력됩니다.

    cnt = 0
    for i in range(N):
        for j in range(M):
            if not visited[i][j] and graph[i][j] == 1:
                bfs(i,j)
                cnt += 1

다음으로 cnt변수를 선언하고 그래프를 순회하는 동안 방문하지 않은 지역이고 해당 지역이 1이라면 BFS 탐색으로 돌아줍니다. 탐색 후에는 cnt변수를 1 올려줍니다.

    ans.append(cnt)

for values in ans:
    print(values)

cnt변수를 ans에 추가하고 values로써 출력하면 답이 출력됩니다.

from collections import deque
dx = [-1,1,0,0]
dy = [0,0,1,-1]

BFS는 항상 먹던 그 맛입니다. dx,dy로 상하좌우 탐색 설정하고

def bfs(x,y):
    que.append([x,y])
    visited[x][y] = 1

탐색에 들어왔으면 해당 위치는 방문여부 O로 표기 해줍니다.

    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=N or ny>=M:
                continue

4방향 탐색을 실시하는동안 그래프 밖을 벗어나려하면 continue로 막아주고

            if not visited[nx][ny] and graph[nx][ny] == 1:
                visited[nx][ny] = 1
                que.append([nx,ny])

만약에 탐색하다가 방문을 안했고 해당 지역이 1이라면 탐색 후보지에 넣어주고 방문여부 O로 표기해주면 됩니다.

9461번 - 파도반 수열

그림과 같은 삼각형이 나선 모양으로 놓여저있고 P(N)은 N번째 삼각형 변의 길이라 할때, P(N)을 구하시오.

라는 DP문제입니다.

분석

먼저 저는 P(4)에서 점화식을 도출하려고 봤더니 P(4) = P(3)+P(1) 그리고 P(4) = P(3)+P(2) 라는 식이 두개가 도출되어 점화식을 세우는게 힘들었습니다.

그래서 확실히 구분되는 지점을 봤더니 P(11)을 살펴보면 P(11) = P(10) + P(6)인데 P(10)과 P(6)은 각각 9와 3인 수열에 하나밖에 없는 고유 수라 P(11)의 연산이 가능한 경우는 저것밖에 없었습니다.

따라서 본 문제에서 P(n)은 P(n-1)+P(n-5)라는 점화식 도출이 가능합니다.

코딩

T = int(input())
for _ in range(T):
    n = int(input())
    print(dp(n-1))

먼저 테스트케이스를 받고 받은만큼 dp함수를 재귀로써 돌려줍니다. n-1로 변수에 넣은 이유는 문제는 P(1)부터 시작하지만 저는 P(0)부터 시작하기 때문입니다.

memo = [0]*101
def dp(N):
    if N == 0 : return 1
    if N == 1 : return 1
    if N == 2 : return 1
    if N == 3 : return 2
    if N == 4 : return 2

메모이제이션을 하나 만들어주고 0,1,2 첫 세 삼각형은 1로 초기화, 3,4 두개의 삼각형은 3,4로 초기화를 진행해줍니다. 3,4를 굳이 넣어주는 이유는 예를 들어 초기화 식 없이 점화식 P(4)를 작동하게 되면 P(3) + P(-1)이라는 음수를 불러오는 사태가 발생하므로 이를 방지하기 위함입니다.

    if memo[N]:
        return memo[N]
    memo[N] = dp(N-1) + dp(N-5)
    return memo[N]

메모이제이션에 있으면 해당 값으로 return 하고 아니라면 현재 탐색중인 N값을 메모이제이션에 넣고 해당 값으로 return 하면 됩니다.

11053번 - 가장 긴 증가하는 부분 수열 (LIS)

가장 긴 증가하는 부분 수열을 탐색하는 문제입니다. 이 문제는 이분 탐색과 DP 두 가지 방법으로 풀이할 수 있으나 저는 DP 연습중이므로 DP로 풀겠습니다.

알고리즘 분석

DP로 풀이하는 방법은 다음과 같습니다. 위와 같이 생긴 리스트와 DP가 존재한다면 이러한 씩으로 현재 조사값 이전 값들 중에서 작은 값들이 존재한다면 해당 작은 값들의 DP값들 중에서 제일 큰 DP + 1을 현재 조사값 DP에 넣어주는 씩으로 코딩하면 됩니다.

코딩

N = int(input())
lst = list(map(int,input().split()))
dp = [1]*len(lst)

먼저 수열의 최소 길이는 1이므로 1을 len(lst)만큼 만들어줍니다.

for i in range(len(lst)):
    maximum = 0
    for j in range(i):

현재 조사값은 lst[i], 이전 값들 조사는 lst[j]로 맡겠습니다.

        if lst[j] < lst[i]:
            if maximum < dp[j]:
                maximum = dp[j]
            dp[i] = maximum + 1      

만약 현재 조사값보다 이전 조사값이 더 작다면, 이전 조사값들 중 제일 큰 DP를 maximum에 넣어주고 maximum + 1을 현재 조사값의 DP에 기록하겠습니다.

print(max(dp))

그중에서 가장 큰 값을 출력하면 됩니다.

11722번 - 가장 긴 감소하는 부분 수열

원리만 알면 거의 보너스 문제라고 할 수 있습니다. 마찬가지로 현재 조사 값 이전 값들 중에서 큰 게 존재한다면 이전 값들 max(DP) + 1을 현재 조사값 DP에 대입시켜주면 되는 방식입니다.

N = int(input())
lst = list(map(int,input().split()))
dp = [1]*len(lst)

for i in range(len(lst)):
    maximum = 0
    for j in range(i):
        if lst[i] < lst[j]:
            if maximum < dp[j]:
                maximum = dp[j]
            dp[i] = maximum + 1

print(max(dp)) 

오답 풀이중

15686번 - 치킨 배달

거의 다 푼거 같은데 안풀리는 문제입니다. 지난번 풀이 후 질문을 올려봤는데 라고 친절히 답변해주셔서 저 문제를 살펴봤습니다. ? ㅋㅋㅋㅋㅋㅋ 이게 어떤 말씀하시는지는 감이 잡히는데 (조합 코드 작성할 때 visited를 쓰지 말고 count 변수 증가 형식으로 재귀를 돌려서 백트래킹 부분 시간복잡도를 줄여라? 이런 느낌인 것 같습니다)

정말 한 5시간동안 고민해도 결국 못풀었습니다. 다른 문제 좀 더 살펴보다가 풀어야 할 것 같습니다.

*15686번 - 치킨 배달 *

from collections import deque
import sys
import copy

input = sys.stdin.readline

dx = [-1,1,0,0]
dy = [0,0,1,-1]

def bfs(x,y):
    visited[x][y] = 1
    que.append([x,y])
    while que:
        x,y = que.popleft()
        for i in range(4):
            nx = dx[i] + x
            ny = dy[i] + y
            if nx<0 or ny<0 or nx>=N or ny>=N:
                continue 
            if not visited[nx][ny]:
                if graph[nx][ny] == 2:
                    return graph[x][y]                    
                if graph[nx][ny] >= 0:
                    graph[nx][ny] = graph[x][y] + 1
                    visited[nx][ny] = 1
                    que.append([nx,ny])

N,M = map(int,input().split())
graph = []
visited = [[0]*N for _ in range(N)]
distance = 0
que = deque()
for _ in range(N):
    a = list(map(int,input().split()))
    graph.append(a)
graph_copy = copy.deepcopy(graph)


#살려둘 치킨집을 구하는 경우의 수 
def combination(chicken):
    if len(tmp) == M:
        chicken_choice.append(tmp[:])
        return 
    else:
        for i in range(len(chicken)):
            if visited_chicken[i]:
                continue
            tmp.append(chicken[i])
            visited_chicken[i] = 1
            combination(chicken)
            tmp.pop()
            visited_chicken[i] = 0

tmp = []
chicken = []
chicken_choice = []
for p in range(N):
    for q in range(N):
        if graph[p][q] == 2:
            chicken.append([p,q])
visited_chicken = [0]*len(chicken)

combination(chicken)

distance = 0
ans = []


#치킨거리 구하기 
while chicken_choice:
    choice = chicken_choice.pop()
    for m in range(N):
        for o in range(N):
            if graph[m][o] == 2:
                graph[m][o] = 0
    while choice:
        [x,y] = choice.pop()
        graph[x][y] = 2
    graph_copy2 = copy.deepcopy(graph)

    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1:
                distance += bfs(i,j)
                visited = [[0]*N for _ in range(N)]
                graph = copy.deepcopy(graph_copy2)
                que.clear()                
    ans.append(distance)
    distance = 0
    graph = copy.deepcopy(graph_copy)

print(min(ans))

BFS와 Combination으로 시도하였으나 시간초과 및 메모리 제한으로 실패. 이어서 BFS를 제외한 순수한 점대점 거리로 계산하였으나 역시 실패.

11726번 - 2*N 타일링

분석

이런 문제입니다.

2xn이라는 총 공간이 주어졌을 때 1x2타일과 2x1타일을 이용해서 이 공간을 채울 수 있는 경우의 수를 구하면 되는 문제입니다.

이런 경우 두 가지 유형으로 나눌 수 있는데 먼저 타일이 1x2타일로 끝나는 경우 와 타일이 2x1 타일로 끝나는 경우입니다. 따라서 점화식은 DP(N) = DP(N-1) + DP(N-2)라는 형태로 작성할 수 있습니다.

코딩

N = int(input())
print(dp(N)%10007)

입력을 받고 큰값이 나오니까 해를 10007로 나누라 했으므로 문제대로 따라줍니다.

memo = [0] * 1001
def dp(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

최대 값이 1000이므로 메모이제이션 크기는 1001로 설정해주겠습니다. 1인 경우 1가지 경우밖에 안되므로 1 return, 2인경우 2가지 경우밖에 안되므로 2 return 하고

    if memo[n]:
        return memo[n]

메모이제이션에 데이터가 존재할 경우 해당 데이터를 return

    memo[n] = dp(n-1) + dp(n-2)
    return memo[n]

아까 도출한 점화식을 return 해주면 최종적으로 DP를 활용해 문제풀이가 가능합니다.

11727번 - 2*N 타일링 2

위 문제를 응용한 문제입니다. 이번엔 2x2 타일이 하나 추가됬네요. 초기값하고 점화식만 조금 바꿔주면 될듯 싶습니다.

N = int(input())
print(dp(N)%10007)

N을 입력받고

memo = [0] * 1001
def dp(n):
    if n == 1:
        return 1
    if n == 2:
        return 3

길이가 2일때 2x2타일 하나, 1x2타일 2번, 2x1타일 2번 총 3번으로 만들수 있기 때문에 3으로 초기화를 진행해줍시다.

    if memo[n]:
        return memo[n]
    memo[n] = dp(n-1) + dp(n-2) + dp(n-2)
    return memo[n]

그리고 마지막 부분에 2x2타일도 올 수 있으므로 dp(n-2)를 하나 더 추가하면 정답을 도출할 수 있습니다.

2133번 - 타일 채우기

타일 채우기 끝판왕 문제입니다. 이번에는 크기가 3xN인 벽을 1x2, 2x1 타일로 채우는 방법을 계산해야 합니다.

분석

*1. 타일 값 선언 *

타일을 채우기 시작하는 부분(초기화값)부터 한번 살펴보겠습니다. 일단 공간이 1인 경우에는 타일을 세워서 공간을 못만듭니다! 그리고 공간이 2인 경우에는 이렇게 3개의 경우로 스타트를 끊을 수 있겠습니다. 그리고 제가 하나 간과했던 점이 있는데 GPT한테 물어보니 명쾌한 해답을 내놓더군요. 그건 바로 공간이 0인 경우도 하나의 경우의 수로 취급되어 1로 스타트를 끊을 수 있다는 겁니다! 이제 이걸 코드로 표현하면

    if n == 0:
        return 1
    if n == 1:
        return 0
    if n == 2:
        return 3

이런 느낌으로 초기값을 선언하고 시작할 수 있습니다.

*2. 타일을 끝맺을 때 경우의 수 *

이게 좀 복잡합니다. 일단 위의 예시처럼 2칸만 남았을 때는 3 X DP(N-2) 값으로 점화식을 세우는 게 가능합니다.

그런데 이제 제가 그려둔 오른쪽 예시를 보시면 2XDP(N-짝수) 만큼 계속해서 점화식을 세우는 게 가능하여 결과적으로 N-i가 0이 될때까지 점화식을 세우는 게 가능해집니다...

For문을 사용하여 N-i가 0이 될때까지 점화식을 세우고 메모이제이션에 추가해주는 방식으로 코딩해야 문제풀이가 가능하겠습니다.

코딩

N = int(input())
print(dp(N))

N 입력을 받아주고 dp(N)을 실행시켜줍니다.

memo = [0] * 1001
def dp(n):  
    tmp = 0

    if n == 0:
        return 1
    if n == 1:
        return 0
    if n == 2:
        return 3

메모이제이션을 하나 만들어주고 위에 분석처럼 시작 크기에 알맞게 return 값을 대입해줍시다.

    if memo[n]:
        return memo[n]

메모이제이션에 있는 값이면 해당 메모로 값을 return 해주고

    tmp = 3 * dp(n-2)

없는 값이면 일단 2칸 남았을 경우의 점화식을 세우고 해당 값을 tmp에 추가시키겠습니다.

    for i in range(3,n+1):
        if i%2 == 0:
            memo[n] += 2 * dp(n-i)

핵심 부분입니다.

4칸 이상의 짝수칸이 남았을 경우에는 2 X DP( N - 반복문변수)라는 점화식을 0이 되기 전까지 계속해서 돌려줍니다.

해당 부분은 4칸,6칸,8칸...계속해서 N 전까지 경우의 수가 늘어날 여지가 있기 때문에 for문안에 점화식을 넣어 처리해주도록 합시다.

    return memo[n]

마지막으로 return 메모이제이션을 하면 정답을 도출할 수 있습니다.

9095번 - 1,2,3 더하기

DP문제인데 그냥 재귀로 풀어버렸습니다 하하...

N = int(input())

입력받을 횟수를 받고

for _ in range(N):
    cnt = 0
    ans = []    
    a = int(input())
    dp(0,a)
    print(cnt)

변수를 받아 재귀를 돌려줍니다.

def dp(start,end):
    global cnt
    if start >= end:
        cnt += 1
        return 

만약 start변수가 end와 같아지거나 더 커진다면 cnt를 하나 올리고 함수를 종료합니다.

    for i in range(1,4):
        if sum(ans) + i > end:
            continue

1,2,3을 사용하여 해당 숫자를 어떻게 만드는지가 관건이므로 1~3까지 for문 재귀를 통해 구현하겠습니다. 돌리다가 만약 저장해둔 숫자(1,1,1...) + i(1or2or3) 이 end보다 커진다면 continue를 써서 해당 for문은 스킵하겠습니다.

        ans.append(i)

만약 더해서 커지지 않는다면 해당 경우의 수를 구하기 위해 i를 ans배열에 추가하고

        dp(start+i,end)

재귀로 다시 들어가서 예를 들어 합이 4라면 1111 구하고

        ans.pop()

pop 해서 1112,1113,1114 다 continue에 막히고 111은 끝났으니 112실행 => 합산 4니까 cnt+1 이런씩으로 작동됩니다.

2579 - 계단 오르기

제대로 된 DP 문제입니다. DP는 점화식을 세우는게 제일 중요하니 만큼 문제 분석도 잘 해야 사용이 가능합니다.

분석

해당 문제는 최대값으로 계단을 오르면 점수가 몇점인가 묻는 문제입니다. 최대값으로 오를 수 있는 경우가 두 가지가 있는데,

1. 바로 직전 계단에서 마지막 계단으로 올라올 때
2. 전전 계단에서 마지막 계단으로 올라올 때

이 두가지 경우입니다.

마지막 계단을 기준점으로 삼은 이유는 N번째 계단을 밟아야만 끝난다는 제약이 있기 때문입니다.

1번과 같은 경우는 계단을 연속으로 최대 두 번만 밟을 수 있다는 제약이 있으므로, 위의 그림에 그려둔 것과 같이 N-3번째 계단을 밟고 N-1번째 계단을 밟아야 마지막 계단인 N번째 계단을 밟을 수 있습니다.

반면, 2번과 같은 경우는 제약이 없으므로 N-2번째 계단을 밟고 바로 마지막 계단인 N번째 계단을 밟는 게 가능합니다.

이를 식으로 세워두면

1. DP(N-3)(N-3까지의 최대값) + stair(N-1)(N-1의 계단 점수) + stair(N)(N의 계단 점수)
2. DP(N-2)(N-2까지의 최대값) + stair(N)(N의 계단 점수)

라는 형식으로 세울 수 있습니다.

코드

N = int(input())
stair = []
for _ in range(N):
    a = int(input())
    stair.append(a)

일단 계단의 개수하고 계단에 적힌 값들을 입력받아줍시다.

if N == 1:
    print(stair[0])
elif N == 2:
    print(stair[0]+stair[1])

1을 입력받았을때와 2를 입력받았을때는 점화식 스타트가 N-3부터이기 때문에 예외로 저렇게 처리해줍니다.

else:
    #dp 초기화
    dp = [0]*301
    dp[0] = stair[0]
    dp[1] = stair[0]+stair[1]
    dp[2] = max(stair[0] + stair[2], stair[1] + stair[2])

dp 시작부분입니다. 0과 1, 2는 초기값을 지정해줍시다. 이것 또한 마찬가지로 점화식에서 나오는 최소 변수가 N-3부터이기 때문에 4번째 계단부터 실질적으로 점화식 사용이 가능하기 때문입니다.

    #dp 점화식
    for i in range(3,N):
        dp[i] = max(dp[i-3]+stair[i-1]+stair[i],dp[i-2]+stair[i])

위에 문제분석을 실시한대로

N-3,직전계단,마지막계단을 거쳐서 오는가 직전계단,마지막계단을 거쳐서 오는가

를 판단해주어 그중 더 큰 값을 갖는 값을 dp리스트에 담아주도록 합시다.

그러면 dp값은 결국 해당 계단 위치에서 가질 수 있는 최댓값의 모임이 되고 그중 제일 마지막 계단의 최댓값 => 결국 정답이니까

    print(dp[N-1])

을 해주면 성공적으로 정답을 도출할 수 있습니다.

약 47일간 DFS와 BFS를 해결했으므로 하나만 계속해서 힘든 것도 있고 보다 다양한 알고리즘을 접하고자 오늘부터는 DP 알고리즘에 손대보려고 합니다.

DP란?

Dynamic Programming의 약자입니다.

def dp(N):
    if(N==1): return 1
    if(N==2): return 1
    return dp(N-1) + dp(N-2)
print(dp(10))

여기 피보나치 수열을 구하는 식이 있습니다. 이렇게 코딩을 작성하고 실행해보면 이러한 형식을 거쳐 재귀적으로 실행되겠죠. 그런데 위 실행 형식을 자세히 들여다보면 dp(8)도 두번 쓰이고 dp(7)도 두번 쓰이니 효율이 굉장히 떨어진다는 생각이 들지 않나요? 실제로 컴퓨터에서 위 코드 컴파일을 돌려보면

dp(10)같은 경우는 55로 잘 나오는데 dp(50)같은 경우는 때려죽여도 안나옵니다.

근데 이건 당연한 현상입니다. 위 코드대로 dp(50)을 구할 경우엔 1,000,000 초 = 약 277시간 후에나 컴파일 값이 나올 겁니다.

이렇게 쓸모없는 더미 자료들(위 예시에서의 dp(8),dp(7) 등)을 줄이고 시간복잡도를 2의 n승에서 O(n)으로 획기적이게 줄일 수 있는 알고리즘이 바로 DP의 메모이제이션입니다.

쉽게 설명하면 저 더미 자료들을 배열 하나 만들어서 저장하고, 만약에 현재 조사중인 N이 배열 안에 있는 자료라면 그대로 갖다 써먹는 방식입니다.

memo = [0] * 100
def dp(N):
    if(N==1): return 1
    if(N==2): return 1
    if(memo[N] != 0): return memo[N]
    memo[N] = dp(N-1) + dp(N-2)
    return memo[N]
print(dp(55))

이런 방식으로 배열 하나 만들어주고 메모가 비어있지 않으면 해당 메모로 return 해줍니다. 그리고 함수를 실행할 때마다 memo의 n번째 인덱스에 해당하는 값을 넣어줍니다. 위 식을 실행하면

이런씩으로 시간복잡도가 크게 줄어 금방 컴파일 값을 도출할 수 있습니다.

1003번 - 피보나치 함수

본격적으로 문제풀이를 해보겠습니다. 피보나치 수열에서 N을 호출할 때 0과 1이 각각 몇번 불러와지는지 횟수를 구하랍니다.

T = int(input())
for _ in range(T):
    zero = 0
    one = 0
    memo = [0]*41
    a = int(input())
    fib(a)

먼저 선언을 해주고 메모이제이션을 위한 memo의 길이는 n<41이므로 41로 설정하겠습니다.

    if a == 0:
        print(1,0)
    elif a == 1:
        print(0,1)
    elif a == 2:
        print(1,1)
    else:
        print(memo[a-1],memo[a])

DP는 점화식을 세워주는게 제일 중요한데 위와 같은 예외의 경우가 아니면 1과 0의 호출횟수를 메모이제이션을 통해 알아낼 수 있습니다.

def fib(N):
    if (N == 0): 
        return 0
    if (N == 1):
        return 1
    if (memo[N] != 0):
        return memo[N]
    memo[N] = fib(N-1) + fib(N-2)
    return memo[N]

메모이제이션을 사용하여 메모에 담겨있으면 return memo[N] 형식으로 return 해주고 메모에 담겨있지 않다면 memo[n]을 fib(n-1) + fib(n-2)로 지정해줍시다.

13265번 - 색칠하기

트리가 하나 주어졌을 때 이 트리를 두 가지 색으로 색칠할 수 있는지 묻는 문제입니다. 다만, 이어진 노드끼리는 같은 색을 띨 수 없습니다.

접근

일단 단순히 구현 문제라고 생각하고 노드를 모두 이진 트리로써 취급하여 생각해보기로 했습니다. 레벨 1에서는 빨간색, 레벨 2에서는 흰색, 레벨 3에서는 다시 빨간색 ... 이런씩으로 하여 만약 현재 탐색중인 노드와 탐색할 노드가 서로 이어져있는데 같은 색을 띈다, 이러면 두 가지 색으로 칠하지 못하고 만약 아니라면 두 가지 색으로 칠할 수 있습니다.

아마 그림으로 그려보면 이런 느낌이지 않을까 싶습니다...

선언

t = int(input())
que = deque()

for _ in range(t):
    ans = []
    que.clear()
    a,b = map(int,input().split())

일단 트리를 t만큼 받고 BFS 사용을 위해 que를 받아줍니다. 그리고 a,b로 트리를 받아주기 시작하겠습니다. que를 비우는 이유는 이따 상세히 서술하겠습니다.

    graph = [[0]*(a+1) for _ in range(a+1)]
    visited = [0]*(a+1)

그래프와 방문여부를 선언하고

    for _ in range(b):
        c,d = map(int,input().split())
        graph[c][d] = graph[d][c] = 1

이차원배열로 c노드와 d노드가 이어졌다는 형식으로 표현해줍시다.

    for i in range(1,d+1):
        if not visited[i]:
            ans.append(bfs(i))

그리고 노드중에 방문 안한 노드가 존재한다면 해당 노드는 bfs 탐색을 돌려줍니다.

BFS

from collections import deque
import sys
input = sys.stdin.readline


def bfs(N):
    color = True
    visited[N] = 1
    graph[0][N] = color
    color = False
    que.append(N)

이 문제가 풀다보니 시간제한에 좀 민감한 친구여서 sysinput 선언해주고 시작하겠습니다. 어짜피 색은 두가지므로 True 와 False로 구분해주고 초기 색깔은 True로 지정해준 다음에 초기 색깔을 graph[0]에 넣어주겠습니다 (어짜피 안쓰는 자리, 형식상 인덱스 숫자 맞추려고 +1 선언해서 비는 공간). 그리고 노드 레벨 0은 탐색이 끝난거니까 color는 False로 바꿔주고 (다음 트리 레벨 넘어 갈 때 색 변경) 방문여부 1로 바꿔주고 que에 추가하면서 탐색을 시작합니다.

    while que:
        for _ in range(len(que)):
            connect = que.popleft()
            for i in range(len(graph[0])):

이번에도 이전 문제와 마찬가지로 BFS의 level을 파악해야 하므로 len(que)만큼만 for문을 돌려주겠습니다. 그리고 항상 탐색하듯이

                if not visited[i] and graph[connect][i] != 0:
                    visited[i] = 1
                    que.append(i)

만약 노드끼리 이어져있고 아직 방문을 안했으면 방문처리 하고 다음 탐색구간으로 지정해줍니다.

                    graph[0][i] = color

초반에 레벨 0에서 컬러를 바꾸고 for문에 들어왔으므로 color 변수 그대로 graph[0][i], 즉 다음 탐색지점의 색깔을 대입해주도록 합니다.

                if graph[connect][i] != 0:
                    if graph[0][i] == graph[0][connect]:
                        return 'impossible'

만약 탐색을 할 노드와 현재 탐색 중인 노드의 색깔이 일치한다면 impossible을 return 해주도록 합시다. 0이 아닐 때라는 조건을 건 이유는 만약 graph[0]의 인덱스의 초기값이 0인데 색깔이 아예 안들어있는 인덱스와 맞물리게 되면 조건식이 발동되는 대참사가 일어나므로 지정해줘야 합니다.

        if color == False:
            color = True
        elif color == True:
            color = False

마지막으로 해당 레벨의 색깔을 다 지정했으면 다음 레벨로 넘어갈 때 색깔을 변경해줍시다.

출력

    if 'impossible' in ans:
        print('impossible')
    else:
        print('possible')

최종적으로 ans배열에 impossible이 있다면 불가능, 없다면 가능을 출력해주면 끝납니다.

중요 실수

아까

for _ in range(t):
    ans = []
    que.clear()
    a,b = map(int,input().split())

에서 que.clear()를 해준 이유가 이게 BFS가 실행되다가 return을 만나면 굳이 while에 있는 que값을 다 빼고 나올 필요가 없기 때문에 que에 값이 잔류하게 됩니다.

그래서 이 상태로 que를 초기화시키지 않고 다시 BFS를 돌리면 값이 오염되서 이상한 결과가 나와버립니다. 이것때문에 상당히 시간을 허비해서 앞으로 코드를 짤 때는 이런 변수들 유심히 살펴야겠습니다.