이전포스팅
알고리즘 분석(Algorithm Analysis) | 개념 | 임의 접근 머신 | 원시 연산
알고리즘 기본 개념 알고리즘이란 정해진 시간 동안 어떠한 문제를 해결하기 위한 순차적인 단계입니다 "0개 이상의 인풋을 넣었을 때 1 이상의 값을 도출해 내는 방법이나 과정" 내비게이션 - ro
jelong.tistory.com
이전 포스팅 리뷰
알고리즘의 실제 실행 시간을 평가하는 것은 어려울 수 있습니다. 이는 입력 크기, CPU 주파수, 사용 가능한 RAM, 데이터 전송 속도 및 자원을 선점하는 프로그램 등의 여러 요인으로 인해 어려워집니다. 그러나 데이터의 크기가 종종 알고리즘 실행 시간을 결정하는 가장 중요한 요소입니다
알고리즘의 시간 복잡도를 정의하기 위해 성장률과 점근적 표기법과 같은 기술을 사용할 수 있습니다. 성장률은 입력 크기가 증가함에 따라 알고리즘 실행 시간이 얼마나 빠르게 증가하는지를 나타냅니다. Big O, Big Omega 및 Big Theta와 같은 점근적 표기법은 알고리즘 실행 시간의 상한, 하한 및 극한 값을 표현하는 표준화된 방법을 제공합니다
알고리즘의 시간 복잡도를 분석함으로써, 특정 데이터에 대한 어떤 알고리즘을 선택할지 결정하고 다양한 입력 크기에서의 성능을 추정할 수 있습니다
이전 포스팅은 아래의 더보기를 통해 확인 하실 수 있습니다
데이터 구조(Data structure)
알고리즘 계산은 작동할 데이터(정보)가 필요합니다
알고리즘 계산 속도는 이러한 데이터를 효율적으로 사용하는 데 따라 (부분적으로) 영향을 받습니다.
데이터 구조는 정보를 저장하고 액세스하기 위한 특정 방법입니다.
우리는 다양한 종류의 데이터 구조를 공부합니다. 특정 알고리즘에 대한 사용 방법과 저장된 데이터 유형에 따라 적합한 데이터 구조가 다를 수 있기 때문입니다
스택(Stack)
스택(Stack)은 후입선출(LIFO) 방식의 데이터 구조입니다
- 스택에는 언제든지 항목을 삽입할 수 있습니다(스택 오버플로우가 없다고 가정할 때).
- 우리는 마지막으로 삽입된 요소에만 직접 액세스할 수 있습니다.
(예를 들어, 웹 브라우저는 최근에 방문한 웹 페이지 주소를 스택에 저장합니다)
스택 메서드(Stack Method)
스택(Stack)은 추상 데이터 타입(Abstract Data Type, ADT)이며 다음과 같은 메서드를 지원합니다:
- push(Obj) : 객체 Obj를 스택의 맨 위에 삽입합니다
- pop() : 스택의 맨 위에서 객체를 제거하고 반환합니다. 스택이 비어있을 경우 오류가 발생합니다. push와 pop 메서드 외에도 일반적으로 다음과 같은 메서드가 있습니다:
- initialize() : 스택을 초기화합니다
- isEmpty() : 스택이 비어있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다
- isFull() : 스택이 가득 찼으면 true를 반환하고, 그렇지 않으면 false를 반환합니다
PUSH 함수는 스택에 객체를 추가하는 함수입니다. 스택이 가득 찼을 경우, "스택이 가득 찼습니다"와 같은 오류 메시지를 출력합니다. 스택이 비어 있는 경우, t(top) 변수에 1을 더한 값을 t에 할당하여 스택의 포인터 위치를 이동합니다. 그 다음, S[t]에 객체를 저장하면, 새로운 객체가 스택의 맨 위에 추가됩니다
POP 함수는 스택에 객체를 비우는 함수입니다. 스택이 비어있을 경우, "스택이 비어 있습니다"와 같은 오류 메시지를 출력합니다. 스택에 값이 있는 경우, S[t]에 null 값을 할당함으로 스택을 비우고, t - 1 값을 t에 할당함으로 스택 포인터 위치를 이동합니다
스택 적용(후위 표기법 RPN)
현대적인 절차형 프로그래밍 언어(C, C++, Java 등)의 실행 환경에서 중요합니다. 산술식을 후위 표기법으로 표현하면 (Jan Łukasiewicz라는 개발자의 이름을 따서 Reverse Polish notation (RPN)이라고 함) 스택을 사용하여 계산할 수 있습니다
후위 표기법(Postfix notation) 또는 역 폴란드 표기법(Reverse Polish notation, RPN)은 산술 표현식을 나타내는 방법입니다. 후위 표기법에서는 피연산자(숫자 또는 변수)가 연산자(+ 또는 -와 같은)보다 앞에 나옵니다. 예를 들어, 3 + 4 대신에 3 4 +와 같이 표현합니다
후위 표기법으로 표현된 식을 계산하기 위해서는 스택을 사용합니다. 식을 왼쪽에서부터 읽으면서 각 피연산자를 스택에 넣습니다. 연산자를 만나면 스택에서 가장 최근에 넣은 두 개의 피연산자를 pop하고, 해당 연산자를 적용한 결과를 다시 스택에 넣습니다.
예를 들어, 3 4 + 5 * 식을 계산하려면, 먼저 3과 4를 스택에 push합니다. + 연산자를 만나면, 스택에서 4와 3을 pop하여 더하고, 그 결과인 7을 다시 스택에 넣습니다. 그 다음, 5를 스택에 push합니다. * 연산자를 만나면, 스택에서 5와 7을 pop하여 곱하고, 그 결과인 35를 다시 스택에 넣습니다. 최종 결과는 35입니다.
