CS/Data structure3 Stack & Queue ( 스택 & 큐) Q1. Stack(스택)란? -LIFO: 후입선출 - 삽입(push), 삭제(pop), 탐색(top) 3가지의 함수 모두 O(1)의 시간 복잡도 스택의 활용 예시 - 웹 브라우저 방문기록: 가장 나중에 열린 페이지부터 다시 보여준다 -역순 문자열 만들기: 가장 나중에 입력된 문자부터 출력한다 등이 있다 이제 스택을 직접 구현해보자 코드는 자바스크립트로 구현하려고 한다 배열을 이용하려고 한다 class Stack { arr = []; push(value){ return this.arr.push(value); //push 후 length값 리턴 } pop(){ return this.arr.pop(); //pop 후 length값 리턴 } top(){ //return this.arr[this.arr.lengt.. 2024. 2. 29. Linked List(연결 리스트) Q1. 연결리스트(Linked List)란? - 메모리 내에 분산되어 있는 데이터들을 하나로 묶어 관리하기 위해 노드 내부에 다음 노드의 위치에 관한 정보가 포함되어 있는 자료 구조 이때, 각각의 노드는 데이터 노드와 다음 노드를 가르키는 포인터 필드로 구성된다 - 연결 리스트에서는 첫 번째 노드부터 시작하여 찾고자 하는 요소까지 순차적으로 접근해야 한다 =>최악의 경우 O(n)의 시간이 소요된다(찾고자 하는 요소가 마지막에 위치할 때) 이제 Linked List를 직접 구현해보자 코드는 자바스크립트로 구현하려고 한다 먼저 노드를 구현해보자. //Node class Node{ //다음 노드의 위치 next = null; //현재 노드의 값 constructor(value){ this.value = val.. 2024. 2. 28. 시간 복잡도 표기법: 자료구조, 알고리즘 성능 표시 위해서 공간 복잡도: 메모리를 얼마나 많이 차지하는가 -> 메모리 성능이 올라감에 따라 실제로는 잘 사용하지 않음 시간 복잡도: 시간이 얼마나 걸리는가 1) Big-O(빅오): 최악의 경우 / 많이 사용 2) Big Theta(빅 세타): 최악 = 최선 3) Big-Omega (빅 오메가): 최선의 경우 / 잘 쓰지 않음 이제 빅오 표기법을 예시를 통해서 알아보자 for(let i=0;i O(n log n) > O(n^2) > O(n^3) > O(2^n) > O(n!) * 항상 O(n log n) > O(n^2) 일까? n이 커지면 차이가 유의미하겠지만 n이 작으면 오히려 후자가 좋은 경우도 있다 *O(n) vs O(2n) n과 2은 n이 커질수록 차이가 무의미해지.. 2024. 2. 27. 이전 1 다음
