JS 런타임 환경이 뭘까?

JS 실행 환경이란?

JS를 실행시키기 위한 전체적인 환경을 의미한다. JS는 그 자체로 독립적으로 동작하는 언어가 아니라, 실행될 환경에서 다양한 기능을 추가로 제공받는다. 이렇게 JS가 실행되는 곳을 호스트 환경이라고 한다. 그리고 그런 자바스크립트 호스트 환경에는 브라우저, node.js, Deno 등이 있다. 특히 가장 유명한 node js는 크롬의 v8엔진을 가져와서 만든 자바스크립트 런타임 환경이다. 모든 JS 실행 환경에는 JS를 해석하고 실행할 수 있는 JS 엔진을 내장하고 있다. 하지만 브라우저와 Node.js의 차이가 있다.

브라우저와 Node.js의 차이점

브라우저는 웹페이지를 화면에 렌더링 하는 것이 주된 목적이고, Node.js는 브라우저 외부에서 자바스크립트 실행 환경을 제공하는 것이 주된 목적이다. 따라서 모두 자바스크립트 코어인 ECMAScript(JS 핵심 문법)을 가지고 있지만, 이외에 추가로 제공하는 기능은 호환되지 않는다.

Node.js: ECMAScript + Node.js 고유의 API

브라우저: ECMAScript + DOM API (DOM, Canvas, fetch, SVG, Web Storage, Web Worker ..)

요약❗️자바스크립트는 어디서 실행되느냐에 따라서 사용할수 있는 기능이 다르다.

왜 JS는 브라우저라는 제한된 환경에서 실행되었는가?

JS가 생긴 목적은 기존의 정적 콘텐츠로 구성되어 있던 웹페이지에 동적인 기능을 추가하기 위해 개발되었다. 당시의 JS 사용 목적은 브라우저에서 JS가 실행되도록 하는 것이었으므로, 다음과 같은 이유로 브라우저 상에서만 JS가 실행되게 하였다.

1. JS는 웹 개발을 위한 언어이다.
   JS는 웹페이지를 동적으로 조작하기 위해 만들어진, 브라우저를 위한 언어이다.
2. 서버와 클라이언트가 명확히 역할 분담이 되어야 한다.
   서버는 데이터 처리를 맡고, 클라이언트는 데이터를 화면에 표시한다. JS는 그러한 클라이언트의 역할을 돕기 위해 개발되었다.
3. 보안
   JS가 파일 시스템에 접근할 수 있다면, 브라우저에서 다운받은 파일에 악성코드가 심겨져서 사용자의 정보를 탈취할 수 있을 것이다.
4. 플랫폼 독립성
   JS는 브라우저에서 동작하기 때문에 운영체제나 하드웨어에 상관없이 웹페이지에서 동일한 동작을 보장할 수 있다.

백준 3273 - 두 수의 합

해결 방법

1️⃣ 파이썬의 특수 구문을 활용하면 문제를 간단히 해결할 수 있다. (for - in) x - ai 가 수열에 포함되는지 확인하면 된다.

2️⃣ 내가 작성하는 문법이 파이썬이 아님을 생각했을 때 다른 방식으로 풀 수 있다. 먼저 주어진 수열에서 max 값을 뽑은 다음, 그 크기만큼의 새로운 리스트를 만든다. 그 뒤, 리스트의 인덱스를 활용해서 입력받은 수열의 존재여부를 기록한다. 그리고  x - ai가 그 리스트에서 1 (존재) 인지 아닌지 체크한다.

어려웠던 점

✅ 배열의 인덱스에 따른 예외 처리를 생각하지 못했음.

새로 알게 된 점

✅ set과 list의 차이

접근 방법

1️⃣ 처음에는 set 대신 list를 사용했는데, 시간초과가 났고, list를 set으로 바꾸니까 해결되었다. 그리고 // 연산자 대신 /을 한 뒤 형변환을 했는데, //로 바꾸고 시간이 약간 줄었다.

N = int(input())
arr = set(map(int, input().split()))
X = int(input())

count = 0

for i in arr:
  if X-i in arr:
    count += 1

print(count//2)

2️⃣ 예외 처리를 고려하지 않아 런타임에러(IndexError)가 발생했었다.

N = int(input())
arr = list(map(int, input().split()))
X = int(input())

arr1 = [0] * (max(arr) + 1)
for i in arr:
  arr1[i] = 1

count = 0

for i in arr:
  remain = X - i
  if remain < 0 or remain >= len(arr1): continue
  if remain != i and arr1[remain] == 1:
    arr1[i] = 0
    count += 1

print(count)

2️⃣ 보다 1️⃣ 번이 훨씬 효율적이었다. 

백준 1475 - 방 번호

해결 방법

0~9까지의 인덱스를 가지는 배열을 선언하고, 방 번호에 필요한 숫자들의 개수를 +1 하면 된다. 그런 다음, 가장 큰 값만큼 숫자 세트를 구매하면 된다.

어려웠던 점

✅ 9와 6에 대한 예외가 없었다면, 그냥 배열의 max 값을 뽑으면 되었을텐데, 9와 6이 서로 대체 가능하다는 점을 고려하는 게 까다로웠다. 

새로 알게 된 점

✅ 올림은 +1 한 다음 나머지를 버리면 되는구나를 알았다.

접근 방법

1️⃣ 방 번호를 가장 작은 자리수부터 탐색하며 0~9까지 인덱스를 가지는 배열의 값을 +1 하려고 했다. 그 이후 max 값에 6, 9 인덱스가 포함되어 있을 경우 예외 처리를 하려고 했다. 하지만, "max 값 확인 -> 6, 9 포함 -> 6, 9 예외처리 -> 다시 max 값 확인" 이 과정이 너무 번거로웠다.

2️⃣ max 값을 뽑기 전에 예외 처리를 하기로 했다. 그러면 max 값을 가지는 모든 인덱스를 확인해서 그 인덱스에6, 9가 포함되는지 확인하지 않아도 되니 1번 보다 효율적이었다. 먼저 6, 9가 공통으로 가지는 부분은 1set로 사야하는 부분이다. 그리고 그 둘의 차이는 절반만 사도 된다. 단, 그 둘의 차이가 홀수라면 한 세트를 추가적으로 구매해야 한다.

# 모든 수를 순회하면서 0~9까지 숫자가 몇 개인지 체크. 나중에 6,9를 예외처리해서 몇 개의 플라스틱 세트를 사야 하는지 확인하기
import math

N = int(input())

answer = [0]*10

while(N > 0):
  answer[int(N%10)] += 1
  N = int(N/10)

if answer[6] > answer[9]:
  answer[6] = answer[9] + math.ceil((float(answer[6] - answer[9])) / 2)
elif answer[6] < answer[9]:
  answer[9] = answer[6] + math.ceil((float(answer[9] - answer[6])) / 2)

print(int(max(answer)))

3️⃣ math를 사용하지 않고 올림 처리를 했다. 또한, 6, 9 인덱스를 뺀 나머지에서 max를 구하고, 6, 9인덱스 값과 비교해 max를 뽑는 식으로 로직을 수정하여 코드 길이를 단축시켰다.

N = int(input())

answer = [0]*10

while(N > 0):
  answer[int(N%10)] += 1
  N = int(N/10)

max_value = max([answer[i] for i in range(len(answer)) if (i != 6 and i != 9)])

print(int(max(max_value, (answer[6] + answer[9] + 1) / 2)))

import math

N = int(input())

answer = [0]*10

while(N > 0):
  answer[int(N%10)] += 1
  N = int(N/10)

if answer[6] > answer[9]:
  answer[6] = answer[9] + math.ceil((float(answer[6] - answer[9])) / 2)
elif answer[6] < answer[9]:
  answer[9] = answer[6] + math.ceil((float(answer[9] - answer[6])) / 2)

print(int(max(answer)))

백준 2577 - 숫자의 개수

접근 방법

1️⃣ 세 수의 곱셈 결과를 배열로 변환하고, 0~9 배열의 인덱스를 활용해 각 숫자에 해당하는 배열의 값을 +1 함.

A = int(input())
B = int(input())
C = int(input())

result = A*B*C

multiple = [int(digit) for digit in str(result)]

answer = [0]*10

for i in multiple:
  if i == 0:
    answer[0] += 1
  elif i == 1:
    answer[1] += 1  
  elif i == 2:
    answer[2] += 1  
  elif i == 3:
    answer[3] += 1  
  elif i == 4:
    answer[4] += 1  
  elif i == 5:
    answer[5] += 1  
  elif i == 6:
    answer[6] += 1  
  elif i == 7:
    answer[7] += 1  
  elif i == 8:
    answer[8] += 1  
  elif i == 9:
    answer[9] += 1

for i in answer:
  print(i)

2️⃣ if elif문이 너무 길어서 코드 길이를 단축하고자 함

A = int(input())
B = int(input())
C = int(input())

result = A*B*C

multiple = [int(digit) for digit in str(result)]

answer = [0]*10

for i in multiple:
  answer[i] += 1
  
for i in answer:
  print(i)

3️⃣ while문을 사용해서도 풀 수 있을 것 같았음. 그러면 세 수의 곱을 배열로 저장하지 않아도 됨. 백준 결과 세 번째 방식이 가장 효과가 좋았음.

A = int(input())
B = int(input())
C = int(input())

result = A*B*C

answer = [0]*10

while(result>0) :
  answer[int(result%10)] += 1
  result = result/10
  print(result)

for i in answer:
  print(i)

❗️바킹독 강의 정리

배열이란?

배열은 메모리 상에 원소를 연속하게 배치한 자료구조

배열의 성질

1. O(1)에 k번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리의 양이 거의 없음
3. cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

원소의 삽입/삭제는 O(N) 시간이 걸림.

배열과 리스트의 차이는?

배열과 리스트의 차이를 이해하기 위해서는, 메모리 사용법이 다르다는 것을 알아야 한다.

배열은 연속된 메모리 공간에 원소를 넣는 것이고, 리스트는 연속되지 않은 메모리 공간을 사용한다.

이 차이에서 배열과 리스트의 내부 동작 방식이 완전히 달라진다.

파이썬에서 배열은?

❗️파이썬에서 배열은 리스트와 다르다는 것을 인지하자.

배열은 같은 자료형의 데이터들이 하나의 변수로 정의된 것이다. 그런데 파이썬에서는 서로 다른 자료형들이 하나의 변수로 정의할 수 있도록 만들어놓았다. 그것이 바로 '리스트'이다.

우리가 흔히 쓰는 list = [] 이런 형식의 파이썬 코드는 '리스트'이다.

배열은, numpy같은 외부 라이브러리를 사용해야 한다.

파이썬에서 배열의 삽입/삭제는?

앞서 파이썬에서 배열은 numpy같은 라이브러리를 사용한다고 했다. 따라서 파이썬에서 원소의 삽입 삭제는 insert 함수와 delete 함수를 통해 새로운 배열을 생성할 수 있다.

동작 방식은, 복사의 방식을 사용한다. 즉, 새로운 크기의 배열을 만든 후 원래 배열 요소를 복사한다.

파이썬 리스트로 배열 insert 구현하기

배열의 동작 방식을 이해하기 위해 파이썬으로 insert를 구현해보자. 나는 새로운 리스트를 하나 만들고, 거기에 원본 배열을 복사했다. 

def insert(idx, num, arr, len) :
  copy_arr = []

  insert_idx = 0

  for i in range(0, len + 1):
    if i != idx:
      copy_arr.append(arr[insert_idx])
      insert_idx += 1
    elif i == idx:
      copy_arr.append(num)

  return copy_arr

문제

백준 10808 - 알파벳

새롭게 알게 된 점

✅ 배열을 출력하기 위해 for문만 생각했는데 map과 join 한수를 사용해 배열을 출력할 수 있다는 것을 알게 되었다.

접근 방법

두 가지 접근 방식을 생각하고, 어떤 것이 더 효율적인 연산일지 고려함.

1️⃣ 가정1. 알파벳을 기준으로 a~z까지 단어에 해당 알파벳이 몇 개 포함되어 있는지 갯수를 센다.

      예상1. 알파벳 갯수 26*단어 수 최대 100 = 26^100 연산이 필요함.

2️⃣ 가정2. 단어를 기준으로 해당 단어에 어떤 알파벳이 포함되어 있는지 찾고, 해당 알파벳의 적합한 인덱스 번호와 단어에 포함된 갯수를                    계산해서 배열을 만든다.

     로직: 단어의 처음부터 끝까지 순회하며 ord 함수를 통해 문자를 숫자로 변환해서 해당 인덱스 값을 +1 한다.

     예상2. 100*1*1 연산 필요. (ord 함수는 사전 정의된 매핑 테이블을 참조하는 정도이므로 상수 시간이 소요됨.)

inp = input()
alpabet = [0]*26

for i in range(0, len(inp)):
  inp_ascii_num = ord(inp[i])
  alpabet[inp_ascii_num - 97] += 1

print(' '.join(map(str, alpabet)))

[목차]

1. Tree
2. Binary Tree
3. Binary Search Tree
4. B-Tree
5. RB-Tree

[면접 질문 list]

1. 트리 자료구조에 대해서 설명
2. 트리와 그래프의 차이?
3. 트리의 순회방식 종류
4. 이진트리란?
5. BST란?
6. BST worst case 해결방법은?
7. BST 성능 개선 방법
8. RB Tree란?
9. RB Tree 작동 원리는?
10. RB Tree 삽입/삭제 알고리즘 구현은?
11. RB Tree 사용 시 주의해야 할 점
12. RB Tree 사용 예시
13. RB Tree 장점
14. AVL 트리란?
15. 검색 자동완성을 어떻게 구현할 수 있는가?

Tree

❓루트가 없는 트리도 있는가?

yes. 루트가 없는 free tree가 존재

❓루트가 있고 없고의 차이는 뭐고, 왜 루트가 있는 트리를 많이 사용하는 것일까?

루트가 있는 트리는 부모-자식 관계가 명확하다.

레벨이나 깊이의 개념이 있다. (계층 구조 존재) ⇒ 파일 시스템 등 많은 데이터들이 계층 구조를 가지고 있기에, 이런 데이터를 표현하기 적합하다.

모든 노드가 루트로부터 유일한 경로를 가진다. ⇒ 탐색이 효율적이다. 또한 부모에서 자식으로 단방향 참조만 필요하므로 메모리 사용이 효율적이다.

❓트리란 무엇인가?

#계층구조 #노드 #간선 #루트 #부모-자식 관계 #리프 #사이클 없음 #연결성

트리란 계층 구조를 가진 비선형 자료구조이다. 트리는 노드를 가지며, 노드는 객체로 표현된다. 각 노드는 간선으로 연결되어 있으며, 0개 이상의 자식 노드를 가질 수 있다.

트리의 중요한 특성은 사이클이 없다는 점이며, 모든 노드는 서로 연결되어 있어야 한다.

이러한 특성들로 인해 트리는 계층적 데이터를 표현하고 처리하는 데 매우 효과적인 자료구조이다.

❓트리와 그래프의 차이점?

1. 사이클: 트리는 사이클이 없지만, 그래프는 사이클을 가질 수 있다.
2. 연결성: 트리는 항상 모든 노드가 연결되어 있지만, 그래프는 연결되지 않을 수 있다.
3. 엣지 수: n개의 노드를 가진 트리의 엣지 수는 n-1 개로 항상 정해져 있다.
4. 루트: 그래프에는 루트 개념이 없다
5. 부모 자식 관계: 트리는 관계가 명확하고, 그래프는 이런 개념이 없음

모든 트리는 그래프이지만, 모든 그래프가 트리인 것은 아니다.

Binary Tree

이진트리는 각 노드가 최대 두개의 자식 노드를 갖는 트리 구조이며, 보통 왼쪽 자식과 오른쪽 자식으로 구분된다. 이때 자식 노드는 없을 수도 있고, 하나만 있을 수도 있고, 두 개 있을 수도 있다. 같은 루트에 같은 자식 노드를 가지고 있더라도, 그 노드의 위치가 다르면 서로 다른 트리로 구분된다.

주요 특징으로는 서브트리가 존재하며, 모든 노드의 차수가 최대 2이다. 또한 이진트리는 선형자료구조인 1차원 배열로 표현할 수 있다는 특징을 가진다.

Binary Search Tree

• 이진검색트리란?

이진 트리 형태를 가지며, 각 노드를 객체로 하는 자료구조다. key, 부속 데이터, left, right, p 필드를 가진다.

• 이진 검색트리 특징

모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다. 또한 자녀 노드는 최대 두 개까지 가질 수 있다.

• 값을 정렬된 순서로 출력하기 위해 이진 검색 트리를 순회하는 방법
  1. 중위 트리 순회 (inorder tree walk)
  2. 전위 트리 순회 (preorder tree walk)
  3. 후위 트리 순회(postorder tree walk)
• 이진 검색 트리에서 하나의 값을 검색하는 방법
• 최대 원소 또는 최소 원소를 찾는 방법
• 한 원소의 직전원소 또는 직후 원소를 찾는 방법
• 삽입/삭제를 수행하는 방법

B-Tree

• 개념

이진 트리를 확장한 것으로, 하나의 노드는 자식 노드를 2개 이상 가질 수 있다. 또한 이러한 자료구조는 데이터 베이스를 관리하는 데 특히 유용하다.

• 특징

자녀 노드의 최대 개수를 늘리기 위해서 부모 노드에 key를 하나 이상 저장한다.

부모 노드의 key들을 오름차순으로 정렬한다.

정렬된 순서에 따라 자녀 노드들의 Key 값의 범위가 결정된다.

추가는 항상 leaf 노드에 한다.

노드가 넘치면 가운데 Key를 기준으로 좌우 key들은 분할하고 가운데 Key는 승진한다.

• 파라미터

M: 각 노드의 최대 자녀 노드 수

M-1: 각 노드의 최대 key 수

⌈M/2⌉: 각 노드의 최소 자녀 노드 수

⌈M/2⌉ - 1 : 각 노드의 최소 key 수

RB-Tree

• 개념

이진 검색 트리의 최선의 시간 복잡도는 O(logn)이고, 최악의 시간 복잡도는 O(n)인데, 최악의 경우에도 빠른 실행 속도(O(logn))를 보장할 수 있도록 이진 검색 트리를 변형한 것이 RB Tree 이다.

RB Tree는 트기가 ‘균형을 이루도록’ 고안된 검색 트리 구조이다.

• 특징

레드 블랙 트리는 다음과 같은 특성을 만족하는 이진 검색 트리이다.

1. 모든 노드는 적색이거나 흑색이다.
2. 루트는 흑색이다.
3. 모든 리프는 흑색이다.
4. 노드가 적색이면 그 노드의 자식은 모두 흑색이다.
5. 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 흑색 노드를 포함한다.

문제

백준 1629 - 곱셈 

새롭게 알게 된 점

✅ 모듈러 연산의 성질

접근 방법

1️⃣ 거듭제곱을 통해 문제를 해결하면, 연산이 너무 오래 걸릴 것이라고 예상했다. 왜냐하면 10의 12 승만 되어도 테라바이트, 즉 조단위의 연산이 되기 때문이다. 따라서 연산 횟수를 줄여야 한다고 생각했다.

# 가설1. 나머지를 먼저 구하고 거듭제곱을 한다.
# 논거1. 곱셈은 교환법칙과 결합법칙이 성립함으로 계산 순서를 바꿔도 될 것이다.

A, B, C = map(float, input().split())

remain = A%C

answer = (remain*A)^(B-1)

print(answer)

# 검증1: 오답. "나머지 연산 자체"는 교환 법칙과 결합 법칙이 성립하지 않음.

2️⃣ 위와 같은 풀이는 나머지를 먼저 구한 후 거듭제곱을 수행한다는 점에서는 올바른 접근 방법이었으나, 모듈러 연산의 성질에 대해 알지 못해 잘못된 풀이를 적었다.

3️⃣ 따라서 다음과 같은 과정을 도출했다.

결과 코드

def power(A, B, C) :
  # B=0
  if B == 0:
    return 1

  # B=1
  if B == 1:
    return A%C

  k = power(A, B//2, C)

  # B가 짝수
  if B%2 == 0:
    return (k*k)%C
  # B가 홀수
  if B%2 == 1:
    return (k*k*A)%C

A, B, C = map(int, input().split())
print(power(A,B,C))