알고리즘, 자료구조를 공부안한지 너무 오래된거같다.
사실 언제 공부했는지 기억조차 나지않는다고 이실직고 하는게 옳겠다. ㅋㅋ
당연히 머릿속에 모든것들이 다 초기화된 상태이다...ㅎㅎㅎ
그래서 새로 처음부터 공부를 다시 시작하려고 한다.
자료구조와 알고리즘은 C언어로 공부를 할 생각이다, 그리고 나중에 코딩테스트를 준비할때는 Python을 사용할까 생각중인다.
굳이 C언어를...? C++. Java, Python도 아니고 C를? 이라고 생각할지도 모르겠지만, 나는 C가 좋다.
프로그래밍을 처음 배우면서 접한 언어가 C이기도 하고, 나에게는 C의 투박한 부분들이 매력적으로 다가왔다.
뭐라고 표현해야할까? string의 length를 확인하기 위해서 내가 직접 구현해야하는 부분조차 마치 "나는 내가 필요로 하는 기능들이 어떤식으로 동작하는지 이해하고있어!" 라는 느낌을 받게 해준다랄까?
Python을 포함해서 다른 High Level의 인간에게 친절한 언어들은 list, string의 길이를 구하는 method쯤이야 다 기본으로 내장되어 있지만 어떻게 동작하는지 이해하는 사람들이 얼마나 있을까? 라는 생각이다. (특히 python의 dict)
동시에 C는 빠르지않나? 난 빠른게 좋다. 그래서 F1도 레드불을 좋아하나 싶다.ㅋㅋㅋ
여튼저튼 서론이 불필요하게 길어진거 같은데, 알고리즘 공부를 C언어로 처음부터 다시 해볼생각이다.
핵심은 내가 필요로 하는 기능이 어떤 원리로 돌아가는지 알고싶었다, 가능하면 machine에 가깝도록.
가장 최근 C언어 문제를 언제 접했지? 라고 생각해봤는데, 대략 3~4년전에 회사 식당에서 점심먹으려고 선배랑 같이 마스크쓰고 줄서있으면서 링크드인으로 문제풀었던게 마지막인거 같다.ㅋㅋ
배고파서 대충 흐린눈 하고 풀었던거로 기억한다. (직장인들에게 점심시간이란...!!)
이때도 일 시작하면서 C언어를 안한지 6~7년 지났었는데 좀 집중해서 풀걸 그랬다. 지금 확인해보니 상위15%라네, 원래 12%였는데...???
여튼 다시 공부하면 되겠지 뭐...ㅋㅋ
(지금은 이전직장이 되었지만, 앞으로도 회사가 계속 잘되면 좋겠다.)
알고리즘이란?
알고리즘이 뭘까? 한국말로 바꿔서 설명하기에도 약간 애매한 느낌이 없지않아 있는거 같은데, 주어진 문제를 해결하기 위해 잘 정의된 동작들의 집합 이라고 표현할 수 있을것 같다.
위의 정의에서 보듯이 알고리즘은 우선 주어지는 문제가 있고, 이 문제를 해결하기 위한 순서적인 동작들이 있다.
그리고 이 동작들은 자료구조를 필요로 한다.
알고리즘을 개발하는데 가장 먼저 선행되어야 할 것은 바로 "주어진 문제를 잘 이해하는 것이다." (진짜진짜 중요하다고 생각한다.)
여기서 주어지는 문제는 문제 그 자체뿐 아니라, "문제가 주어지는 상황"도 포함된다.
알고리즘과 자료구조
알고리즘을 다른발로 표현하면 "방법" 정도로 표현이 가능할것 같다.
간단한 예시를 들어보면, 의자를 만들어야 한다고 하자.
의자는 철로만든 의자도 있을것이고 나무로 만든 의자도 있을거다.
만약 의자를 철로 만들어야 한다면 이거는 나무로 의자를 만드는 방법과는 완벽하게 다를것이다.
비록 "앉을 수 있는 의자" 라는 부분에서는 동일할지언정, 철로 만드는 의자는 철을 자르고 용접하는 과정이 필요하다.
하지만 나무의자는 목재를 자르고 못질하는 과정이 필요하다.
즉, 나무의자를 만들것인지 철의자를 만들것인지 구분하고 판단하는 부분이 바로 문제를 잘 이해해야 한다는 부분을 나타낸다.
위의 의자를 만드는 예시에서 "무엇을 어떻게 하라" 라는 부분이 바로 문제 해결 방법이고 "무엇을"이 바로 자료(data)를 의미한다.
그리고 자료는 스스로를 조직화 하는 경우가 많고, 이렇게 조직화된 자료를 바로 자료구조 라고 부른다.
알고리즘과 자료구조의 관계
알고리즘과 자료구조의 관계는 마치 계란의 노른자와 흰자와 비슷하다.
계란을 상상해 볼때 껍질 속에 한정된 양만의 노른자와 흰자만 존재할 수 있는데, 노른자가 커지려면 흰자가 줄어들어야하고 반대로 흰자가 커지려면 노른자가 줄어들어야 한다.
마찬가지로 자료구조가 잘 조직화 되어서 복잡한 구조라면 알고리즘은 간단하게 할 수 있고, 반대로 자료구조가 단순한 구조이면 알고리즘은 복잡해진다.
어떤 알고리즘을 선택해야 할까?
하나의 문제에 대해 해결 방법은 여러가지가 존재할 수 있다.
예를 들어서 sort 알고리즘을 구현한다고 할때 selection, bubble, insertion, quick, radix, merge 등등 여러 다른 종류의 알고리즘이 있다.
그러면 이런 수 많은 종류의 알고리즘 중에서 어떤걸 사용해야하나?
정답은 절대적인 최상의 알고리즘은 없다...!
즉 어떤 상황에서도 찰떡으로 잘 맞아 떨어지는 알고리즘은 존재하지 않고, 항상 주어진 문제와 제한적인 상황을 이해하고 판단한 뒤에서야 "가장 적합한 알고리즘"을 선택할 수 있다.
일반적으로 정렬 알고리즘 중에서 퀵정렬을 가장 좋은 알고리즘으로 생각하는데, 많은 경우에 있어서 사실 퀵소트는 좋은 알고리즘이지만 모든 상황에서 만능은 아니다.
data의 유동성이 심하다면 퀵소트 보다는 힙소트나 인서트 소트가 유효할수도 있고, 다중 인덱스를 사용하는 경우 보다 안정적인 머지소트가 보다 적합할 수 있다.
또한 알고리즘의 속도와 메모리 관계또한 이해해야 하는데, 퀵정렬이 빠르긴 하지만 재귀 호출이나 stack에 필요한 정보를 저장하는 방식으로 추가적으로 메모리를 더 필요로 하게 된다.
즉 속도를 위해서 메모리를 희생한다는 이야기인데, 반대로 선택 정렬은 속도는 퀵소트에 비해서 느리지만 추가적인 메모리가 필요하지는 않다. (단순히 data 저장에 필요한 memory만 있으면 됨)
이런식으로 알고리즘을 선택하는데 확정되어있는 기준이 없기 때문에, 상황과 환경에 맞게 선택해야한다.
따라서 다양한 알고리즘을 충분히 이해하는것이 큰 도움이 된다는 이야기!
