기록을 하려는 동기
기존에는 코테 문제를 풀다가 시간 초과 메모리 초과가 떴을 때 항상 이중 for문 사용 금지라고 생각하고 문제를 해결하곤 했다. 하지만 이 접근 방식에는 한계가 있음을 느꼇다. 초기에 알고리즘을 설계할 때 틀을 잡고 코드를 짜게되면 불필요한 코드 수정을 할 필요가 없기 때문이다. 항상 대략적으로 배열을 어느정도 사이즈로 사용할지 또는 for loop은 몇 번 정도 까지 돌리면 되는지 생각을 하면서 코드를 작성하는 습관을 만드는게 좋다고 생각한다.
코테 풀다가 머리 아파서 다시 한 번 복기하면서 정리
들어가기 전에 혹자가 군대 가기전에 봤던 쉽게 배우는 알고리즘이라는 책에 있는 내용중에 알고리즘은 생각하는 방법을 훈련하는 것이라는 내용이 있다. 어떤 문제를 해결하기 위해 중요한 것과 중요하지 않은 것을 구분하고 문제를 단순화 시켜서 볼수 있는 시각이 필요하다고 생각한다. 문제를 보면서 예를 들어 탐색을 할 때 특정 숫자보다 큰 수들의 갯수를 구하는 문제에서는 이분 탐색을 이용하면 효율적이게 탐색 할 수 있겠다와 같은 아이디어를 떠올리는 것과 함께 구상할 수 있는 능력이 있으려면 역시 이해를 하고 완벽히 그 내용을 숙지하는 것이 중요하다고 생각한다. 기존의 공부 방식은 어렴풋이 이해하고 코테 문제를 직접 설계해서 푸는 느낌보다는 뭔가 유형을 외우는 듯이 풀었던 것 같다. 하지만 난 암기보다는 이해를 해서 공부하는 파이기 때문에,,, 습관을 한 번 고쳐보자.
알고리즘의 수행 시간
알고리즘의 수행 시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지로 표현한다. 무엇이 입력의 크기인지는 대부분 문제에서 주어진다. 정렬로 예를 들면 n개의 수를 정렬한다치면 입력의 크기는 n입니다. 즉 수행 시간은 n개의 입력으로 얼마 만큼의 연산을 수행하는지를 알아내는 것이다.
예를 들어서
for i 1 to n
print i다음 코드는 1부터 n까지 총 n번 i를 프린트 하는 작업을 하는데 걸리는 시간은 n이다.
for i 1 to n
for j in 1 to n
print(i+j)위 코드의 경우는 바깥 쪽에서 n번 수행하고 각 i에 대응하여 n번 더 연산하므로 n*n번 n^2번 수행하는 것이다.
점근적 표기
big-O 표기법
알고리즘의 소요 시간이 입력의 크기 n에 대해 O(n^2)이라면 기껏해야 n^2에 비례하는 시간이 소요됨을 뜻합니다. O(f(n))이 증가해봐야 f(n)을 넘지 않는 모든 함수의 집합을 뜻해요. 예를 들어서 5n^2 + 100000n은 O(n^2)으로 표기할 수 있습니다. 또한 7*n 도 O(n^2)으로 표기할 수도 있구요 상한을 나타내는 표기법이 바로 빅오 노테이션입니다.
코테를 위한 알고리즘
코테를 보는데 시간 복잡도를 일일이 계산을 하기 위한 공부를 해서는 안된다고 생각합니다. 왜냐하면 정해진 시간 내에 문제를 풀고 입력값을 통해서 자료형의 크기를 대략적으로 계산해 어떤 풀이를 전개해 나갈지 고민하는 정도로만 공부하면 충분하다고 생각합니다.
시간 복잡도는
- 평균 시간복잡도
- 최악 시간 복잡도
가 있습니다. 하지만 우리는 최악의 경우만 따져서 문제를 설계하면 되기 때문에 문제에서 주어진 최대 입력값을 계산해보면 대략적으로 어떻게 문제를 접근할 것인지 알 수 있을 것 같습니다.
아래 사이트에서 다음을 참고했습니다.
-
대체로 코딩 테스트에서 시간 공간의 효율성을 제약하기도 한다.
-
따라서, 제약에 따라 사용할 수 있는 알고리즘도 제한된다.
- 공간 :int 자료형은 4byte 4MB의 메모리 공간에 array의 최대 크기는 1,000,000, 백만이다.
- 시간
- python :c/c++보다 느리며 입력의 크기 n이 2000만에 대략 1초가 걸린다고 생각해야 함(c/c++의 경우 1억)
- 입력의 크기가 10,000이라면, O(n^2)의 알고리즘 문제에선 python의 경우 1억회 연산을 하기 때문에 다른 알고리즘을 생각해야한다.
- 공간 : 4MB = 1,000,000, 시간 1초 = 20,000,000
-
이것 외에 입력값으로 주어지는 것들의 경계 값을 주의깊게 살펴봐야한다.(최소 입력, 최대 입력 시작이 0인지 1인지에 따라 결과가 달라지는 것)
