알고리즘 기본자료형, 데이터의 구조 , 시간복잡도

알고리즘 기본자료형, 데이터의 구조 , 시간복잡도

 

데이터 구조와 알고리즘은 서로 다른 개념이면서 상호 보완적이다.

데이터 구조와 알고리즘은 컴퓨터 과학의 핵심적인 두 가지 요소입니다. 데이터 구조는 데이터를 효율적으로 저장하고 조작하는 방법에 대한 연구입니다. 이에 반해, 알고리즘은 문제를 해결하기 위한 절차나 방법을 설명합니다.

데이터 구조는 정보를 저장하고 검색하는 데 사용되며, 알고리즘은 이러한 데이터에 대해 수행되는 연산을 정의합니다. 따라서 두 개념은 서로 다르지만, 실제 응용에서는 상호 보완적으로 작동합니다. 효과적인 소프트웨어 설계를 위해서는 적절한 데이터 구조 선택과 그에 따른 알고리즘의 활용이 중요합니다.

 

기본 자료형: 불, 문자, 정수, 부동소수점 수가 있다.

 

기본 자료형은 프로그래밍 언어에서 제공하는 가장 기본적인 유형의 데이터를 나타냅니다. 

- **불(boolean)**: 참(true) 또는 거짓(false) 중 하나의 값을 가집니다.
- **문자(char)**: 단일 문자를 나타내며 ASCII 코드나 유니코드 등을 사용하여 인코딩됩니다.
- **정수(int)**: 양수와 음수 모두 포함된 정수 값을 나타낼 수 있습니다.
- **부동소수점(float or double)**: 소수점 아래의 값까지 포함하여 실수 값을 표현할 수 있습니다.

각각의 자료형은 특정 종류의 값과 그에 해당하는 연산들을 지원하며 프로그램 내에서 변수나 객체 등으로 사용됩니다.

 

탐욕 알고리즘은 근사치를 구하고 동적 프로그래밍 알고리즘이 최적화한다

탐욕 알고리즘이란 각 단계에서 최선의 선택을 하는 전략을 취하여 문제 해결을 시도하는 방법인 반면, 동적 프로그래밍(DP)은 복잡한 문제를 작게 분할하여 하나씩 해결하며, 이러한 부분 문제들의 해를 재사용함으로써 전체 문제를 효율적으로 해결하는 방법입니다.

탐욕 알고리즘은 각 단계에서의 최선의 선택이 항상 전체적인 최선의 결과로 이어진다는 보장이 없기 때문에 근사치를 찾는 데 종종 사용됩니다. 반면, 동적 프로그래밍은 주어진 제약 조건 내에서 가능한 최선의 해답을 찾아내므로 최적화 문제에 적합합니다.

 

시간 복잡도를 분석하는 방법은 실제적인 방법과 수학적인 방법이 있다

시간 복잡도는 알고리즘 실행 시간을 측정하는 데 사용되는 메트릭입니다. 

실제 시간 분석은 알고리즘이 실제로 실행되는 데 걸리는 시간을 측정합니다. 이러한 분석은 구체적인 환경(하드웨어, 운영 체제 등)에 따라 결과가 크게 달라질 수 있습니다.

반면에, 수학적 분석은 입력 크기와 관련하여 알고리즘이 얼마나 많은 연산을 수행하는지를 고려합니다. 이러한 분석은 Big-O 표기법 등을 사용하여 알고리즘의 상대적 효율성을 비교하는 데 유용합니다.

 

 

시간복잡도의 대표적 문제는 방문 판매원 문제다

 

방문 판매원 문제(TSP: Traveling Salesman Problem)는 모든 도시를 한 번씩 방문하고 시작점으로 돌아오는 가장 짧은 경로를 찾으려 하는 NP-완전 문제입니다. 이런 종류의 문제들에서 모든 가능한 경우를 탐색해야 할 경우 시간 복잡도가 지수 함수형태로 증가하기 때문에 다루기 어렵습니다. 따라서 TSP와 같은 NP-완전 클래스에 속하는 많은 중요한 컴퓨터 과학 및 운영 연구 문제들이 실세계에서 발생할 때 그 해결책을 찾는 것은 매우 어렵습니다. 이러한 문제를 효과적으로 해결하기 위해 근사 알고리즘, 휴리스틱 메소드, 동적 프로그래밍 등 다양한 방법이 사용됩니다.