알고리즘과 자료구조 그리고 시간복잡도 사이의 관계

알고리즘 재미있냐?? ( 재미있어 질 예정입니다!!!! )

 

알고리즘 Algorithm

문제를 해결하기 위한 절차나 규칙의 집합이다.

입력을 받아 어떤 목표나 문제를 해결하기 위해 처리 과정을 명확히 정의한 방법이다.

• 명확성: 각 단계가 명확해야 한다.
• 유한성: 알고리즘은 일정한 단계 내에 종료되어야 한다.
• 입력과 출력: 반드시 정해진 입력이 있고 원하는 결과를 출력한다.
• 효율성: 문제를 해결하는 데 시간과 공간 자원을 최소화해야 한다.

 

알고리즘의 종류

기술계산	유클리드 호제법(최대공약수), 가우스 소거법(방정식), 사다리꼴법칙(정적분), 데이스크라 알고리즘(최적경로), 에라토스테네스의 체(소수)
정렬	단순 선택 정렬, 단순 삽입 정렬, 단순 교환 정렬(버블정렬) 병합정렬, 퀵 정렬, 셸정렬
검색	선형검색(리니어서치), 이진검색(바이너리서치)
문자열 매칭	단순 문자열 일치, KPM알고리즘, BM알고리즘

 

알고리즘은 구조적 프로그래밍을 따른다.
프로그램을 효율적으로 작성하고 설계상 오류를 최소화 하기위 한 방법론

• 순차구조 : 적힌 순서대로 실행하는 것
• 선택구조 : 조건에 따라 처리의 흐름을 바꾼다
• 반복구조 : 조건이 성립하는 동안, 일정한 처리를 반복한다

 

자료구조 Data Structure

• 데이터를 효율적으로 저장하고 관리하기 위해 사용하는 구조나 형식이다.
• 메모리와 디스크에 데이터를 저장하고 접근하기 쉽도록 만들어진 컨테이너 역할을 한다.
• 이를 통해서 알고리즘의 효율성을 높인다. 데이터를 어떻게 구성하고 저장하느냐에 따라 검색, 삽입, 삭제와 같은 연산의 성능이 크게 달라지므로, 다양한 상황에서 적합한 자료구조를 사용하는 것이 중요하다.

 

시간복잡도

알고리즘이 실행되는 데 걸리는 시간을 입력 크기에 따라 분석한 것이다. 일반적으로 빅오 표기법을 사용하여 가장 나쁜 최악의 경우의 실행시간을 나타낸다.

• O(1)은 가장 빠르고 효율적인 복잡도이고,
• O(N!), O(2^N) 같은 경우는 매우 비효율적인 경우다.

 

시간복잡도를 코딩 테스트에 활용하는 방법!!!!!

문제를 분석한 후에 빅오 표기법을 활용해 해당 알고리즘을 적용했을 때 시간 내 출력값이 나올 수 있는지 확인해 볼 수 있다. ( 아직은 낯선 방법이지만 쉬운 문제부터 적용해보려고 노력중이다 ) 

 

• 컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억 번이다. ( 성능에 따라 8500만회 ~ 8.5억번의 연산 수행 가능..... )
• 이를 기반으로 코딩테스트의 문제를 풀 때 초당 1000 ~ 3000만 정도로 고려해서 시간복잡도를 생각하면 된다. 

코딩테스트 진행시, 시간 복잡도별로 허용할 수 있는 최대 연산 횟수

'데이터가 1000만개 정도면 O(N)을 사용해야 한다' 는 감을 익혀야 한다 

 

 

정리 : 자료구조와 알고리즘, 시간복잡도의 관계

각 개념들은 자신만의 의미를 지니며, 서로 상호 보완적인 관계에 위치해 있다.

• 자료구조는 효율적으로 데이터를 관리하는 구조로, 어떤 자료구조를 사용하느냐에 따라 알고리즘의 시간 복잡도에 영향을 준다.
• 알고리즘은 주어진 문제를 해결하기 위한 단계별 절차로, 어떤 자료구조에서 어떤 알고리즘을 사용해 문제를 해결하는지에 따라 시간 복잡도에 영향을 미친다.
• 시간복잡도는 알고리즘이 실행되는 데 걸리는 시간을 뜻한다. 일반적으로 최악의 시간을 표현하며 이를 빅오 표기법으로 나타낸다.

⇒ 효율적인 자료구조를 사용하여 데이터를 관리하고, 가장 최적의 조건을 생각하여 알고리즘을 선택해 문제를 해결할 수 있어야 한다.

 

 

---

reference 

• 코딩 테스트 합격자되기 - 자바스크립트 편
• 그림으로 배우는 알고리즘 Basic