근자감 민아, 자신감의 근거 찾기!
안녕하세요, /*elice*/ 서포터즈 1기 민아입니다.
이번 기간 동안 저는 알고리즘 수업을 집중적으로 이수했습니다.
2주 동안 알고리즘1의 2, 3주차 내용인 완전탐색법과 분할정복법에 대해 살펴보았습니다.
오늘은 지난 리뷰보다 강의의 내용에 대해 좀 더 다루어보려고 합니다.
본격적으로 두 가지 탐색 방법에 대해 살피기 전에 알고리즘을 공부하면서 기본적으로 숙지하고 넘어가야 할 두 가지 개념에 대한 설명이 이어졌습니다.
이 내용은 매 주차 거듭 언급하시는 중요한 포인트인데요,
바로 문제 해결 절차와 시간 복잡도 입니다.
문제 해결 절차
아래의 내용은 강의 자료 중 일부입니다.
과거의 저를 비롯한 프로그래밍 입문자들이 많이 하는 착각 중 하나는 프로그래밍을 할 때 연필이 필요없다는 것 입니다.
하지만 기본적인 예제를 넘어가고 머리로 계산이 되지 않는 순간, 여러분은 연필을 꺼내서 계산을 해야 합니다.
물론 문제를 보고 어떤 방식으로 접근할지는 경험이나 재능이 필요하겠지만, 재능이 없다고 느낀다면 강의에서 제시해주는 방법대로 차근차근 접근하는 경험을 쌓아 익숙해지는 것도 좋은 방법일 것입니다.
시간복잡도
알고리즘이 제대로 작동하는 것을 알았다면 다음으로 시간 복잡도를 계산해 제한 시간 내에 알고리즘이 작동을 마치도록 해야합니다.
시간 복잡도는 꽤 중요한 이슈가 될 수 있는데, 이는 프로그램의 작동 속도에 비례하기 때문입니다.
시간 복잡도는 몇 개의 명령을 수행하는가 에 대한 것으로 프로그램의 수행 시간을 유추할 수 있습니다.
sum = 0
for i in range(n):
sum = sum + i
이 코드는 n개의 명령이 수행됩니다.
그리고 이를 O(n) 이라고 표기합니다.
상수의 경우 연산의 규모가 매우 커졌을 때 크게 영향을 주지 않기 때문에 일반적으로 생략합니다.
def findNumber(myList, target):
for v in myList:
if v == target:
return True
return False
이 코드는 운이 좋으면 한 번의 연산으로 끝날 수도 있지만 최악의 경우 n번의 연산이 필요합니다.
시간 복잡도를 표기할 때에는 최악의 경우 에 맞추어 표기합니다.
따라서 이 코드의 시간복잡도 역시 O(n)으로 표기합니다.
완전탐색법
완전탐색법은 가능한 모든 경우의 수를 시도하는 것입니다.
이는 연산의 수가 크지 않을 경우 유용하게 사용할 수 있는 방법입니다.
만약 두 개의 요소를 비교하는 경우를 그림으로 그린다면 이렇게 그려볼 수 있을 것 같습니다.
이처럼 완전 탐색은 모든 경우를 다 시도하기 때문에 특별한 증명이 필요없는 방법입니다.
따라서 모든 문제에 대해 우선 완전 탐색을 이용한 접근을 할 필요가 있습니다.
방법 자체도 크게 복잡하지 않기 때문에 강의에서 주어진 예제를 따라서 풀어가다보면 금방 익숙해질 수 있을 것 같습니다.
분할정복법
분할정복법은 하나의 문제를 여러 개의 소문제로 분할하여 각각의 소문제를 해결하고 그 결과를 이용해 전체 문제를 해결하는 방법입니다.
일반적으로 분할정복법은 재귀를 이용해 구현합니다.
첫 시간부터 재귀를 중요하게 다룬 이유입니다.
재귀호출 자체만 두고 본다면 일반적인 반복문보다 시간이나 메모리에서 불리한 점이 있지만, 잘 활용한다면 효율적인 코드를 작성할 수 있습니다.
제가 이해한 내용을 바탕으로 분할정복법을 그림으로 대략 표현하자면 이렇습니다.
완전탐색법을 그릴 때는 끝까지 그리지 못했지만 분할정복법은 끝까지 그려볼 수 있을 정도로 간단히 문제가 해결됩니다.
기저조건에서의 오류가 없다면 논리적으로 맞기 때문에 문제를 작게 나누어 반환되는 값을 바탕으로 문제의 답을 찾습니다.
예를 들어 예제 중 연속부분 최대합을 구하는 문제의 경우
완전 탐색법을 사용한다면 시간 복잡도가 O(n3)이지만,
분할정복법을 이용할 경우 시간 복잡도가 O(N logN)으로 줄어들게 됩니다.
알고리즘이라는 것 자체가 매우 생소했기 때문에 수업 내용을 모두 제대로 이해하고 넘어온 것인지에 대한 확신은 아직은 없습니다.
하지만 독학으로 공부를 해오면서 계속 느꼈던 예제의 부족함에 대한 부분이 충분히 해소 될 만큼 문제를 풀어볼 수 있었습니다.
문제에 대한 해결책을 찾는 연습도 많이 되었지만 그보다 생각한 방식대로 코드를 작성하는 연습이 정말 많이 된 것 같습니다.
매 주차마다 풀어볼 문제가 충분히 제공되기 때문에 한 주에 모두 끝내지 못하고 넘어온 경우도 많았습니다.
문제의 난이도에서 차이가 있었을 수도 있지만 주간 알고리즘의 성적이 매우 올랐습니다!!
건강상의 문제로 이후에 올라온 문제들은 아직 풀지 못했지만, 연습이 생각보다 효과가 있었다고 느껴졌습니다.
항상 코드를 작성할 때마다 내가 생각하는 것을 코드로 어떻게 표현해야하는가에 대한 고민이 많았는데, 3주간 꾸준히 연습을 한 결과 생각한 것을 코드로 옮기는 속도가 빨라졌습니다.
물론 아직 효율적인 문제 해결 방법에는 익숙해지지 못했지만, 짧은 기간 동안 이만큼 성장한 것도 만족스러운 것 같습니다.
다음 글에서도 오늘보다 나아진 모습으로 돌아오겠습니다!
이 글은 /*elice*/ 서포터즈 활동을 위해 작성되었습니다.
elice academy : https://academy.elice.io/explore
민아가 들은 수업이 궁금하다면?
알고리즘1 : https://academy.elice.io/courses/339/info
이 글은 elice gitbook과 블로그에서도 연재됩니다.
elice gitbook: https://elicesupporters.gitbook.io/support/
