[코딩 테스트 합격자 되기]시간복잡도
해당 블로그는 아래 강의 내용을 중 "시간 복잡도"부분을 요약한 내용 입니다.실제 강의영상에는 별도로 강의자료를 제공 합니다.강의 영상 : https://inf.run/H9yxm 시간 복잡도란?시간 복잡도(Time Complexity)는 알고리즘의 효율성을 평가하는 데 사용되는 개념으로, 입력 크기에 따라 알고리즘의 실행 시간이 어떻게 변하는지를 나타냅니다. 이는 코딩 테스트뿐만 아니라 실제 소프트웨어 개발에서도 매우 중요한 개념입니다. 알고리즘 정의 및 특성먼저, 알고리즘이란 문제를 해결하기 위한 일련의 규칙이나 절차를 의미합니다. 알고리즘은 다음과 같은 주요 특성을 가져야 합니다:1. 정확성: 알고리즘의 각 단계는 명확하고 변하지 않아야 합니다.2. 유일성: 각 단계마다 다음에 수행할 작업이 명확해야 합니다.3. 실현 가능성: 알고리즘은 실제로 구현 가능하고 실용적이어야 합니다.4. 입력과 출력: 알고리즘은 명확한 입력과 출력을 가져야 합니다.5. 유한성: 알고리즘은 반드시 종료되어야 합니다. 무한 루프에 빠지면 안 됩니다. 알고리즘 성능 측정 방법알고리즘의 성능을 측정하는 방법에는 여러 가지가 있지만, 대표적인 두 가지 방법은 다음과 같습니다:- 절대 시간 측정: 특정 하드웨어에서 알고리즘을 실행하는 데 걸리는 시간을 측정합니다. 하지만 하드웨어 성능에 따라 결과가 달라질 수 있어 일반적으로 사용하기에는 한계가 있습니다.- 연산 횟수 측정: 하드웨어와 무관하게 알고리즘이 수행하는 연산의 횟수를 측정합니다. 이는 보다 신뢰할 수 있는 방법입니다. 빅오 표기법 (Big-O Notation)빅오 표기법은 알고리즘의 최악의 경우 시간 복잡도를 나타내는 데 사용됩니다. 이는 상수와 낮은 차수 항을 무시하고, 가장 큰 성장률을 가진 항을 중심으로 표현합니다. 예를 들어, O(n^2), O(n), O(log n), O(n log n) 등이 있습니다.### 일반적인 시간 복잡도다음은 코딩 테스트에서 자주 접할 수 있는 시간 복잡도 예시입니다:- O(1): 입력 크기에 상관없이 항상 일정한 시간이 걸리는 경우.- O(n): 입력 크기에 비례하여 시간이 증가하는 경우.- O(n^2): 중첩된 반복문처럼 입력 크기의 제곱에 비례하여 시간이 증가하는 경우.- O(log n): 이진 탐색처럼 로그 스케일로 시간이 증가하는 경우.- O(n log n): 합병 정렬과 같은 알고리즘의 경우. 시간 복잡도의 실제 적용코딩 테스트에서 시간 복잡도를 이해하는 것은 매우 중요합니다. 예를 들어, 중첩된 반복문을 사용하면 O(n^2) 복잡도가 발생하며, 이는 큰 입력에 대해 비효율적일 수 있습니다. 따라서 입력 크기 제한을 고려하여 적절한 자료 구조와 알고리즘을 선택해야 합니다. 코딩 테스트에서의 시간 복잡도 활용코딩 테스트 문제를 풀 때, 문제에서 주어진 입력값의 크기를 바탕으로 우리가 사용할 수 있는 알고리즘의 시간 복잡도를 추측할 수 있습니다. 예를 들어, 입력값의 크기가 100만이라면, O(n^2) 알고리즘은 시간 초과가 날 가능성이 높습니다. 이때는 O(n log n) 또는 O(n) 알고리즘을 사용하는 것이 바람직합니다. 결론시간 복잡도는 코딩 테스트에서 알고리즘의 효율성을 평가하는 중요한 도구입니다. 이를 통해 우리는 더 나은 성능을 가진 알고리즘을 선택하고, 시간 초과를 방지할 수 있습니다. 알고리즘의 정확한 연산 횟수를 측정하는 것도 중요하지만, 빅오 표기법을 사용하여 대략적인 성능을 파악하는 것이 더 중요합니다. 이를 통해 문제의 요구 사항을 충족하는 최적의 알고리즘을 선택할 수 있습니다.이상으로 시간 복잡도에 대한 블로그 포스트를 마치겠습니다. 읽어주셔서 감사합니다! 다음 포스트에서는 더 흥미로운 알고리즘 주제로 찾아뵙겠습니다.
