목록백준 2252 줄세우기 (1)

공부 흔적남기기

[백준] [JAVA] 줄세우기 2252 위상정렬 메모리 초과

위상정렬이란 정해진 순서가 있고 해당 순서대로 정렬한 것을 의미한다.정해진 순서란 작업들 간의 관계이다. 즉 의존하고 있는 작업이 반드시 의존 되고 있는 작업보다 뒤에와야 한다.예를들어 A가 B를 의존하고 있다고 가정하면 B A 순서여야한다. 1학년 때 알고리즘 기초를 수강해야 2학년때 알고리즘 심화를 들을 수 있는 것과 같다. 위상정렬은 인접행렬과 인접리스트로 구현할 수 있는데 이때 인접행렬은 시간복잡도가 O(V^2) 이고 공간 복잡도도 마찬가지이다 하지만 인접리스트는 시간복잡도가 O(V+E) 이며 공간 복잡도는 O(V+E)이다 인접 행렬을 사용하여 메모리가 초과가 난 코드 32000 * 32000 *4 거의 4000MB를 사용하게 되어 메모리 초과가 발생한다.시간 복잡도도 1초를 넘길 수 있다.imp..
코테/백준 2024. 11. 4. 23:53
이전 Prev 1 Next 다음