🔔문제 소개

---

🔗연습 요약

연습 시간	연습 문제 수	카테고리
90 분	6 문제	그리디, 다이나믹 프로그래밍, 정렬, 그래프, 구현 중 랜덤 3 선택

🔗문제 요약

문제	번호	난이도	시간 내 풀이 여부	풀이 여부
가희와 3단 고음	16162	S4	O	O
이상한 하노이 탑	15500	S2		바로가기
민겸 수	21314	S2		바로가기
무한부스터	17391	S1		바로가기
Boardle	24939	S3		문제가 너무 노잼이라 pass
알고리즘 수업 - 깊이 우선 탐색 1	24479	S2	O	O

📑풀이 노트

---

📌가희와 3단 고음

문제 요약

첫 항과 공차가 주어지고, $N$만큼 숫자가 주어질 때, 가장 긴 수열의 길이를 출력하여라

풀이 요약

풀이 순서	풀이 시간	시도횟수	카테고리
2	H+58	2	그리디

참가자들의 음계를 리스트로 입력받은 뒤, 수열의 첫 항부터 공차대로 증가시켜가며 같은 경우 res를 증가시킨다.

코드

1. 메모리초과 코드

n, a, d = map(int, input().split())
note = list(map(int, input().split()))
l = max(note)
s = [i for i in range(a, l+1, d)]

j = 0
res = 0

for i in note:
    if j == l+1:
        break
    if i == s[j]:
        res += 1
        j += 1

print(res)

2. 정답 코드

n, a, d = map(int, input().split())
note = list(map(int, input().split()))
l = max(note)
#s = [i for i in range(a, l+1, d)]

j = 0
res = 0
s = a
for i in note:
    if j == l+1:
        break
    
    if i == s:
        res += 1
        s += d

print(res)

회고

수열을 바로바로 구해 넘길 수 있음에도 굳이 리스트에 저장해 메모리초과를 받았고, 금방 수정할 수 있는 문제에 난이도도 그리 어렵지 않은 문제였음에도 불구하고 시간이 너무 많이 들어갔다.

📌알고리즘 수업 - 깊이 우선 탐색

문제 요약

첫 항과 공차가 주어지고, $N$만큼 숫자가 주어질 때, 가장 긴 수열의 길이를 출력하여라

풀이 요약

풀이 순서	풀이 시간	시도횟수	카테고리
1	H+25	3	그래프 이론

코드

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

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
count = 1

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

def dfs(v):
    global count
    visited[v] = count
    graph[v].sort()
    for g in graph[v]:
        if visited[g] == 0:
            count += 1
            dfs(g)

dfs(r)

for i in range(1, n + 1):
    print(visited[i])

회고

기본적인 DFS 문제, 처음 구현했을 때, 변수를 잘못선택해 메모리초과와 재귀 오류가 발생하였다 주의하자.

전체 회고

---

전체적으로 너무 오래걸린다. 실버 수준의 문제였음에도 불구하고 두 문제 밖에 못 푼것이 너무 아쉽다.
연습 또 연습하자