[레벨 0] `3주차` 6. 알고리즘의 시간 복잡도와 공간 복잡도의 개념, 빅오 표기법에 대해 설명해주세요.

[longlivedrgn]

• 자주 사용되는 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)의 동작 원리와 시간 복잡도를 설명해주세요.
• 이진 탐색의 원리와 시간 복잡도에 대해 설명해주세요.
• 다이나믹 프로그래밍(Dynamic Programming)의 개념을 설명해주세요.

[ohdair]

블로그에 기재

[longlivedrgn]

시간 복잡도와 공간 복잡도

공간 복잡도

• 알고리즘이 실행되는 데 걸리는 시간의 총량
• 입력 크기에 대한 함수로 표현된다.
• O(n^2) → 입력 크기가 n인 경우 n^2의 작업 수행 시간이 걸린다.=

공간 복잡도

• 알고리즘이 실행되는 동안 사용된느 메모리 공간의 양
• 입력 크기에 대한 함수로 표현이된다.
• 메모리 사용량을 예측하고 비교하는 데 활용된다.

빅오 표기법

• 알고리즘의 시간 복잡도와 공간 복잡도를 표현하는 데 사용되는 수학적 표기법
• 함수의 상한을 나타낸다.
  • 알고리즘의 복잡도를 입력 크기에 대한 상한으로 나타낸다. (알고리즘의 성능을 최악의 경우로 나타낸다.)

[아래 알고리즘은 간단하게 정리 - 추후에 다시 정리할 예정]

자주 사용되는 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)의 동작 원리와 시간 복잡도를 설명해주세요.

• 퀵 정렬

  • 분할 정복/재귀 알고리즘을 이용한 정렬 알고리즘
    • 아래의 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
    • 최선의 경우 - O(nlogn)
    • 최악의 경우 - O(n^2)

• 병합 정렬

  • 분할 정복 알고리즘의 하나이다.
  • 추가적인 리스트가 필요하다.
  • 최악/최선의 시간 복잡도 - O(nlogn)

이진 탐색의 원리와 시간 복잡도에 대해 설명해주세요.

• 정렬이 된 배열안에서 중간 값을 비교하면서 검색값을 찾는다.
• 최선의 경우(바로 딱 찾았을 경우) - O(1)
• 최악의 경우(나누고 나누고 마지막 2개 중에서 찾았을 경우) - O(logn)

다이나믹 프로그래밍(Dynamic Programming)의 개념을 설명해주세요.

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것
  • 문제해결 패러다임
• Memoization

[qwerty3345]

알고리즘의 시간 복잡도와 공간 복잡도의 개념, 빅오 표기법에 대해 설명해주세요

• 시간 복잡도는 특정 알고리즘을 수행할 때 걸리는 총 시간을 나타내는 개념입니다.
• 반면 공간 복잡도는 특정 알고리즘을 수행할 때 걸리는 총 메모리 공간을 나타내는 개념입니다.
• 빅오 표기법은 시간/공간 복잡도를 표기할 때, 사용하는 수학적 표기를 방식으로,
• 함수의 극한적인 동작을 통해 표기합니다. O(n), O(n2), O(logn) 같은 방식으로 표기합니다.

자주 사용되는 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)의 동작 원리와 시간 복잡도를 설명해주세요.

• 퀵 정렬: 분할정복 기법과 재귀 알고리즘을 사용한 정렬 알고리즘으로 이름 그대로 많은 경우 빠른 편에 속하는 정렬 알고리즘입니다.
• 대부분의 언어에서 기본 알고리즘에 해당 퀵 정렬을 변형한 것을 사용하는 것으로도 알고 있습니다.
• 병합 정렬: 분할 정복 기법을 사용하는 "안정 정렬" 방식입니다.
• 개념적으론 알고있는데, 실제로 코드로 구성하라고 하면 못할 것 같네요;ㅎㅎ
• 더 학습하겠습니다.

이진 탐색의 원리와 시간 복잡도에 대해 설명해주세요.

• 정렬되어있는 데이터를 가정하고, 특정한 값을 찾는 알고리즘입니다.
• 탐색 범위를 절반으로 나눠서 범위를 좁혀가는 방식으로 동작합니다.
• 1/2 로 줄여가는 방식이기 떄문에 데이터의 길이가 2배가 되면 횟수는 1회 증가합니다. 그러므로 시간 복잡도는 O(logn) 입니다.

다이나믹 프로그래밍(Dynamic Programming)의 개념을 설명해주세요.

• DP, 동적 계획법이라고도 하는 다이나믹프로그래밍은 쉽게 말해 "답을 재활용" 해서 문제를 풀어가는 방식입니다.
• 어떤 문제를 풀기 위해 해당 문제를 더 작은 문제의 연장선으로 간주하고, 이전에 구한 답을 재활용하는 방식으로 해결하는 방식입니다.
• 가장 대표적인 예시는 피보나치 수열 구하기 방식이 있습니다.

[ueunli]

개관

DP(Dynamic Programming)는 큰 문제를 작은 부분 문제로 나누고, 각 부분 문제의 결과를 메모리 캐싱(Memoization)을 통해 저장 및 재사용하는 문제 해결 방식을 말한다. 이로써 중복 계산을 방지하고 복잡한 문제를 효율적으로 처리할 수 있다. 쪼갠 문제들에 대하여, 제일 빈번하게 반복하게 되는 동작은 데이터를 정렬하고 탐색하는 일이다. 정렬 알고리즘, 탐색 알고리즘은 그만큼 다양하기에 각 동작에 적합한 알고리즘을 선택하기 위해 복잡도를 고려한다. 메모리 용량이 부족하지 않다는 전제 하에, 가장 대표적인 기준은 시간 복잡도다. 최악의 경우 n개의 데이터에 대해 얼마나 많은 시간(또는 공간)이 소요되는가를 나타낸 빅 오 표기법이 자주 쓰인다. 　

정렬 알고리즘

대표 예시: 병합 정렬

• 동작 원리:
  1. 배열을 반으로 나누어 재귀적으로 분할한다. (재귀적으로 == 자기 자신을 호출하여 == 자기 자신을 나누고 나눈 자신을 나누고 나뉜 자신을 나누고... )
  2. 분할된 각각의 부분 배열을 정렬한다.
  3. 둘씩 병합(merge)하기를 반복한다. (분할 정복 기법)
• 시간 복잡도:
• O(nlogn)
• 시간 복잡도가 안정적이고 일정한 편 　

  탐색 알고리즘

  대표 예시: 이진 탐색

• 동작 원리
• 전제 조건(0단계):
• 배열이 오름차순으로 정렬된 상태여야 함
• 배열의 시작과 끝 인덱스가 초기화 되어 있어야 함 (start와 end가 어디인지, 즉 '검색 범위'가 정의·선언되어야 함)
• 반복 과정:
  1. 중앙 인덱스를 계산한다. (start와 end의 평균)
  2. 중앙 요소를 찾고, 타겟(찾는 대상)과 비교한다.
  3. 타겟이 그보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 선택한다.
  4. 타겟을 찾을 때까지 반복하여 수행한다.
• 시간 복잡도
• O(logn)
• 전체 검색 범위에서 탐색 범위를 절반씩 줄여가므로, 처음 규모로 시간 복잡도가 결정됨 (마지막 범위에서 발견할 경우, 즉 최악의 경우 logn임) 　

  DP, XP

  (별 관련은 없지만 그냥 Dynamic Programming 하니 eXtreme Programming 연상돼서 정리함)

• DP
• 알고리즘 설계 기법
• 적용 대상: 수열 관련 문제, 경로 탐색 문제 등
• XP
• 소프트웨어 개발 방법론 (애자일(Agile) 방법론의 한 종류)
• 주요 원칙: 짧은 개발 주기, 지속적인 고객 피드백, 테스트 주도 개발(TDD), 짝 프로그래밍, 빌드·배포 자동화 등

　 　

[SunnnySong]

1️⃣ 자주 사용되는 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)의 동작 원리와 시간 복잡도를 설명해주세요.

병합 정렬 / 합병 정렬 / Merge sort

• 분할 정복 알고리즘의 한 종류이다.
  • 분할(divide) : 배열을 같은 크기의 2개 부분 배열로 분할한다.
  • 정복(conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 작지 않다면, 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.
• 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계이다.
• 시간 복잡도: O(logN)

버블 정렬 / Bubble sort

• 서로 인접한 두 원소를 검사해 정렬하는 알고리즘이다.
• 자료의 교환(swap)이 자료의 이동(move)보다 더 복잡하기 때문에 버블 정렬은 단순하지만 거의 쓰이지 않는다.
• 시간복잡도: O(n^2)

퀵 정렬, Quick sort

• 분할 정복 알고리즘의 한 종류이다.
  • 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
  • 평균적으로 매우 빠른 수행 속도를 갖는다.
• 피벗을 기준으로 피벗보다 작은 요소들은 왼쪽으로 옮기고, 피벗보다 큰 요소들은 오른쪽으로 옮긴다.
  • 피벗: 리스트 안에 있는 한 요소이다.
• 피벗을 제외한 왼쪽, 오른쪽 리스트를 다시 정렬한다.
  • 분할된 부분 리스트에 대해 순환 호출을 이용해 정렬을 반복한다.
  • 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

2️⃣ 이진 탐색의 원리와 시간 복잡도에 대해 설명해주세요.

이진 탐색 / Binary search

1. 정렬된 배열의 중간값을 가져온다.
2. 중간값과 검색값을 비교한다.
   1. mid == key : 중간 값이 검색값과 같다면 종료한다.
   2. mid < key : 중간값보다 검색값이 크다면 중간값 기준 배열의 오른쪽 구간을 대상으로 탐색한다.
   3. mid > key : 중간값보다 검색값이 작다면 중간값 기준 배열의 왼쪽 구간을 대상으로 탐색한다.
3. 값을 찾거나 간격이 비어있을 때까지 반복한다.

시간 복잡도

• 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
  • 문제를 해결하는데 걸리는 시간과 입력의 함수 관계이다.
• 주로 빅오 표기법(Big-O)을 사용한다.
  • 오메가, 세타 표기법이 있지만 평가하기가 까다롭다.
  • 그래서 최악의 경우를 계산하는 빅오를 사용한다. 알고리즘이 최악일 때의 경우를 판단하면 평균과 가까운 성능으로 예측하기 쉽기 때문이다.

3️⃣ 다이나믹 프로그래밍(Dynamic Programming)의 개념을 설명해주세요.

다이나믹 프로그래밍 / 동적 계획법

• 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.
• 주로 상향식(bottom-up) 접근 방식을 사용한다.
  • 작은 하위 문제들부터 시작해 그 결과를 저장하고, 이를 이용해 점진적으로 큰 문제를 구해나간다.
• 메모이제이션(Memoization)을 사용한다.
  • 중복되는 계산 결과를 저장하는 메모리 기법이다. 이전에 계산한 값을 캐시하고, 필요한 경우 해당 값을 가져와 재사용한다.
  • 재귀적 호출에서 중복 계산을 방지하고 계산 속도를 향상시킨다.
• 시간 복잡도는 작지만 공간 복잡도가 높다.
• ❓알고리즘 기법과 알고리즘 설계 기법
  • 알고리즘 기법 : 문제를 해결하기 위해 사용되는 절차적 방법
    • 정렬 알고리즘, 검색 알고리즘 등
  • 알고리즘 설계 기법 : 문제 해결을 위해 사용되는 알고리즘을 설계하는 방법이나 접근 방식. 알고리즘을 개발하고 구현하는데 사용되는 전략/원칙을 포함한다.
    • 분할 정복, 동적 계획법, 탐욕적 알고리즘, 백트래킹

[soo941226]

자주 사용되는 정렬 알고리즘(예: 퀵 정렬, 병합 정렬)의 동작 원리와 시간 복잡도를 설명해주세요.

먼저 공통점을 이야기를 드리면 좋을 것 같은데요. 둘다 분할정복이라는 방법을 이용하게 됩니다. 분할정복은 그 이름처럼 하나의 큰 문제를 작은 여러개의 문제로 나누어서 풀어나가며 해를 구하게 됩니다. 위 전제를 바탕으로 두 알고리즘을 비교하면, 결국 문제를 어떻게 분할해나가고, 풀어나가는가? 입니다. 이야기하기 쉽도록 오름차순으로 설명드리면, 퀵 정렬은 임의의 피벗이라는 원소를 기준으로 작은 값은 왼쪽, 큰값은 오른쪽으로 밀면 왼쪽 리스트와 오른쪽 리스트가 생겨납니다. 새롭게 생긴 왼쪽, 오른쪽 리스트에 다시 임의의 피벗이라는 원소를 두며 앞선 행위를 반복하면 정렬이 됩니다. 이때 피벗을 임의의 원소로 선택하는 게 중요한데, 재수없게 가장 큰값이나 작은 값이 선택되면 리스트가 하나만 생기기 때문입니다. 그래서 최악의 경우 O(n^2) 일반적으로는 O(nlogn)이 나옵니다. 합병정렬은 정확한 알고리즘은 기억이 안나는데... 분할정복을 사용해서 리스트를 나누고 합병해나가면서 정렬을 하는 건데, 이게 메모리를 좀 많이 잡아먹습니다. 제가 퀵정렬만 특히 기억하는 이유가 이름부터가 특히나 좋은 알고리즘이어서 퀵이 붙었던 걸로 기억합니다

이진 탐색의 원리와 시간 복잡도에 대해 설명해주세요.

위에서 퀵솔트가 피벗을 기준으로 좌우를 나눠가며 '정렬'을 하는 거라고 말씀드렸는데요. 이진 탐색은 이미 정렬이 되어있는 리스트에서 중간값을 피벗으로 두고 탐색을 하는 거라고 이해하면 받아들이기 쉬우실 것 같습니다. 정렬을 할 필요가 없고, 모든 리스트를 탐색을 할 필요가 없으므로 n이 빠져 O(logn)이 나옵니다

다이나믹 프로그래밍(Dynamic Programming)의 개념을 설명해주세요.

다이나믹 프로그래밍을 이하 DP라고 표현하겠습니다. DP에 앞서 먼저 위에서 분할정복을 말씀드렸는데요. DP도 분할정복과 발상이 크게 다르지 않습니다. 결국 작은 문제가 풀기 쉽기 때문에 작은 문제부터 풀어보려는 건데요. 분할정복은 이 작은 문제의 해가 곧 해가 되는 측면이 있는데, DP는 반대로 이 해를 통해서 조금 더 큰 문제의 해를 구할 수 있게 됩니다. 가장 대표적으로 이야기되는 게 피보나치 수열인데요. An+2 = An+1 + An이라는 수열이 있을 때 A0 A1은 보통 주어지고, 이를 통해 A2의 해를 구하면, 그 뒤에 A3은 A2와 A1의 합으로 결정됩니다. 이런 식으로 작은 문제의 해가 큰 문제의 해를 풀게 되는데, 그냥 점화식을 찾고 푸는 거라고 이해해도 무방할 것 같습니다. 그리고 앞서 피보나치에서 이야기를 드렸던 것처럼 앞서 풀었던 해를 저장시킬 필요가 있습니다