[알고리즘] 개요, 시간복잡도 효율성 etc

알고리즘 개념을 공부하려고 합니다. 알고리즘 무척 중요합니다.

중요한데 실력은 욕심만큼 잘 늘진 않네요. 😂 웃픕니다. 그래도 꾸준히 하면 언젠가 늘게 되겠죠?

인덱스는 다음과 같습니다.

 

1. 개요

2. 효율성

3. 문제의 크기

4. 시간 복잡도

5. 메모리

---

 

 

 

 

 

 

✅ 개요

알고리즘이란?

☘️ 알고리즘 (Algorithm)
: 수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것

• 입력을 통해 알고리즘으로 문제를 해결하고, 정답을 출력합니다. 어떤 문제를 해결하는 방법을 모두 알고리즘 이라고 할 수 있습니다.
• 많은 개발은 어떠한 문제를 해결해야 하는 것이 목적인 경우가 많습니다.
• 알고리즘 공부 법
  • 처음 공부할 때는 2-3일 고민
  • 어느정도 익숙해진 이후에는 2-3시간 고민
  • 많이 익숙해진 이후에는 20-30분 고민

• 해당 문제를 푸는 알고리즘이 무엇인가? 를 알아내는 것이 중요합니다.
• 각각의 알고리즘 특징을 알고, 왜 해당 알고리즘으로 다른 문제를 풀 수 있었는지 위주로 기억하여 문제에 적용합시다.

 

 

 

---

 

 

 

✅ 효율성

알고리즘을 해결하는 데 있어, 프로그램이 얼마나 효율성이 있는가를 알아보려면?

1. 수행시간
2. 사용한 메모리
3. 코드의 길이

• 제일 중요한 것은 수행시간입니다.

예시)
만약 메모리가 부족하다면, 램을 사면되지만
어떤 프로그램의 실행시간이 30일이 걸린다면 30일 동안 실행시켜야한다.

 

 

 

 

 

---

 

 

 

✅ 문제의 크기

문제를 해결하는 데 있어 항상 문제의 크기는 존재한다.

• 문제의 크기 N에 따라 걸리는 시간이 다릅니다.
• 예를 들면 N의 크기는 다음과 같습니다.
  • 쇼핑몰 장바구니 물건의 개수
  • 게임 동시 접속자의 수 등등

• 문제를 해결할 때는 문제의 크기를 먼저 보고 방법을 생각해야 합니다.

 

 

 

 

---

 

 

 

✅ 시간 복잡도

프로그램을 수행하는데 걸리는 대략적인 시간은?

☘️ 시간 복잡도 (Time Complexity)
: 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한 것

• 시간 복잡도를 이용하면 작성한 코드가 시간이 대략 얼마나 걸릴지 예상할 수 있습니다.
• 보통 표기법으로 Big-O 표기법을 사용합니다. (Big-O Notation)
• 시간복잡도는 즉, 입력의 크기 N에 대해서 시간이 얼마나 걸릴지 나타내는 방법을 이릅니다.
• 최악의 경우에 시간이 얼마나 걸릴지 알 수 있습니다.
• 시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때, 1억이 1초 정도 됩니다.

예시)
총 N명의 사람이 식당에 방문했다.
식당에는 메뉴가 M개 있고, 메뉴판이 1개 있다.
사람 1명이 메뉴판을 읽는데 걸리는 시간은 O(M)이다.
주문한 모든 메뉴는 동시에 나왔고, 각 사람 i가 식사를 하는데 걸리는 시간은 A[i]이다.
각 사람이 계산을 하는데 걸리는 시간은 O(P)이다.
각 사람이 메뉴판에 있는 모든 메뉴를 읽는 시간 복잡도 = O(NM)
모든 사람이 식사를 마치는 데 걸리는 시간 = O(max(A[i]))
식사를 모두 마친 다음 한 줄로 서서 각자 계산을 하는 시간 복잡도 = O(NP)

 

 

 

---

 

 

 

✅ 메모리

알고리즘 메모리의 제한은?

• 메모리 제한은 보통 넉넉하기 때문에, 걱정할 필요 없습니다.
• 보통 가장 많은 공간을 사용하는 것은 배열입니다.
• 배열이 사용한 공간
  • 배열의 크기 x 자료형의 크기 Byte
  • ex) int a[10000][10000] = 10000 x 10000 x 4 = 4억 Byte = 400MB  

 

 

 

 

 

 

 

 

 

 

 

---