오늘도 삽질

노트정리/자료구조

자료구조 스택/큐 개념과 구현 (with javaScript)

스택(Stack)과 큐(Queue) 스택과 큐는 기초적인 자료구조로 꼭 CS를 공부하지 않았어도 개발 공부를 하다 보면 한 번씩 들어보는 자료구조입니다. 실제 개발을 하면서 구현을 하기도 하며, 실 생활에서도 볼 수 있는 자료구조입니다. 많이 활용되고 유명하단 말이겠죠? 그리고 둘은 선형 데이터 구조로 선형구조는 데이터들이 일렬로 저장되어 있는 형태를 말합니다. 비슷한 점도 가지고 있지만 차이점도 있습니다. 스택과 큐의 개념과 몇 가지 대표적인 특성에 대해 알아보고 구현해보면서 비교해 보겠습니다. 스택(Stack) 특징 마지막에 들어온 게 먼저 나가는 Last In First Out 후입선출 구조를 가지고 있습니다. 데이터를 삽입하는 것을 Push, 삭제하는 것을 Pop이라 합니다. 스택에서 top이라는..

노트정리/자료구조

[자료구조] 시간복잡도, 공간복잡도

프로그램의 성능 평가에 프로그램을 실행하는 데 필요한 시간과 공간의 추정치를 분석하는 방법과 컴퓨터가 실제로 프로그램을실행하는데 걸리는 시간을 측정하는 방법이 있다. 여러 프로그램을 비교하는 데 성능 측정 방법보다는 성능 분석을 사용한다.공간적인 효율성과 시간적인 효율성이라는 복잡도를 평가한다. 공간 복잡도공간 복잡도 (space complexity)는 프로그램을 실행시켜 완료하는 데까지 소요되는 총 저장 공간을 의미한다. 알고리즘에 사용되는 메모리 총량이라고 생각하면 쉽다. 공간 복잡도는 최악의 경우나 평균의 경우를 고려하여 표현한다.공간 복잡도 = 고정 공간 + 가변 공간 | 특정 프로그램의 성능을 분석하기 위해서 공간 복잡도는 기억공간이 최악이나평균적으로 얼마나 필요한지를 분석하는 방법이다. 시간 ..

노트정리/자료구조

[자료구조] 수식 표기법, 순회 방법

수식 표기법 전위 표기식 , 중위 표기식, 후위 표기식이 있다. 전위 표기식은 연산자를 피연산자의 앞에 표기하는 방법 + AB 이다.중위는 피연산자를 가운데 표기한다. A + B후위는 AB + 이다. 전위 표기식 : - + AB / CD중위 표기식 : A + B - C/D후위 표기식 : AB + CD / - 중위 표기식이 가장 일반적이다. 예를 들어 A/B + C -D*E 의 중위 표기식을 전위 표기식으로 변환하는 과정을 알아보면처음으로 괄호를 묶어준다. 그리곤 연산 순서에 따라 해당 연산자를 괄호 앞으로 이동하여 표기한다.그리고 괄호를 삭제한다. -+/ ABC*DE 로 변환이 끝난다. 순회 방법 1. 중위 순회중위 순회는 Left - root - right 순으로 방문한다. 후위 순회는 Left - r..

노트정리/자료구조

[자료구조] 기본 점화식 , 재귀호출

자신이 포함된 수식으로 표현하는 것을 점화관계라 한다.예를 들어서 T(n)을 입력크기가 n인 이진 탐색의 시간 복잡도라 할 떄 T(n)은 T(n) = T(n/2) + O(1) 점화식으로 표현 가능하다. T(n) = T(n - 1) + Θ (1), T(1) = Θ (1) -> O(n)T(n) = T(n - 1) + Θ (n), T(1) = Θ (1) -> O(n^2)T(n) = T(n/2) + Θ (1), T(1) = Θ (1) -> O(logn)T(n) = T(n/2) + Θ (1), T(1) = Θ (1) -> O(n)T(n) =2 T(n/2) + Θ (1), T(1) = Θ (1) -> O(n)T(n) = 2T(n/2) + Θ (1), T(1) = Θ (1) -> O(nlogn) 기본 점화식 재귀호출..