-
99클럽 코테 스터디 3일차 TIL: Graph, Dijkstra, 프로그래머스, 가장 먼 노드Today_I_Learned/Algorithm 2024. 6. 12. 23:40
문제
https://school.programmers.co.kr/learn/courses/30/lessons/49189
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
통과 여부Pass
나의 접근법
- Dijkstra 채택( Dijkstra 의 조건1. 어느 한 Node 로 부터 나머지 모든 Node 간의 거리를 구해야 함. 조건2. Node 간 거리는 모두 양수여야 함.)
- 최대 거리를 나타내는 변수 longgest 를 두고, 시작점과 어느 한 Node 의 거리가 longgest 의 값보다 크면 해당 거리로 longgest 를 갱신한다.
- longgest 와 동일한 거리가 측정되면 정답 수를 + 1 하고, longgest 가 갱신되면 정답 수를 1로 초기화한다.
문제가 대놓고 다익스트라 조건을 모두 충족하고 있었기 때문에 Dijkstra 를 복습하고 문제를 마주하니 무리 없이 쉽게 풀 수 있었다.
def solution(n, edge): answer = 0 adj = [[] for _ in range(n+1)] for e in edge: adj[e[0]].append(e[1]) adj[e[1]].append(e[0]) dist = [50001] * (n+1) # 문제에서 간선의 최대 수가 50000 최대 거리인 50000 보다 큰 값으로 초기화한다. dist[1] = 0 visited = [False] * (n+1) q = [(1, adj[1])] longgest = 0 for curr, next in q: for n_v in next: if visited[n_v]: continue if dist[n_v] > dist[curr] + 1: dist[n_v] = dist[curr] + 1 if longgest < dist[n_v]: longgest = dist[n_v] answer = 1 elif longgest == dist[n_v]: answer += 1 q.append((n_v, adj[n_v])) visited[curr] = True return answer print(solution(6, [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]))
평소보다는 문제를 쉽게 풀었지만 이번 경험은 단순히 문제를 푸는 것을 넘어 또 다른 의미를 갖고 있다. 바로 내가 잘 알고 있는 유형과 그렇지 못한 유형이 존재하고 그것을 파악할 수 있었다는 것. 이전까지는 그저 모든 코딩 테스트 문제는 나에게 어려울 뿐이라고 막연히 생각했었다. 그러나 항해99스터디를 통해 다양한 유형의 문제를 꾸준히 접하다보니 꼭 다 풀지 않더라도, 그저 문제를 훑어 보는 경험뿐이라 하더라도 그것이 나에겐 학습법을 개선할 수 잇는 계기가 된다는 것을 알게 되었다.
늘 시간에 쫓겨, 게으름이 밀려 밀린 코딩 테스트 앞에서 허덕이는 기분이었는데, 그 동안 시간 낭비만 한 것은 아니라는 사실을 깨닫는 긍정적인 경험이었다.
참고한 그리디 설명 영상
1.
학습 페이지
www.inflearn.com
2.
학습 페이지
www.inflearn.com
'Today_I_Learned > Algorithm' 카테고리의 다른 글
99클럽 코테 스터디 5일차 TIL: 배열, Leetcode 1476. Subrectangle Queries (0) 2024.06.15 99클럽 코테 스터디 4일차 TIL : Graph, 프로그래머스, 순위 (0) 2024.06.13 99클럽 코테 스터디 1일차 : 그리디, 구명보트(프로그래머스) (0) 2024.06.06 MST 탐색(프림 Prim / 크루스칼 Kruskal) (0) 2023.04.16 탐욕 Greedy Algorithm (0) 2023.04.16