[Algorithm] Introduction

Introduction of Algorithm

• 자료 구조 : 다양한 방식의 데이터 저장 방식을 의미하고, 그 안에 저장된 데이터에 접근하는 데 필요한 비용을 결정

• 알고리즘: 주어진 문제가 있을 때, 데이터에 대한 정확한 정의와 데이터 변환 순서에 대한 일련의 명령

• 알고리즘의 좋고 나쁨은 알고리즘 동작의 효율성에 의해 결정된다. 또는 알고리즘 수행에 필요한 명령의 개수도 판단의 근거가 될 수 있다.

알고리즘 문제 분류(계산 복잡도 기준)

• P 문제: 다항 시간 알고리즘을 이용하여 솔루션을 구할 수 있는 문제

• NP 문제: 특정 솔루션을 다항 시간으로 검증할 수는 있지만 알려진 다항 시간 솔루션은 없는 경우

• EXPTIME 문제(지수 시간 문제): 입력 크기에 대한 지수 함수 형태의 시간 복잡도 솔루션을 갖는다

• PSPACE(다항식 공간) 문제 : 다항식 크기의 공간이 필요한 문제

P = NP 문제

• P 문제 집합이 NP 문제 집합과 완전히 같은지를 알아내는 것을 P = NP 문제라고 한다

  • 수십 년의 노력에도 아직 해결되지 않은 문제

Ref) 코딩 테스트를 위한 자료구조와 알고리즘 with C++