웹브라우저의 동작 원리 / 스택, 큐 구조 / 재귀함수

웹브라우저의 동작 원리 공부

1/ 자바스크립트 코드 처리 방식

2/ 동기 비동기

3/ 스택과 큐

4/ 재귀함수 (ft.피보나치수열)

 

 

자바스크립트의 코드 처리 방식에 대해서 우선은 간단하게 원리만 이해했다.

 

1/ JavaScript = single threaded language?! 

메모리 상에서 코드를 실행하고 처리하는 곳을 콜스택이라고 하는데,

이 콜스택은 한번에 하나씩만 처리할 수 있으면 쌓이는 일이 없이 그때그때 코드가 실행되는 곳이다.

=> 자바스크립트를 single threaded language 라고 한다

(하나의 프로세스에 하나의 스레드 / 멈추지 않는다) 

=> 원래 Javascript는 hoisting (변수,함수 선언) 이후 시간순대로 코드가 실행되는데, 예외적으로 비동기 처리 방식을 보일 때도 있다.

 

 

예외로 시간이 걸리는 함수들의 경우,

#1 콜스택에선 우선 급한 애들만 처리한다면서 이런 애들을 일종의 대기실같은데로 보내버린다고 한다. 

#2 그동안 다른 출력물을 먼저 뽑아내고, 대기실로 간 코드들은 큐에서 대기를 탄다.

#3 스택이 완전히 비었을 때 큐에서 기다리고 있던 코드들이 콜스택으로 이동하고 드디어 출력!

 

2/ 동기 vs. 비동기

 

동기

: A->B->C 순으로 간결하고 직관적인 프로세스지만 B에서 오류, 시간지연의 문제가 생기면 C의 출력도 미뤄짐

 

비동기

: 하나의 프로세스에 살짝 복잡하지만 융통성 있는 카페 같은 느낌..

카페에서 단체 손님이 10잔을 시켰는데 그 바로 다음 손님이 아메리카노 한잔만 시킨다면,

한 사람이 10잔을 만들고 있는 동안 다른 한 사람은 아메리카노 1잔을 만들어서 기다리지 않게끔 해주는 구조!

=> 대량의 I/O 처리 능력이 뛰어나다 => INPUT/OUTPUT이 많은 웹사이트에 JS가 많이 쓰이는 이유

 

 

3/ 스택과 큐

stack

- LIFO (Later In First Out) 

- 후입선출 구조 : 나중에 넣은 것을 먼저 꺼내는 구조

- ex) 뒤로가기 버튼 (사용자가 했던 행동들을 쌓아놨다가 뒤에서부터 하나씩 out)

 

아래 코드의 경우, 단순하게 생각하면, 3rd가 먼저 화면상에 출력되고, 2nd, 1st 순으로해서 thirdIn() = 3rd2nd1st가 나올 것 같지만, 틀렸다. 대기실에 쌓였다가 먼저 출력될 수 있는 애들이 나가는 걸로 상상하면 간단하다. 

 

thirdIn 에서 secondIn이라는 함수가 계산될 동안 3rd는 쌓여있다. 

secondIn도 firstIn 함수가 계산되기 전에 2nd도 쌓여 있다가 firstIn이 출력되자마자, 마지막으로 쌓인 2nd가 나가고, 그 다음에 3rd가 나가게 되어 1st2nd3rd가 출력! 

 

좀 더 복잡하게 연습

 

Queue 구조 

- FIFO (First In First Out)

- 선입선출 구조 : 먼저 넣은 것을 먼저 꺼내는 구조

- ex) 푸쉬 알림 기능, 쇼핑몰 주문 처리방식 

 

 

4. 재귀함수 

 

자기 자신을 호출하는 함수

종료 조건이 충족할 때까지 반복적으로 스스로를 불러내면서 주어진 작업을 수행하는 거!

 

대표적인 예시 : 피보나치 수열

1 1 2 3 5 8 13 21 34 55 89 ...

 

function fibo(n){
 if(n==1 || n==2){
	return 1
 }
 return fibo(n-1) + fibo(n-2)
}

console.log(fibo(10))

 

포인트:

공통적인 부분을 찾아서 프로그래밍적인 걸로 바꿔야하는게 포인트!!

 

공통적인 부분 : n번째 값 = (n-1)번째 값 + (n-2)번째 값 

 

작은 문제를 해결하고 큰 범위로 넓혀서 해결하는 걸 DP = Dynamic Programming 이라고 한다.

 

=> 다만, 위의 식 같은 경우 시간 복잡도가 올라간다. 

=> 메모이제이션 기법을 활용한다. 

(한번 계산한 값은 저장했다가 다시 가져오는 형태)

 

 

시간 복잡도란!? 
알고리즘은 빠르다 느리다 로 표현하지 않음
같은 알고리즘이여도 컴퓨터 하드웨어의 능력치에 따라 같은 작업이여도 컴퓨터마다 다 다른 속도를 보이기 때문!
=> 완료까지 걸리는 절차의 수로 결정한다! 

N개의 데이터 처리 = step N번을 거친다 => On 이라고 부른다

Big O 
1. 시간복잡도 O(n)
ex) 선형 검색의 경우 한개씩 일렬로 찾아야하므로, input size = n개 => 시간복잡도 O(n)
     각 아이템을 출력하는 for문의 경우도 이에 해당

2. 시간복잡도 O(1) 
input이 몇 개던 상관 없이 constant time (상수 시간)
=> O는 중요한 항목 이외는 무시한다는 의미를 가진 기호라고 한다.
=> 즉, 함수의 디테일엔 관심이 없다. 정말 의미있는, 이 함수의 작동 단위 / 계산의 기본 단위만을 따짐
함수 내에서 console.log 출력을 2번하건 3번하건 O(2), O(3)이 아니라
그냥 '출력'이라는 기본단위만을 따지기 때문에 O(1)로 따짐 

3. 시간복잡도 O(n^2)
ex) 중첩 for문

4. 시간복잡도 O(log n)
 ex) 이진검색

 

 

 

 

다시 본론으로 돌어와서

메모이제이션 기법을 간단히 알아보자..

처음 쓴 코드는 중복되는 계산식이 존재해서 n^2 로 점점 계산해야할 것들이 늘어나서.. 스택이 터지는데, 

아래 메모이제이션 코드는 계산이 반타작 날라가는 형태라 더 빠르다고 한다.

근데 알듯말듯하다가도 아예 모르겠음ㅠ 리액트 배울 때 다시 나온다고 하니 그때 다시 보자..

 

let number = [];
function fibo2(n){
	if (number[n]>0){
    return numbers[n]
	} else if (n == 1 || n == 2){
    	return numbers[n] = 1;
	} else {
    	return numbers[n] = fibo2(n-1) + fibo2(n-2)
	}
}

console.log(fibo2(10))

 

아, 참고로 

 

javascript에서 코드 처리 시간 계산은 

계산할 코드 앞에 console.time() / 마지막에 console.timeEnd() 넣으면 콘솔창에 시간이 찍힌다.