목록백준 1377번 (1)

kakasoo

[node.js] 버블 소트 ( 백준 1377번 )

첫번째부터 두번째까지는 버블 정렬을 시도한 것이다. 그런데 시간 초과가 나왔다. 아니, 문제가 버블 정렬인데 버블 정렬 했다고 시간 초과라니, 문제가 잘못된 것 아닌가 해서 봤더니, A에 들어있는 수가 100만까지 나올 수 있다고 한다. 버블 정렬은 O(n^2) 이었으니까 100만의 제곱이면... 아하, 이건 해결할 수 없는 방식이었다. 이 문제는 버블 정렬을 시키진 않을 거면서 버블 정렬을 하면 몇 번이나 걸리는지를 묻는 문제였다. 그래서 방식을 바꾼 게, 버블 정렬이 어떤 조건에서 발생하는지를 보는 것이었다. 버블 정렬을 하면 각 자리 수는 좌측으로 한 칸씩 이동하게 된다. 예를 들어 예제처럼, 10, 1, 5, 2, 3의 숫자가 있다고 해보자. 1, 2, 3, 5, 10으로 정렬되어야 한다. 그러면..
프로그래밍/알고리즘 풀이 2021. 4. 11. 13:37
이전 Prev 1 Next 다음