[코딩 테스트 합격자 되기]시간복잡도

해당 블로그는 아래 강의 내용을 중 "시간 복잡도"부분을 요약한 내용 입니다.실제 강의영상에는 별도로 강의자료를 제공 합니다.강의 영상 : 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) 알고리즘을 사용하는 것이 바람직합니다. 결론시간 복잡도는 코딩 테스트에서 알고리즘의 효율성을 평가하는 중요한 도구입니다. 이를 통해 우리는 더 나은 성능을 가진 알고리즘을 선택하고, 시간 초과를 방지할 수 있습니다. 알고리즘의 정확한 연산 횟수를 측정하는 것도 중요하지만, 빅오 표기법을 사용하여 대략적인 성능을 파악하는 것이 더 중요합니다. 이를 통해 문제의 요구 사항을 충족하는 최적의 알고리즘을 선택할 수 있습니다.이상으로 시간 복잡도에 대한 블로그 포스트를 마치겠습니다. 읽어주셔서 감사합니다! 다음 포스트에서는 더 흥미로운 알고리즘 주제로 찾아뵙겠습니다.

[코딩 테스트 합격자 되기]큐 접근하는게 효율적인 경우

큐를 사용하여 문제를 해결하는 것은 때로는 경험이나 직감에 기반하기도 합니다. 그러나 일반적으로 다음 두 가지 주요 특성을 가진 문제들이 큐를 사용하여 해결될 가능성이 높습니다.선입선출 특성 (First In, First Out, FIFO)큐는 선입선출 방식으로 동작합니다. 즉, 먼저 삽입된 요소가 먼저 제거됩니다. 따라서, 선입선출 특성을 이용해야 하는 문제에서 큐가 효과적입니다.순차적 처리 (Sequential Processing)큐는 순차적으로 데이터를 처리하는 데 유용합니다. 데이터를 순서대로 처리해야 하는 문제에서 큐를 사용하는 것이 적합합니다.큐로 접근하는 게 효율적인 경우큐의 대표적인 예시는 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘입니다.BFS를 사용하여 그래프의 모든 노드를 탐색하는 과정은 아래와 같습니다. 예를 들어, 다음과 같은 그래프가 있을 때 시작 노드부터 모든 노드를 탐색합니다.이를 코드로 구현하면 아래와 같습니다.python코드 복사from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: node = queue.popleft() print(node, end=' ') for neighbor in graph[node]: if neighbor not in visited: queue.append(neighbor) visited.add(neighbor) 위의 코드에서 큐는 현재 탐색 중인 노드를 저장하고, 각 노드의 이웃을 큐에 추가하여 순차적으로 탐색합니다. 이 방법은 선입선출 특성을 이용하여 각 노드를 너비 우선으로 탐색하므로 효율적입니다.큐로 접근하는 게 효율적이지 않은 경우반대로, 큐가 비효율적인 경우도 있습니다. 대표적인 예로는 배열의 특정 요소에 접근하여 값을 수정하는 문제가 있습니다.배열의 특정 요소에 접근하여 값을 수정하는 과정은 아래와 같습니다.주어진 배열의 특정 인덱스에 값을 삽입하거나 수정합니다.이를 코드로 구현하면 아래와 같습니다.def modify_array(arr, index, value): if 0 이 코드에서, 큐를 사용하여 각 요소를 저장하고 꺼내어 값을 수정할 수도 있습니다. 그러나 이는 불필요한 메모리 사용과 연산을 증가시킵니다. 단순히 배열 인덱스를 사용하여 접근하는 것이 더 효율적입니다.def modify_array_with_queue(arr, index, value): queue = deque(arr) for i in range(len(queue)): if i == index: queue[i] = value return list(queue) 이와 같이, 배열의 특정 요소에 접근하여 값을 수정하는 문제는 큐를 사용하지 않는 것이 더 효율적입니다. 큐의 선입선출 특성이 불필요하게 사용되기 때문입니다.따라서, 큐를 사용해야 하는 문제는 주로 선입선출 특성을 활용해야 하는 문제나 순차적으로 데이터를 처리해야 하는 문제입니다.

[코딩 테스트 합격자 되기]스택으로 접근하는게 효율적인 경우

스택을 사용하여 문제를 해결하는 것은 때로는 경험이나 직감에 기반하기도 합니다. 그러나 일반적으로 다음 두 가지 주요 특성을 가진 문제들이 스택을 사용하여 해결될 가능성이 높습니다.후입선출 특성 (Last In, First Out, LIFO)스택은 후입선출 방식으로 동작합니다. 즉, 나중에 삽입된 요소가 먼저 제거됩니다. 따라서, 후입선출 특성을 이용해야 하는 문제에서 스택이 효과적입니다.재귀적 구조 (Recursive Structure)재귀적으로 정의된 문제를 반복문을 사용하여 해결할 때 스택이 유용합니다. 함수 호출의 재귀적인 구조를 명시적으로 스택을 사용하여 구현할 수 있습니다.스택으로 접근하는 게 효율적인 경우스택의 대표적인 예시는 괄호의 유효성을 검사하는 문제입니다.괄호의 유효성을 검사하는 과정은 아래와 같습니다. 예를 들어, 문자열 "(([]))"이 주어졌을 때, 괄호가 유효한지 검사합니다.이를 코드로 구현하면 아래와 같습니다.python코드 복사def is_valid_parentheses(s): stack = [] mapping = {")": "(", "]": "[", "}": "{"} for char in s: if char in mapping: top_element = stack.pop() if stack else '#' if mapping[char] != top_element: return False else: stack.append(char) return not stack 위의 코드에서 스택은 열린 괄호를 저장하고, 닫힌 괄호를 만날 때마다 스택의 최상단 요소와 비교합니다. 이 방법은 후입선출 특성을 이용하여 괄호의 짝을 맞추므로 효율적입니다.스택으로 접근하는 게 효율적이지 않은 경우반대로, 스택이 비효율적인 경우도 있습니다. 대표적인 예로는 배열의 합을 계산하는 문제가 있습니다.배열의 합을 계산하는 과정은 아래와 같습니다.주어진 배열의 모든 요소를 더합니다.이를 코드로 구현하면 아래와 같습니다.python코드 복사def sum_array(arr): total = 0 for num in arr: total += num return total 이 코드에서, 스택을 사용하여 각 요소를 저장하고 꺼내어 더할 수도 있습니다. 그러나 이는 불필요한 메모리 사용과 연산을 증가시킵니다. 단순히 반복문을 사용하여 배열의 합을 구하는 것이 더 효율적입니다.python코드 복사def sum_array_with_stack(arr): stack = [] for num in arr: stack.append(num) total = 0 while stack: total += stack.pop() return total 이와 같이, 배열의 합을 계산하는 문제는 스택을 사용하지 않는 것이 더 효율적입니다. 스택의 후입선출 특성이 불필요하게 사용되기 때문입니다.따라서, 스택을 사용해야 하는 문제는 주로 후입선출 특성을 활용해야 하는 문제나 재귀적인 구조를 반복문으로 해결해야 하는 문제입니다.

[코딩 테스트 합격자 되기]그리디로 접근해야 하는 문제를 판단하는 방법

그리디 알고리즘으로 해결 가능한 문제를 판단하는 것은 때로는 경험이나 직감에 기반하기도 합니다. 그러나 일반적으로 다음 두 가지 주요 특성을 가진 문제들이 그리디 알고리즘을 사용하여 해결될 가능성이 높습니다.탐욕적 선택 속성 (Greedy Choice Property)그리디 알고리즘은 매 단계에서 가장 최적이라고 생각되는 선택을 합니다. 즉, 현재 상황에서 가장 좋은 선택을 함으로써 문제를 해결해 나가는 방법입니다. 따라서, 매 단계의 탐욕적 선택이 최종 해답으로 이어지는 경우에 그리디 알고리즘이 효과적입니다.최적 부분 구조 (Optimal Substructure)주어진 문제의 최적 해결 방법이 해당 문제의 부분 문제들의 최적 해결 방법을 포함하는 경우입니다. 즉, 큰 문제의 최적의 해결책을 찾기 위해 작은 문제들의 최적의 해결책을 사용할 수 있어야 합니다.그리디 알고리즘으로 접근하는 게 효율적인 경우그리디 알고리즘의 대표적인 예시는 거스름돈 문제입니다.거스름돈을 구하는 과정은 아래와 같습니다. 예를 들어, 1, 5, 10, 25원의 동전이 있을 때, 32원을 거슬러주기 위해 다음과 같이 합니다.25원 동전 1개5원 동전 1개1원 동전 2개이를 코드로 그대로 옮기면 아래와 같습니다.python코드 복사def get_change(amount, coins): change = [] for coin in sorted(coins, reverse=True): while amount >= coin: amount -= coin change.append(coin) return change 위의 코드에서, 매 단계에서 가능한 가장 큰 동전을 선택합니다. 이 방법은 각 단계에서 가장 최적의 선택을 함으로써 최종적으로도 최적의 해결책을 찾을 수 있습니다.그리디 알고리즘으로 접근하는 게 효율적이지 않은 경우반대로, 그리디 알고리즘이 비효율적인 경우도 있습니다. 대표적인 예로는 배낭 문제가 있습니다.배낭 문제는 다음과 같습니다.배낭에 담을 수 있는 최대 무게가 정해져 있고, 여러 물건들이 각각의 무게와 가치가 주어집니다.물건들을 선택하여 배낭에 담을 때, 가치의 합이 최대가 되도록 해야 합니다.그리디 알고리즘을 사용하여 가치가 가장 높은 물건부터 선택하면 항상 최적의 해결책을 찾을 수 없습니다. 예를 들어, 다음과 같은 물건들이 있다고 합시다.물건 A: 무게 3, 가치 4물건 B: 무게 2, 가치 2물건 C: 무게 1, 가치 1배낭의 최대 무게가 3이라면, 그리디 알고리즘은 물건 A를 선택할 것입니다. 그러나, 최적의 해결책은 물건 B와 물건 C를 선택하여 가치를 3으로 만드는 것입니다. 이처럼, 그리디 알고리즘이 항상 최적의 해결책을 보장하지 않는 경우도 있습니다.이러한 이유로 배낭 문제는 동적 계획법을 사용하여 해결하는 것이 더 적합합니다.

[코딩 테스트 합격자 되기]동적계획법으로 접근해야 하는 문제를 판단하는 방법

동적 계획법으로 해결 가능한 문제를 판단하는 것은 때로는 경험이나 직감에 기반하기도 합니다. 그러나 일반적으로 다음 두 가지 주요 특성을 가진 문제들이 동적 계획법을 사용하여 해결될 가능성이 높습니다. 중복되는 부분 문제 (Overlapping Subproblems)동적 계획법은 중복되는 부분 문제들을 효과적으로 해결하기 위해 설계되었습니다.주어진 문제를 여러 작은 문제로 나누었을 때, 그 작은 문제들이 반복적으로 나타나는 경우 동적 계획법이 효과적입니다. 최적 부분 구조 (Optimal Substructure)주어진 문제의 최적 해결 방법이 해당 문제의 부분 문제들의 최적 해결 방법을 포함하는 경우입니다.즉, 큰 문제의 최적의 해결책을 찾기 위해 작은 문제들의 최적의 해결책을 사용할 수 있어야 합니다. 동적계획법으로 접근하는게 효율적인 경우동적계획법의 대표적인 예시는 피보나치수를 구하는 문제가 있습니다. 피보나치를 구하는 과정은 아래와 같습니다.F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) (n >= 2) 이를 코드로 그대로 옮기면 아래와 같습니다.def fibonacci_dp(n): if n 위의 코드에서 dp 배열은 피보나치 수열의 값을 저장합니다. 이 방법은 중복 계산을 피하면서 각 값들을 한 번씩만 계산하므로 효율적입니다. 코드를 분석해보면, fibonacci_recursive(3) 같은 값을 여러 번 계산하게 됩니다. 이러한 중복된 계산은 많은 시간을 낭비하게 됩니다.(중복부분문제 만족) 추가적으로, 피보나치 수열에서 F(n)의 최적의 해는 F(n-1)과 F(n-2)의 최적의 해를 바탕으로 구해집니다. 즉, 큰 문제의 최적의 해결책을 작은 문제들의 최적의 해결책을 통해 얻을 수 있습니다.(최적 부분 구조 만족) 중복부분문제와 최적 부분 구조 모두 만족하므로, 피보나치수는 동적계획법을 통해 효율적으로 문제를 풀 수 있습니다. 동적계획법으로 접근하는게 효율적이지 않은 경우이번에는 팩토리얼을 구하는 과정을 봅시다.n! = n × (n-1) × (n-2) × ... × 2 × 1 이를 코드로 구현하면 아래와 같습니다.def factorial_recursive(n): if n == 0 or n == 1: return 1 else: return n * factorial_recursive(n-1) 이 코드에서, factorial_recursive(n)을 호출하면 factorial_recursive(n-1)을 호출합니다. 그러나 이전에 계산한 값이 다시 사용되지 않습니다.(중복부분 문제가 아님) 즉, 어떤 값에 대한 팩토리얼을 계산하면 그 값에 대한 계산은 한 번만 이루어집니다. 따라서 팩토리얼은 동적계획법으로 접근하면 효율적이지 않습니다. 부분문제가 중복되지 않기 때문에, 메모이제이션으로 해도 효율이 없기 때문입니다.