728x90
반응형
오늘은 코딩테스트를 쳤다. 4문제 중에 3문제를 풀고 마지막 문제에서는 시간초과가 발생했다.
그래도 저번주 코딩테스트보다는 난이도가 낮았다고 생각한다.
마지막 문제에서 dfs + 이진탐색이라니 ... !! 신박한 유형이었다고 생각한다.
아무튼 ... 힘들었따...!
- 이번 주 진행된 팀 스터디에서 얻은 인사이트는 무엇인가요?
<기술 매니저님 피드백>
높이(레이저, 나무 등) -> stack
https://www.acmicpc.net/problem/1939
1939번: 중량제한
첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이
www.acmicpc.net
마지막 문제가 1939번 중량제한이었다. 처음에는 dfs로 풀었는데 시간초과가 발생했다. 왜 이진탐색을 써야하는지 왜 단순히 dfs만으로 안 풀리는지 그 이유를 정확하게 매니저님께서 알려주셨다. 가려운 곳을 긁어주신...
a -> b 경로 중 최대 weight 찾기
모든 경로 탐색 -> visited[] true 하고 dfs() 호출 후 다시 visited[] false (백트래킹)
=> 시간복잡도가 기본 dfs보다 커짐
=> 시간 초과 / 메모리 초과 원인
728x90
반응형
댓글