[알고리즘] 알고리즘 특성 및 기법

🐣 친숙해지고 싶은 알고리즘

---

나와 친해지고 싶으나 자꾸만 멀어지는 친구 알고리즘.. 그에 대해 개념과 기법을 정리해보려고 한다.

 

 

🐣 알고리즘(Algorithm)

---

1. 개념

알고리즘은 어떠한 문제를 해결하기 위한 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 기법

 

2. 특성

알고리즘의 표현은 자연어, 순서도, 의사코드, 프로그래밍 언어를 이용하는 방법이 존재. 프로그래밍 언어가 아니더라도 알고리즘의 표현은 가능.

입력	외부로부터 입력되는 자료 0 개 이상
출력	출력되는 결과 1개 이상
명확성	각 명령어의 의미가 명확
유한성	정해진 단계를 지나면 종료
유효성	모든 명령은 실행이 간으한 연산들이어야 함

 

 

🐣 알고리즘 기법

---

1. 분할과 정복(Divide and Conquer)

문제를 나눌 수 없을 때까지 나누고, 각 문제를 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘

 

2. 동적 계획법(Dynamic Programming)

어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장성으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘

 

3. 탐욕법(Greedy)

결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달하는 방식의 알고리즘

 

4. 백트래킹(Backtracking)

어떤 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손노드를 검색하는 알고리즘

 

 

🐣 시간 복잡도에 따른 알고리즘 분류

---

참고 - 시간복잡도에 대한 개념 정리

빅오 표기법 Big O Notation - 시간복잡도, 공간복잡도

1. O(1)

• 상수형 복잡도
• 자료 크기 무관하게 항상 같은 속도로 작동
• 알고리즘 수행 시간이 데이터 수와 관계없이 일정
• 대표 알고리즘 : 해싱 함수(Hash Function)

 

2. O(log2n)

• 로그형 복잡도
• 문제를 해결하기 위한 단계의 수가 log2n번만큼의 수
• 대표 알고리즘 : 이진 탐색(Binary Search)

 

3. O(n)

• 선형 복잡도
• 입력 자료를 차례로 하나씩 모두 처리
• 수행 시간이 자료 크기와 직접적 관계로 변함(정비례)
• 대표 알고리즘 : 순차 탐색(Sequential Search)

 

4. O(nlog2n)

• 선형 로그형 복잡도
• 문제를 해결하기 위한 단꼐의 수가 nlog2n번만큼의 수행 시간을 가짐
• 대표 알고리즘 : 퀵 정렬, 합병 정렬(병합 정렬), 힙 정렬

 

5. O(n²)

• 제곱형 주요 처리 루프 구조가 2중인 경우
• n크기 작을 때에는n²이 nlog2n보다 빠를 수 있음
• 대표 알고리즘 : 거품 정렬, 삽입 정렬, 선택 정렬

 

 

🐣 알고리즘 설명

---

각 게시글 작성 후 링크 첨부 예정!_! 

 

---