📌 그래프는 자료구조편과 알고리즘편, 알고리즘-최단경로편, 코드편 총 4편으로 나누어서 작성
📌 "엣지를 지나 그래프의 노드를 탐험해봅시다."
출제빈도 : 낮음
평균점수 : 낮음
다익스트라 알고리즘을 사용해서 최단거리 테이블의 최대값이 몇개인지 세면 끝. 문제에서 가중치는 따로 주어지지 않아서 모든 간선이 가중치 1을 가지는 것으로 계산했다.
잠시 삐끗했던 부분은 새로운 노드를 힙에 언제 삽입하느냐? 와 처음 공부할때도 무슨 역할이었는지 싶었던 19~20번째줄! (다시 정리해둠)
현재노드까지의 최단거리 + 현재노드에서 다음노드로 가는 거리
vs 이전에 계산해둔 다음노드로 가는 최단거리
를 비교하는 것이전에 계산해둔 현재노드까지의 최단거리
가 지금부터 볼 현재노드까지의 최단거리
보다 작다면 볼 필요가 없으므로 이후 과정 생략 (이부분이 없으면 무한루프로 빠진다.)문제에서 주어진 [이긴 선수, 진 선수]
를 그래프 상에서 이긴 선수 -> 진 선수
로 표시하면 아래와 같이 그래프를 그릴 수 있다.
A 선수의 정확한 순위를 매기려면, 모든 선수에 대해 다른 선수에서 A 선수로 오거나(A 선수가 지는 경우), A 선수에서 다른 선수로 가는(A 선수가 이기는 경우) 경로가 모두 합해 전체선수의 수-1
개가 있어야 한다. (정확한 등수를 따질 필요는 없으므로 전체 개수만 맞으면 된다.)
모든 선수쌍에 대해 가능한 경로를 모두 구해야하므로 플로이드 워셜 알고리즘을 사용했다. 그리고 경로가 존재하는 이기는 경우와 지는 경우를 합해서 전체선수의 수-1
이면 답을 하나씩 증가시켰다.
레벨5는 넘 어렵자낭
(DFS/BFS 1문제랑 그래프 1문제 빼고 ㅎ)
첫 시작으로 코테 입문 레벨0 100문제 푸는데 이틀 (2023.06.25 ~ 2023. 06. 26)
레벨1 77문제 푸는데 일주일 (2023.06.28 ~ 2023.07.04)
고득점 키트 45문제 푸는데 20일 (2023.07.05 ~ 2023.07.24)
코테 공부 시작한지 딱 한달만에 고득점 키트까지 완료했다!! 🥳🥳
코테 공부라는 명목 하에 자료구조랑 알고리즘도 공부하면서 벨로그에 틈틈히 정리해뒀으니 나름.. CS 공부도 같이 했다쳐 (?)
학교 다닐때 나름 공부를 열심히 했었는지 대부분 대충 쓱 보고도 아 이거~ 하고 이해가 수월하게 돼서 다행이었다. 자료구조 ㅅㅈㅁ 교수님과 알고리즘 ㅇㅇㅅ 교수님 감사합니다.. (´▽`ʃ♡ƪ)
✏️ 앞으로 할 것 : 백준 solved.ac 클래스 문제 풀기