알고리즘에 대해 알아보기!!

💡 알고리즘(Algorithm)의 개념

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

 

📍 알고리즘 특성

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

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

 

📍 알고리즘 기법

기법	설명
분할과 정복 (Divide and Conquer)	문제를 나눌 수 없을 때까지 나누고, 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘
동적계획법 (Dynamic Programming)	어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘
탐욕법 (Greedy)	결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달하는 방식의 알고리즘
백트래킹 (Backtracking)	어떤 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모 노드로 되돌아간 후 다른 자손노드를 검색하는 알고리즘

 

 

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

복잡도	설명	대표 알고리즘
O(1)	∙ 상수형 복잡도 ∙ 자료 크기 무관하게 항상 같은 속도로 작동 ∙ 알고리즘 수행 시간이 입력 데이터 수와 관계없이 일정	해시 함수(Hah Function)
O(log2n)	∙ 로그형 복잡도 ∙ 문제를 해결하기 위한 단계의 수가 log2n번만큼의 수행 시간을 가짐	이진 탐색(Binary Search)
O(n)	∙ 선형 복잡도 ∙ 입력 자료를 차례로 하나씩 모두 처리 ∙ 수행 시간이 자료 크기와 직접적 관계로 변함(정비례)	순차 탐색(Sequential Search)
O(nlog2n)	∙ 선형 로그형 복잡도 ∙ 문제를 해결하기 위한 단계의 수가 nlog2n번만큼의 수행 시간을 가짐	퀵 정렬, 합병 정렬(병합 정렬), 힙 정렬
O(n^2)	∙ 제곱형 복잡도 ∙ 주요 처리 루프 구조가 2중인 경우의 복잡도 ∙ n의 크기가 작을 때에는 n^2이 nlog2n보다 빠를 수 있음	거품 정렬, 삽입 정렬, 선택 정렬

시간 복잡도 표로 보기!!