어떻게 코드를 이렇게 작성하지?
가끔 어려운 문제를 해결하는 코드나 응용프로그램의 코드를 보면 가장 먼저 드는 생각입니다. 내가 배운 프로그래밍 문법을 쓴건 분명한데 보지도 못한 함수, 메서드나 구문들 이해하기 어려운 프로그램의 동작을 볼수 있고, 천재만 이렇게 코드를 작성 할수 있다는 생각이 듭니다.
복잡하고 어려운 코드를 작성할수 있는 사람과 나의 차이는 경험과 지식입니다. 경험은 계속 시행착오를 해야 하지만, 지식은 노력으로 어느정도 따라잡을수 있는데요. 프로그래밍 문법을 배운 후 거의 필수적으로 공부해야 코드를 작성 할수 있는 지식이 ' 자료구조 ' 와 ' 알고리즘 ' 입니다.
응용 프로그램을 설계 할때 가장 중요하게 생각해야 할 항목 중 하나는 데이터 관리입니다. 데이터를 입력받고 어떤 처리를 해 원하는 결과를 내보낼수 있는지는 자료구조와 알고리즘을 알고있냐 모르고 있냐에 따라 코드의 호율자체가 다릅니다.
그 중 자료구조는 프로그래머가 데이터를 메모리에 저장하기 위해 사용하는 방법이고, 이렇게 모은 데이터를 어떻게 처리할것인지가 알고리즘입니다.
수학에서도 어떤 문제를 해결하기 위해서는 상황에 맞는 이론과 공식을 알고 사용해야 원하는 목적을 보다 쉽고 빠르게 해결할수 있습니다. 여기서 이론과 공식이 프로그래밍에서 자료구조와 알고리즘입니다.
자료구조
알고리즘
" 코드의 성능이 좋다 "의 기준을 정할때 시간 복잡도라는 개념을 이용합니다.
- 시간 복잡도
데이터가 적으면 당연히 프로그램의 수행시간이 작아 크게 의미가 없지만, 데이터가 크면 클수록 연산을 많이 한다던가 쓸데없는 중복 계산이 들어가는 등의 이유로 수행시간이 커집니다.
이때 데이터가 커지면 커질수록 코드의 수행시간이 얼마나 커지는 지에 대한 지표를 의미합니다.
알고리즘에 자세하게 설명하겠지만 간단히 O(1)는 코드가 동작하는데 걸리는 시간이 상수시간으로 아무리 큰데이터가 들어와도 일관된 시간을 가집니다.
O(n)에서 y=x 그래프를 연상하시면 됩니다. 데이터가 커질수록 수행시간이 일차식만큼 늘어납니다. O(n^2)나 O(logn) 또한 y=x^2, y=logx 의 수식처럼 데이터와 수행시간의 관계를 가진다고 생각합시다.
물론 엄밀히 따지면 최악의 경우 (가장 수행시간이 커지도록 데이터가 주어진 경우)에 대해 위 함수만큼 수행시간이 증가하지 않거나 점근적 상한 관계를 가지는 의미이지만 자료구조를 공부할때는 O( ) 형식만 기억해도 크게 문제가 되지 않습니다.
