아직 알고리즘을 정확히 공부해본 적은 없지만 일단은 간단하게만 짚고 넘어가보자. 나중에 더 공부하게 되면 그때 이 포스팅을 수정해보겠음! - 23.7.25
Squares of a Sorted Array 문제를 풀다가 Follow up: Squaring each element and sorting the new array is very trivial, could you find an O(n) solution using a different approach? 후속 조치: 각 요소를 제곱하고 새 배열을 정렬하는 것은 매우 간단합니다. 다른 접근 방식을 사용하여 O(n) 솔루션을 찾을 수 있습니까? 이라는 걸 보고 O(n) 시간 복잡도가 뭔데? 하고 검색을 시작...
- 빅 오 표기법
O(n) 시간 복잡도는 알고리즘의 실행 시간이 입력 크기 n에 비례하는 선형 시간 복잡도를 나타냅니다. 즉, 입력의 크기에 비례하여 알고리즘의 수행 시간이 선형으로 증가합니다.
만약 알고리즘이 O(n) 시간 복잡도를 갖는다면, 입력 크기가 두 배로 증가하면 알고리즘의 실행 시간도 두 배로 증가합니다. 이러한 선형적인 증가는 입력 크기가 커질수록 알고리즘의 수행 시간이 선형적으로 증가함을 의미합니다.
예를 들어, 크기가 n인 배열의 모든 요소를 한 번씩 순회하는 알고리즘은 O(n) 시간 복잡도를 갖습니다. 또한, 주어진 정수 배열을 비내림차순으로 정렬하는 알고리즘도 O(n) 시간 복잡도를 가질 수 있습니다.
O(n) 시간 복잡도를 가진 알고리즘은 입력의 크기에 따라 선형적으로 처리되기 때문에 매우 효율적인 알고리즘이라고 할 수 있습니다. 따라서 문제에서 O(n) 시간 복잡도로 해결하라는 추가 조건이 있었습니다.
- 왜 비내림차순으로 정렬해야 하는데?
정렬 알고리즘은 기본적으로 오름차순(비내림차순)으로 정렬하는 것과 내림차순으로 정렬하는 것 두 가지로 구분됩니다.
오름차순(비내림차순)으로 정렬하는 알고리즘은 입력 배열이 이미 비내림차순으로 정렬되어 있는 경우에 O(n) 시간 복잡도를 가질 수 있습니다. 왜냐하면, 이미 정렬되어 있기 때문에 추가적인 정렬 작업 없이 배열을 그대로 반환하거나 아주 간단한 조작만으로 정렬을 수행할 수 있기 때문입니다.
예를 들어, 주어진 정수 배열 nums가 이미 비내림차순으로 정렬되어 있다면, 간단히 배열을 반환하거나 배열의 요소들을 뒤집는 작업만으로 오름차순 정렬을 얻을 수 있습니다. 이러한 경우에는 O(n) 시간 복잡도를 가진 알고리즘이 가능합니다.
반면, 일반적인 정렬 알고리즘(예: 퀵 소트, 병합 소트)은 최선, 평균, 최악의 경우 모두 O(n log n) 시간 복잡도를 가집니다. 따라서, 입력 배열이 정렬되어 있든지 아니든지 관계없이 이러한 알고리즘을 사용하면 항상 O(n log n)의 시간 복잡도가 발생합니다.
요약하면, 이미 정렬되어 있는 입력 배열을 오름차순으로 정렬하는 경우에 O(n) 시간 복잡도를 가진 알고리즘이 가능하지만, 일반적인 정렬 알고리즘은 항상 O(n log n) 시간 복잡도를 가집니다.
시간 복잡도를 이해하고 분석하기 위해서는 알고리즘의 동작 원리와 작업량을 이해하는 것이 필요합니다. 따라서 알고리즘을 배우는 것은 시간 복잡도를 이해하는 데 매우 중요합니다.
알고리즘은 문제를 해결하기 위한 절차적인 방법이며, 주어진 입력에 대해 원하는 결과를 얻기 위한 계산 과정을 설계하는 것입니다. 시간 복잡도는 알고리즘이 입력의 크기에 따라 수행하는 작업량을 분석하는 방법 중 하나로, 알고리즘이 얼마나 효율적으로 동작하는지를 판단하는 지표입니다.
알고리즘을 배우면 효율적인 방법으로 문제를 해결하는 방법을 이해할 수 있고, 시간 복잡도를 예측하고 개선하는 방법을 익힐 수 있습니다. 이는 프로그래밍에서 성능을 최적화하거나 대용량 데이터를 다룰 때 매우 중요한 요소가 됩니다.
알고리즘을 공부하면서 주로 사용되는 시간 복잡도 표기법으로는 빅오 표기법 (Big O notation)이 있습니다. 빅오 표기법은 알고리즘이 최악의 경우 얼마나 많은 시간이 소요되는지를 나타내는 방식으로, 알고리즘의 성능을 비교하고 분석하는 데 사용됩니다.
따라서 알고리즘과 시간 복잡도를 공부하여 효율적인 프로그램 작성과 성능 개선에 도움이 됩니다. 다양한 자료와 교재들이 인터넷과 도서관에서 이용 가능하니, 관심 있는 분야에 대해 자세히 공부해보시기를 추천드립니다.
