기본 알고리즘 (알고리즘 개념 / 알고리즘 기초 / Algorithm)

알고리즘 Algorithm

알고리즘이란 쉽게 말하면 문제해결 순서이고 자료구조를 구현한 방법론이다.

 

어떤 문제에 대해, 목표를 달성하기 위해, 해결해야할 작업을 단계적으로 지시해 놓은 것을 말한다.

 

 

알고리즘의 4단계

1. 문제 정의 : 해결하고자 하는 바를 input / output 나눠 정의한다.
2. 알고리즘 설명 : 해결하기 위해 할 일들을 단계적으로 정의한다.
3. 정확성 증명 : 알고리즘이 맞는지 수학적으로 증명
4. 성능 분석 : 시간, 공간 복잡도 

 

알고리즘은 반드시 끝이 있다. 시간이 얼마나 걸리든 작업 단계의 횟수는 정해져있다.

여기서 시간, 공간 복잡도가 나온다.

 

 

알고리즘은 방법론이고 성능을 측정하는데는 측정 환경에 따라 달라질 수 밖에 없다.

그래서 시간 복잡도는 얼마나 걸리는지가 아니라 얼마나 수행하는지에 따라 비교하는 방식으로 측정되어야 한다.

 

 

시간 복잡도 Time Complexity

시간 복잡도는 T(n) 과 같이 표기한다.

이는 알고리즘이  n 크기의 입력량을 처리하는데 필요한 연산의 횟수를 말한다.

 

공간 복잡도 Space Complecity

공간복잡도는 O(n) 과 같이 표기한다.

이는 알고리이 n 크기의 입력량을 처리하는데 필요한 작업 기억 영역(메모리)의 양을 말한다. 

 

 

결론적으로

좋은 알고리즘은 효율성을 따져 적절한 자료구조(공간)과 빠른 시간 내에 문제를 해결하는 것이라 할 수 있다.

 

우리는 이 시간, 공간 복잡도를 계산해 알고리즘의 성능을 표현할 수 있다.

 

 

점근적 표기법 

점근적 표기법은 n에 따라 함수가 증가하는 비율인 점근적 증가율을 표기하는 방법을 말한다. 

 

점근적 표기법에는 크게 3가지가 있다.

• 빅오 표기법
• 세타 표기법
• 오메가 표기법

 

Big-O 표기법 

빅오 표기법은 알고리즘의 시간 복잡도가 점근적 증가율을 넘지 않는 함수들의 집합을 말한다. 더 쉽게 말하자면 식에서 큰 대표항만 두고 나머지는 버려서 표기하는 방법이다.

 

빅오 표기법은 알고리즘의 실제 러닝타임을 표시하는 거라기보다 데이터나 사용자의 증가율에 따른 알고리즘의 성능을 예측하는 게 목표이다.
- 유투브 '엔지니어대한민국'  / [자료구조 알고리즘] 빅오(Big-O)표기법 완전정복

 

 

T 아카데미 컴퓨터 알고리즘 초급 2강

 

f(n)함수는 n에 값에 따라 변화하는데 아무리 변화해도 접근적 상한인 cg(n)보다 커지지 않는다는 것이다.

즉 알고리즘이 아무리 느려도 기존의 함수보다는 빠르다는 말이다.

 

 

이 표기법에는 

• O(1)
• O(n)
• O(n²)
• O(log n)

등이 있다.

 

 

[바킹독의 실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

 

알고리즘 문제 해결 전략

1. 반복
2. 재귀 반복 
3. 완전 탐색
4. 역추적
5. 발견법
6. 분할 정복

등이 있다.

 

 

 

(자주 쓰는) 알고리즘 종류

• 정렬 알고리즘
  • 선택 정렬
  • 삽입 정렬
  • 병합 정렬
  • 퀵 정렬
• 탐색 알고리즘
  • 순차 탐색
• 그래프 알고리즘
  • 그래프 탐색
    • 깊이 우선 탐색
    • 너비 우선 탐색
  • 경로 탐색

 

이 외에도 너무 많은 알고리즘이 사용되고 있다.

 

---

참고

 

+자료구조와 알고리즘 기본 개념

자료구조와 알고리즘 그리고 코딩테스트? - YouTube

 

+ 알고리즘 입문에 좋은 강의

T아카데미 | 스마트 ICT 전문가 양성 (skplanet.com)

컴퓨터 알고리즘 초급 | T아카데미 온라인강의

 

 

+ 예전에 공부했던 책인데 지금 다시 참고하기 좋네..

https://book.naver.com/bookdb/book_detail.nhn?bid=13496659

한 권으로 그리는 컴퓨터과학 로드맵

> 책 후기는 여기..

2020.11.23 - [Hello_World/IT도서] - 한 권으로 그리는 컴퓨터 과학 로드맵 (컴퓨터과학/컴퓨터 이론/컴퓨터구조/비전공자/입문/책추천)

 

 

+ 빅-O 표기법 

https://youtu.be/6Iq5iMCVsXA