시간복잡도... 알고리즘을 풀때 항상 나의 발목을 잡는 놈이다..
이번에 어떻게 코딩을 해야하는가에 대해서 조금이나마 알게된것같아 이렇게 글을 남겨본다.
코딩
코딩은 어떠한 결과를 만들어내는 수많은 방법들이 있다. 하지만 보편적으로 코드를 짤때 가독성, 유지보수, 재활용성, 시간복잡도 등 많은 점들을 생각해주어야한다.
하지만, 모든것을 다 챙기면서 코딩을 할수는 없다. 상황에 맞게 속도가 빨라야한다면, 가독성을 포기하더라도 시간복잡도를 신경써서 코드를 짜거나, 속도보다는 유지보수 재활용성을 생각한다면, 시간복잡도를 덜 신경쓰고 유지보수에 신경을 더 써야하는것같다.
요점
이번 요점은 수많은 신경써야하는 항목중 알고리즘에 대해 말할 예정이니 시간복잡도를 더욱 신경써서 적어보겠다.
이번에 백준 11659 구간 합 구하기 4 문제를 풀고 느낌이 왔다. 알고리즘을 풀때 그동안 나는 수식을 만들지 않고 모든것들을 온전히 IDE에 적어서 모든 계산을 컴퓨터가 하게 만들었다. 하지만, 이러한 방식 덕분에? 나는 항상 시간 초과라는 문구를 보게 되었고 구글링을 통해 BufferedReader를 사용하면 입력하는 시간을 줄일수 있다는 정보를 발견하고 이런방식, 저런방식 모든방식을 내가 할수있는 범위에서 해보았지만, 역부족이였다. 그러다 수식을 만들어서 컴퓨터가 해야할 계산을 덜어주어 반복문을 덜 돌게 만들어주는 방식의 코드를 발견했다. 이전까지는 컴퓨터 속도가 빠르다보니 이정도 계산은 당연히 컴퓨터가 무리없이 할거라 생각했지만, 나의 생각이 짧았다. 아무리 컴퓨터라도 1부터 1,000,000까지의 합을 구하라는 반복문은 제한시간에 걸린다.. 그러면 우리는 1부터 1,000,000까지의 합을 구하도록 코드를 짜는게 아니라 내가 만들수있는 간단한 수식문제를 만들어 대략 1부터 100까지의 반복문으로 끝낼수있는 그러한 코드를 짜야한다는 점을 알게되었다. 예를 들자면 1번 인덱스부터 1000번 인덱스까지의 합을 구한다면 1번 부터 1000번까지 일일이 더하게 만드는것이 아닌, 이 사이의 누적합을 배열에 집어넣어 원하는 부분을 (-)만 해도 결과가 나오도록 수식을 만들어 불필요한 반복을 하지않게 만들어 주는 점이다.
시간복잡도 나의 정의
시간 복자도는 그리 어려운 말이 아니라, 간단히 컴퓨터가 어떠한 행동을 할때 걸리는 시간이다. 컴퓨터가 해야하는 일이 많을수록 시간복잡도는 점점 높아지는 것이다.
시간복잡도를 적게 들게 만드려면 자바의 입출력이나, 문법에 대한 이해도가 많으면 적게 들게 하기 수월하겠지만, 현재로서는 간단히 컴퓨터가 해야할 일을 대신 내가 조금 처리해주어서 시간복잡도를 더 적게 들게 만들어야한다고 이해하고싶다.
