ROKROKSS

신입 개발자 면접을 위한 지식 총정리

 
  • 2019년 04월 06일

면접 관련 준비 사항과 문제들을 끌어모아 정리합니다. 코딩 테스트 준비는 백준으로 갑니다.


DS, ALGO, PL, Network, OS

DS and ALGO

Data Structures

Data Structure

데이터구조는 정돈된 데이터의 집합으로 특정 방식으로 데이터를 넣고, 꺼낼 수 있게 합니다.


ADT (Abstract Data Type)

“Data” + “Operations on the data” => “A Data Type”

Data Type은 해당 프로그래밍 언어가 정의해놓은 Primitive Data Type = Concrete Data Type과 Abstract Data Type으로 나뉜다.


Array

인덱스를 이용하여 데이터를 삽입하거나 참조합니다.

create, retrieve, store operation이 있습니다.

인덱스를 안다면 1 step에 데이터를 찾을 수 있지만, 데이터 사이에 삽입을 하려면 먼저 데이터들을 옮겨야 합니다.


Linked-List

index 대신 다음 node의 주소를 들고 있게 합니다. 데이터는 선형 탐색으로 찾아야 하지만 삽입과 제거는 O(1)에 가능합니다.

C로 구현한다면 데이터 삽입과 삭제는 Malloc과 free를 반복하며 하게 됩니다.

Singly-Linked, Doubly-Linked


Stack

LIFO(Last-In/First-Out) Data Structure

array나 linked-list로 구현합니다.

array로 만드려면 간단히 array 하나와 top-index만 가지고 있으면 됩니다.


Queue

FIFO(First-In/First-Out) Data Structure

array를 통한 구현이 stack보다 복잡합니다.

queue의 item들을 한 array에 담고 enqueue, dequeue에 전체 array를 통째로 옮겨가게 만들면 쉽지만 O(n)이 됩니다. 아니면, front와 rear(꼬리) index를 따로 들고 있게 합니다. 이렇게 하면 enqueue/dequeue가 반복될수록 array의 앞이 비고 뒤로 밀리는데, Circular Array 개념을 이용하여 해결할 수 있습니다.


Priority Queue

array를 priority마다 준비하던가, 한 array에 enqueue 할 때 올바른 위치로 들어가도록 합니다. array나 linked-list를 이용하면 삽입이 O(n)인데, heap을 이용하면 삽입과 삭제가 모두 O(log(n))이 됩니다.


Time Complexity

f(n) = O(g(n))

|f(n)| <= C|g(n)| 이 항상 성립하게 하는 양의 상수 C가 있다면 이런 big-oh notation이 성립합니다.

“g(n) is an upper bound of f(n)”


f(n) = Ω(g(n))

|f(n)| >= C|g(n)| 이 항상 성립하게 하는 양의 상수 C가 있다면 이런 big-omega notation이 성립합니다.

“g(n) is an lower bound of f(n)”


f(n) = Θ(g(n))

f(n) = O(g(n))과 f(n) = Ω(g(n))이 모두 성립하면 이런 big-theta notation이 성립합니다.

“g(n) is both an upper bound and a lower bound of f(n)”

시간 복잡도 분석은 Worst case, Best case, Average case를 따로 다룰 수 있습니다, 예시로 Quick sort가 있죠.


Tree

Linked-List와 비슷한 구조로 구현됩니다. root node가 존재하며 각 node는 해당 node의 children의 주소들을 가지고 있습니다.

Binary Tree

node는 left child와 right child를 가질 수 있습니다. 어디서든 쭉 올라가면 root node가 나옵니다.


Full Binary Tree

특정 깊이까지 전부 꽉 차있는 트리입니다.

Full Binary Tree에서 level L (root의 level은 0)의 노드 갯수는 \(2^L\) 입니다.


Complete Binary Tree

최소한 마지막 레벨을 제외하면 Full Binary Tree 구조를 가지며 마지막 레벨의 node는 왼쪽에서부터 채워진 트리입니다.

Complete Binary Tree는 array representation이 있습니다. 좌->우, 상->하로 쭉 채우면 됩니다.


Pre-order Traversal

현재 노드 작업
Left Child
Right Child


In-order Traversal

Left Child
현재 노드 작업
Right Child


Post-order Traversal

Left Child
Right Child
현재 노드 작업


Binary Search Tree

왼쪽 subtree의 모든 node의 key는 현재 node의 key보다 작거나 같으며 오른쪽은 큽니다. skewed tree의 가능성이 있으므로 삽입/삭제/탐색 모두 O(n)이 됩니다.

삭제 매커니즘이 특별한데, 제거해야할 node의 child가 2개로 차있을 경우, 오른쪽 subtree의 최소 key를 가진 node를 제거해야하는 node 자리에 복사하고 원래 자리의 node를 제거합니다.


Heap

Heap은 기본적으로 complete binary tree 구조를 가집니다.

MaxHeap: parent는 child에 비하여 크거나 같은 key를 가집니다.

MinHeap: parent는 child에 비하여 작거나 같은 key를 가집니다.

Priority Queue를 만드는데 쓰이므로 삭제는 root node를 대상으로 이루어지며, root node를 맨 오른쪽 leaf node와 바꾼 뒤 삭제, leaf node는 아래로 traverse하며 제자리를 찾게 합니다.

삽입 시에는 마지막 node 자리에 넣고 위로 traverse하며 제자리를 찾게 합니다.


B-Tree

skewed tree 문제점을 해결하기 위한 해결방안 중 하나입니다.

node는 둘보다 많은 child node를 가질 수 있으며, 한 node가 여러 element를 가질 수 있습니다.

B-Tree는 M(Minimum)이라는 양수를 가집니다.

  1. root는 element를 최소한 1개까지 가질 수 있지만 다른 node들은 최소한 m개의 element를 가져야 합니다.
  2. node 내의 element 갯수의 최댓값은 2m입니다.
  3. 모든 node의 element는 작은 값부터 정렬된 상태로 array에 담겨있습니다.
  4. node가 가지는 subtree는 (node 내의 element 갯수 + 1)개입니다.
  5. non-leaf node에서 index i에 위치한 element는 subtree i의 모든 element보다 크고 subtree i+1의 모든 element 값보다 작습니다.
  6. 모든 leaf node는 같은 깊이에 있습니다.

탐색: node 내의 element를 선형탐색하여 target을 찾고, 못 찾을 땐 처음으로 만나는 target보다 큰 값의 index가 i면 subtree[i]에 대하여 반복한다.

삽입: 탐색과 같은 방식으로 진행하다 leaf에서 target보다 처음으로 커지는 element 앞으로 삽입한다. element 갯수가 maximum+1이 되면, 가운데 element를 parent로 보내버립니다. root까지 가버리면 새로운 root를 만듭니다.

삭제: 1) child가 없는데 못찾으면 False, child가 없는데 찾으면 단순 삭제, child가 있는데 찾았다면 직전 subtree의 가장 큰 element와 swap 후 아래에서 삭제합니다. child가 있는데 root에서 못찾았다면 subtree로 들어가 반복합니다. 이러다 node의 element 갯수가 minimum-1이 된다면 직전 subtree, 직후 subtree 혹은 형제에게서 빌려오거나 합쳐버립니다.

삽입/삭제/탐색 모두 log(n)


Graphs

Graph에는 종류가 많지만 제가 들은 수업에서는 self-loop과 동일한 간선의 반복이 없는 종류만 취급했습니다.

무한하지 않고 공집합이 아닌 node의 집합 V와 무한하지 않은 간선의 집합 E가 모여 Graph(V, E)를 형성합니다.


Free Tree

root가 없고 connected이며 acyclic한 graph입니다.

  • cycle: a simple path in which the first and the last vertices are the same.


Undirected Graph

간선에 방향이 주어져 있지 않습니다.


Directed Graph

간선에 방향이 있습니다.


Complete Graphs

Undirect에서는 간선의 갯수가 n(n-1)/2 입니다.

Directed에서는 n(n-1)입니다.


Subgraphs

V와 E가 상위 그래프에 모두 포함되면 Subgraph라 합니다.

그 외 adjacent, incdent on, adjacent to, adjacent from, in-degree, out-degree


Adjacency List

node 갯수 길이의 array의 각 node가 각자 리스트를 이루고 해당 node에서 adjacent한 node가 push_back됩니다.

for edge in edges:
    a, b = edge
    # a->b    
    adj[a].push_back(b)
    # Undirected면
    adj[b].push_back(a)

out-degree는 찾기 쉽지만 in-degree는 어렵습니다.


Adjacency Matrix

고대로 matrix 만드는 겁니다.

for edge in edges:
    a, b = edge
    # a->b
    adj[a][b] = 1
    # Undirected면
    adj[b][a] = 1


Depth First Search (DFS)

아까 나왔던 preorder tree traversal와 같습니다.

dfs(v): # 아주 대략적으로...
    visited[v] = True
    for w in v->links:
        if not visited[w]:
            dfs(w)

Adjacency List를 이용하면 간선의 갯수만큼 참조가 일어나고, 그 전에는 visit을 위해 node 갯수만큼 참조하므로 \(O(n+e)\)입니다.

Adjacency Matrix를 이용하면 한 node에 인접한 간선을 모두 찾는데 \(O(n)\)이 걸리고 node 갯수만큼 반복하므로 \(O(n^2)\)이 됩니다.


Breadth First Search (BFS)

Level order tree search와 같습니다.

bfs(v): # 아주 대략적으로...
    q = Queue()
    q.enqueue(v)
    while not q.is_empty():
        v = q.dequeue()
        for w in v->links:
            if not visited[w]:
                bfs(w)

시간복잡도는 DFS와 동일하게 Adjacency List에서 \(O(n+e)\), Adjacency Matrix에서 \(O(n^2)\)입니다.


Single Source Shortest Path

하나의 출발점에서 각 정점까지 도달하는데 비용을 계산하여 최단경로를 구하는 것입니다. 기본적으로 Directed Graph 구조를 가지고 설명하며, Undirected일 경우 같은 weight의 directed edge 두 개로 바꾸고 시작합니다.


Dijkstra Algorithm

Priority Queue를 이용하여 하나의 정점으로부터 인접한 간선들을 확장해 나가는 방식입니다. 음수 가중치를 갖는 간선이 없어야 합니다.

d[v] 배열을 모두 ∞으로 초기화하고, 시작점의 d[v] 값을 0으로하고 Priority Queue에 넣습니다.

Queue가 빌 때까지 minimum을 뽑고, 해당 정점에 adjacent한 정점의 d[v]값을 계산하여 업데이트합니다.

dijkstra(adjacency_list, v):
    n = len(adjacency_list)
    d = [INF for _ in range(n)]
    visited = [False for _ in range(n)]
    d[v] = 0
    q = PriorityQueue()
    q.enqueue((d[v], v))
    while not q.is_empty():
        value, cur = q.dequeue()
        if value > d[cur]: continue
        visited[cur] = True
        for dest, weight in adjacency_list:
            new_v = d[curr] + weight
            if (not visited[dest]) and new_v < d[dest]:
                d[dest] = new_v
                q.enqueue((d[dest], dest))

실제로 priority queue를 heap으로 구현하고 path 구하려면 predecessor 배열 만들긴 해야하는데 아무튼 이런 식으로하면 됩니다.

heap에 삽입이 \(O(logE)\), 그리고 삽입이 정점 갯수에 한해서 이루어지므로 \(O(VlogE)\), 값 갱신은 간선 갯수에 한해서 이루어지므로 \(O(ElogE)\), 합쳐서 \(O((E+V)logE)\), \(V <= E^2\)이므로 \(O((E+V)logV)\)입니다. 피보나치 힙을 사용하면 더 줄일 수 있다고 하네요.

정당성 증명

방문된 정점까지의 거리는 최소 거리임을 증명하면 되는데, 초기에 정점 하나만 있을 때 만족하므로 귀납법 + 귀류법으로 풉니다.

K+1 단계에서 정점 u를 방문하였는데 그 거리가 실제 최소 거리가 아니라고 하면, 다른 정점 u’가 방문되지 않은 채 존재하여 u까지의 실제 최소 거리를 잇는 정점으로 존재한다는 것인데, 그렇게 되면 (중략 w, w’가 등장하는 부분) d[u’]가 d[u]보다 작게 되는데 그러면 알고리즘 진행과정에서 u’가 u보다 먼저 방문되었어야 하므로 contradiction이 생기므로 증명 완료됩니다.


Floyd-Warshall’s Algorithm

얘는 Single Source Shortest Path 뿐만 아니라 All Pairs Shortest Paths를 구해줍니다.

floyd_warshall():
    for i in range(E):
        for j in range(E):
            for k in range(E):
                if adj[i][k] > adj[j][i] + adj[i][k]:
                    adj[j][k] = adj[j][i] + adj[i][k]

코드만 보셔도 아실 겁니다. \(O(E^3)\) 입니다. 중요한 점은 가운데 지나가는 정점이 맨 바깥 for문에 위치해야 한다는 것입니다.


Minimum Cost Spanning Tree

connected graph G에서 모든 node를 방문하는 cycle이 없는 subgraph를 spnning tree라고 합니다.

weighted undirected graph에서 spanning tree의 모든 간선의 weight 총합이 경우의 수 중 최소라면 해당 tree를 Minimum Cost Spanning Tree라고 부릅니다. (spanning tree with minimum cost)


Kruskal’s Algorithm

  1. edge를 지우고 정점을 독립적인 집합인 forest로 만듭니다.
  2. edge를 ascending order로 정렬합니다.
  3. cycle을 만들지 않는 가장 작은 edge를 골라 graph에 추가합니다.
E(G)를 ascending order로 정렬한다.
T = (V, 공집합) # vertices + no edges
VS =[[v] for v in V]
While num(VS) > 1 and (E(G) is not empty):
    (v, w) = deleteMin(E(G))
    if Find(u) != Find(v):
        replace set(u), set(v) by Union(set(u), set(v))
        add (v, w) to T

간선을 정렬하는데에 \(O(ElogE)\), 그리고 Union과Find가 E번 반복되는데, Union-by-height과 path-compression을 이용하면 Union은 \(O(1)\) Find는 \(O(log{\star}V)\)가 됩니다. 그렇게 아무튼 \(O(ElogE) + O(Elog{\star}V) = O(ElogE)\)가 됩니다.

크루스칼 알고리즘 정당성 증명

  1. 크루스칼로 만들어진 그래프가 Spanning Tree 임은 Acyclic하고 모든 노드를 포함한다는 점으로 간단하게 증명됩니다.
  2. Minimum Spanning Tree

귀류법을 통해 크루스칼로 만들어진 트리 T가 MST가 아니라고 합시다. 먼저 알고리즘 시작단계의 공집합에서는 MST를 만족하는데, 어느 순간 크루스칼이 택하는 간선이 아닌 다른 간선 (u, v)가 추가됨으로 MST를 만들게 된다는 의미인데 우리는 간선을 최소 weight 순으로 정렬하고 포함시켰으며 만들어지는 트리가 Spanning Tree 임은 1로 증명되었으므로 모순이 됩니다.


Prim’s Algorithm

prim():
    Q = V - {s}
    For v in V:
        D[v] = INF
        v.predecessor = None
    D[s] = 0
    while not Q.is_empty():
       u = Q.extract_min()
       for v in adj[u]:
           if v in Q and w(u,v) < D[v]:
               D[u] = w(u, v)
               v.predecessor = u

크루스칼의 정점 버전입니다. heap으로 구현하면 \(O((E+V)logV)\), array를 이용하면 \(O(V^2)\)입니다.

증명

귀류법+귀납법을 사용합니다. K+1번째에 (u, v)를 추가하여 T를 만들면, (u, v)는 실제 MST T’에 포함되지 않아야 합니다. 그러므로 (u, v)를 T’에 추가하면 cyclic한 graph가 됩니다. (u, v)와 T’가 (u, v) 대신 가진 간선을 바꿨을 때 T는 전보다 weight이 더 커지게 되므로 모순입니다. (알고리즘 상)


Sort Algorithms

Selection Sort

selection_sort():
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if a[j] < a[min_idx]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

너무 간단합니다. \(O(N^2)\) 입니다.


Insertion Sort

insertion_sort():
    for i in range(1, n):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

array 앞의 초기에 1칸짜리 구역을 지정하고 한 칸씩 오른쪽으로 늘리면서 해당 item을 왼쪽 구간의 올바른 위치에 넣는것입니다. 마찬가지로 \(O(N^2)\) 입니다.


Bubble Sort

bubble_sort():
    for i in range(n):
        for j in range(n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

뒤에서 i번째 칸을 위해 맨 앞부터 올바른 값을 swap을 반복하며 가져오길 반복합니다. \(O(N^2)\) 이고 위 두 정렬보다 성능이 더 나쁩니다.


Merge Sort

merge_sort(a):
    n = len(a)
    if n <= 1:
        return a
    mid = n // 2
    g1 = merge_sort(a[:mid])
    g2 = merge_sort(a[mid:])
    i1 = 0
    i2 = 0
    ia = 0
    while i1 < len(g1) and i2 < len(g2):
        if g1[i1] < g2[i2]:
            a[ia] = g1[i1]
            i1 += 1
        else:
            a[ia] = g2[i2]
            i2 += 1
        ia += 1
    while i1 < len(g1):
        a[ia] = g1[i1]
        i1 += 1
        ia += 1
    while i2 < len(g2):
        a[ia] = g2[i2]
        i2 += 1
        ia += 1
    return a

분할정복으로 분해된 sub-array들을 한 쌍씩 쭉 합쳐주는겁니다. \(O(NlogN)\) 이지만 같은 시간복잡도의 다른 정렬들과 다르게 추가적인 memory를 필요로 합니다.


Quick Sort

quick_sort(a, start_idx, end_idx):
    if start_idx >= end_idx:
        return;
    pivot_idx = random.randint(start_idx, end_idx)
    pivot_val = a[pivot_idx]
    a[pivot_idx], a[end_idx] = a[end_idx], a[pivot_idx]
    store_idx = start_idx
    for i in range(start_idx, end_idx):
        if a[i] < pivot_val:
            a[i], a[store_idx] = a[store_idx], a[i]
            store_idx += 1
    a[store_idx], a[end_idx] = a[end_idx], a[store_idx]
    quick_sort(a, start_idx, store_idx - 1)
    quick_sort(a, store_idx + 1, end_idx)

\(O(N)\)의 extra memory를 허용하게 하면 더 쉽게할 수 있지만 위처럼 만들면 extra memory는 starck frame의 \(O(logN)\) 만 필요합니다.

평균적으로 \(O(NlogN)\) 의 시간복잡도를 가지지만, 최악의 경우 \(N^2\) 의 시간복잡도를 가집니다.

시간복잡도에 대한 증명은 여기를 참고하세요. 근데 교수님 수업에서 적분까지 해가면서 strict하게 증명했던 것 같은데 필기가 남아있지 않네요… 나중에 그때 그 내용 어디서 찾으면 추가할게요.


Heap Sort

heapify(a, idx, heap_size):
    largest = idx
    left_idx, right_idx = 2 * idx + 1, 2 * idx + 2
    if left_idx < heap_size and a[left_idx] > a[largest]:
        largest = left_idx
    if right_idx < heap_size and a[right_idx] > a[largest]:
        largest = right_idx
    if largest != idx:
        a[largest], a[idx] = a[idx], a[largest]
        heapify(a, largest, heap_size)


heapsort(a):
    n = len(a)
    for i in range((n - 1) // 2, -1, -1):
        heapify(a, i, n)
    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        heapify(a, 0, i)

이건 코드를 좀 열심히 봐야 이해가 가더군요. 일단 heapify() 는 heap을 array로 표현했을 때 idx 위치에 있는 node의 left child, right child와 비교해서 더 셋 중 가장 큰 node를 parent 자리에 위치시키는 겁니다. 이걸 array의 뒤에서부터 해주면 아래에서 자리가 올바르지 않은 node 들이 쭉 올라와서 제자리를 찾으며 정렬이 됩니다. 그리고 두 번째 for문에서는 정렬된 heap에서 max 값인 root를 반복적으로 추출해서 array의 뒤에 위치시키는 겁니다.

complete binary tree에서 left child가 2*idx+1, right child가 2*idx+2를 index로 가지는 것은 귀납법으로 증명 가능하며, heapify를 (n-1)//2부터 하는 이유는 해당 node가 바로 child를 가질 수 있는 마지막 node이기 때문입니다.


Topological Sort

Directed Graph에서 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘입니다. Scheduler처럼 작업의 순서가 정해져 있을 때 각각의 작업이 완료되어야 끝나는 문제에 주로 쓰입니다.

topological_sort():
    q = Queue()
    for i in range(n):
        if in_degree[n] == 0: 
	    q.enqueue(i)
    for i in range(n):
        if q.is_empty():
            error
        x = q.dequeue()
        answer[i] = x
        for j in adj[x]:
            in_degree[j] -= 1
            if in_degree[j] == 0:
                q.enqueue(j)

BFS랑 비슷한데, inDegree를 이용하여 enqueue 합니다. 시간복잡도는 \(O(V+E)\) 입니다.


Hashing

Hashing

Hashing이란 Hash Function을 이용해 item의 index를 item의 key를 이용해 결정하는 것입니다.


Collision

간단하게 array length로 나눠 나머지를 index로 이용하는 방법이 있으며 서로 다른 item이 같은 위치로 배정되는 collision이 일어날 수 있습니다.


Linear Probing

collision이 일어난다면 empty spot을 찾을 때까지 선형 이동하여 해당 index로 이동시킵니다.


Search

hash function을 통해 index를 찾고 해당 key와 동일한 지 이동해가며 찾습니다.


Delete

삭제를 할 때에는 해당 index를 빈 공간으로 만들지만 marking하여 원래 item이 있던 곳임을 표시합니다.


Double Hashing

hash function 두 개를 사용해서 collision이 일어나면 hash2로 다음 spot을 찾습니다.


Chained Hashing

collision이 일어나도 해당 index에서 linked-list를 형성하며 위치시킵니다.

삽입/삭제/탑색의 시간복잡도가 사실 \(O(1)\) 은 아닌데 그렇다고 봐도 무방합니다…


Dynamic Array

처음엔 작은 길이의 array를 할당하여 사용하고, 해당 사이즈를 넘어가는 삽입이 일어나면 길이를 두 배로 늘린 array를 할당하여 item을 다 옮겨주길 반복합니다.

amortized analysis를 통해 놀랍게도 삽입의 시간복잡도가 \((nO(1) + O(n))/(n+1) = O(1)\) 이 됩니다.


String-related Algorithms

String Matching

주어진 긴 문자열(길이 m)에서 특정 문자열(길이 n)의 등장 위치를 찾는 알고리즘들입니다.


Brute Force Algorithm

모든 상황을 다 검색한다는 의미로 더 크게 쓰이기도 하지만 string matching에서는 앞에서부터 차례대로 검색하는 것입니다.

bruteforce():
    for i in range(len(text) - len(pattern) + 1):
        j = 0
        while j < len(pattern) and pattern[j] == text[i + j]:
            j += 1
        if j == len(pattern):
            print(i)

시간복잡도는 \(O((n - m + 1)m)\) 인데 보통 \(n >> m\) 인 상황이 많으며 그럴 때는 \(O(nm)\) 입니다.


Rabin-Karp Algorithm

Hashing을 이용한 알고리즘입니다.

Rabin Fingerprint라는 hash function을 사용합니다. alphabet의 길이를 d 라고 하고, pattern을 d-항식으로 두고 갑을 계산합니다. 그리고 Text의 subword에 같은 방법으로 값을 계산하여 비교하는 것입니다.

하지만 이렇게 하면 hash값이 너무 커질 수 있으니 적당한 prime number를 사용해 modular 값을 이용합니다. 그리고 False-Positive를 피하기 위해 해시값이 같을 때 문자열을 직접 비교하고 결과에 추가합니다.

rabin_karp():
    h = hash(pattern)
    for i in range(len(text) - len(pattern) + 1):
        if h == hash(text[i:i + len(pattern)]):
            j = 0
            while j < len(pattern) and pattern[j] == text[i + j]:
                j += 1
            if j == len(pattern):
                print(i)

이렇게 하면\(O(nm)\) 입니다만, Horner’s scheme을 사용하면 hash값이 한 step 전의 hash값으로 부터 \(O(1)\)에 계산하고, hit의 경우가 엄청 큰 경우가 아니라면 \(O(n + m)\) 에 가까워집니다.


Boyer-Moore Algorithm

브루트포스처럼 왼쪽에서 오른쪽을 패턴을 이동시키지만 문자 일치 검사는 패턴의 오른쪽부터 합니다.

이 때 3가지의 Bad Character Heuristic을 가집니다.

  1. text의 character가 pattern 내에 없는 경우 pattern을 그 character 너머로 이동시킵니다.
  2. text의 character가 pattern 내에 있을 경우 pattern 안의 가장 오른쪽의 character와 해당 character를 대치하도록 이동시킵니다.
  3. 아니면 한칸이동합니다.

이렇게 해도 worst case의 경우 브루트포스와 같은 \(O(nm)\) 을 가지지만 average case는 \(O(n/m)\) 으로 줄일 수 있다고 합니다. 이 계산 증명은 아직 알아보지 않았습니다. 상대적으로 좋은 heuristic이기 때문에 속도가 더 빠르다고 볼 수 있습니다.

뿐만 아니라 Good Suffix Heuristic도 사용하는데, Pattern 내부에서 suffix가 prefix로 등장할 경우, 매칭이 되다가 miss가 나왔을 시 1칸만 움직이는 것이 아니라 prefix를 suffix가 매칭되던 위치로 이동시킬 수 있습니다. 이와 같은 경우를 고려하기 위해 Text를 훑기 전, Pattern의 miss가 나는 위치에 따라 몇 칸을 이동시켜야하는지 미리 계산해두고 사용하는 것입니다.

두 Heuristic을 같이 사용하므로 둘 모두 고려하여 최대 이동거리를 사용합니다.


Edit Distance

“LewenStein distance”, 주어진 문자열 u, v가 얼마나 다른지 파악하는 것입니다. delete, insert, replace 3가지 operation을 기준으로 몇 번의 oepration을 통해 u를 v로 변환시키는지 d(u, v)로 표현합니다. rule은 여기 옮기지 않겠지만 dynamic programming으로 해결합니다.


Trie

Set of Strings을 위한 Data Structure 입니다.

alphabet의 길이를 d라고 할 때, d-ary tree 구조를 가집니다.

edge에 character가 label되었다고보고, 모든 정점은 해당 정점까지 path의 string을 의미합니다.

구현 방식으로 array를 이용하여 d 길이의 array가 각 vertex를 의미하게 만드는 방법과 linked list를 이용하는 방법이 있습니다.

공간복잡도는 string의 종류를 m이라 할 때 array를 이용하면 \(O(md)\), linked-list를 이용하면 \(O(m)\) 입니다.

탐색/삽입/삭제의 시간복잡도는 linked-list의 경우 outdegree를 전부 확인해야하므로 \(O(md)\), array는 \(O(m)\)이 됩니다.

Linked-list의 경우 edge에 길이가 1 이상인 string을 부여하여(compress paths) 효과적인 구조로 만들 수 있습니다.


Suffix Tree

Trie와 비슷해보이지만 string(+ 끝을 뜻하는 “$”)의 모든 suffix의 집합을 이용하여 만든 tree입니다. edge에는 string, node에는 index를 표시합니다. construct 시간복잡도와 공간복잡도는 \(O(n^2)\) 입니다.

String Matching에 사용되는 경우 pattern(edge 중간에 끊길 수도 있습니다)을 찾고 해당 path에서 나오는 모든 leaf node의 index에 해당 pattern이 존재합니다.

시간복잡도는 \(O(n + m)\) 입니다.


Dynamic programming

Dynamic Programming

엄밀히 말하자면 알고리즘은 아니고 알고리즘 설계 기법입니다. 답을 구하기 위해서 했던 계산을 또 하고 또 해야하는 류의 문제(Optimal Substructure)를 위해 memoization을 통해 한번 계산한 결과를 메모리에 저장해 두었다가 꺼내 쓰는 것입니다. 대표적으로 피보나치 수열을 푸는 문제의 경우 시간복잡도를 \(O(2^n)\) 에서 \(O(n)\) 으로 줄일 수 있습니다.

관련 문제를 풀고 몸에 익히는 것이 중요합니다.


PL

Static scope and Dynamic scope

Static Scope

Static Scope는 우리가 접하는 대부분의 언어에서 사용되는 방식으로 function이 정의된 곳의 environment를 사용하는 것입니다. 아래의 dynamic scope가 어떻게 다른지만 보시면 되겠습니다.


Dynamic Scope

반면에 Dynamic scope는 function이 call 된 곳의 environment를 function이 사용합니다.

{deffun {f p} n}
{with {n 5} {f 10}}

제 편의(;;)를 위해 수업에서 사용한 scheme 언어를 사용하면, 위와 같은 코드는 dynamic scope라면 n의 값이 함수 내에서도 사용되므로 5을 return하고 static scope에서는 error를 뱉게 됩니다.


First-order functions and First-class functions

First-order Functions

f(x) = 1 + x

C에서 함수를 정의하고 사용하는 방식을 생각하시면 됩니다. 그리고 아래의 first-class function을 보고 차이점을 이해합시다.


First-class functions

f = λx. 1 + x

Python에서 함수를 괄호없이 불러서 변수에 저장하는 방식이나, Javascript에서 const로 함수를 정의하여 () => ... 등의 문법을 사용하는 것을 예시로 들 수 있습니다. C에서도 함수포인터를 이용하여 비슷한 효과를 낼 수 있지만 function이 first-class object로 취급되는 언어를 이용하면 후에 Higher-order function (ex. map())을 사용할 수 있습니다.


Calling Convention

Calling Convention

함수가 호출될 때, 메모리 공간 안에서는 함수 내부의 명령어를 실행하며 사용하기 위한 Stack Frame이 할당됩니다. 이 때 parameter가 어떤 방식으로 전달되는지 아래의 여러 방식이 있습니다. 실제 Calling Convention은 parameter 전달 방법 뿐만 아니라 전달 순서, return value 전달 방법, stack frame 정리 방법, 이렇게 4가지가 있지만 parameter 전달 방법만 다루겠습니다.


Call by Value

C에서는 사실상 모든 상황에 Call by Value가 이용됩니다. Java를 예로 들면 primitive type인 int, short, long, float, double, char, boolean에 대해서 적용되며, value를 복사하여 함수의 인자로 사용합니다. swap 함수를 사용할 때 cadll by value가 적용되면 swap이 되지 않습니다.


Call by Reference

value를 복사하는 것이 아닌 해당 variable을 직접 전달하는 것입니다. C에서 변수에 &를 붙인 채 함수를 정의할 때와 같은 효과를 가집니다. Java에서 reference type인 Array, Class에 대해 적용됩니다.


Call by Address

C에서 포인터를 이용해 주소를 전달하는 것입니다. pointer를 쓰지 않는 언어에서는 언급되지 않는 것 같습니다.. 이 부분은 확실하게 확인하지 못했습니다.


Call by Assignment

Python의 경우 모든 상황에 Call by Assignment가 사용됩니다. 먼저 int, float, str, tuple은 immutable object, 그리고 list, dict, set은 mutable object로 분류하는데, mutable object는 call by reference를 적용시키고 immutable object의 경우 처음에는 call by reference를 이용하다 값이 변경되면 call by value로 전환됩니다.


Call by Name

Call by name을 이용할 경우 argument는 function call 즉시 계산되는 것이 아니라 필요시에 계산되게 됩니다.


Lazy Evaluation

Lazy Evaluation

def some_function(x, y):
    return x + 1

some_function(3, 3 + 2)

위와 같은 코드를 실행한다고 합시다. strict evaluation에서는 some_function이 call 되는 순간 3 + 2 가 계산되어야 하지만 lazy evaluation에서는 해당 parameter 값이 필요할 때에 계산합니다. 고로 위 코드에서는 y가 필요없으므로 계산하지 않고 더 높은 성능을 보일 수 있습니다.

위의 예시는 정말 간단한 경우이지만, list의 head 값을 알기 위해 quick sort를 사용할 시에 head 값이 결졍되는 대로 나머지 계산은 하지 않기도 하며, python의 if문에 여러 condition을 부여했을 때 검증이 필요없어진 condition은 evaluation 하지 않고, infinite list에 대해서도 모든 item의 계산이 필요하지 않을 때 handling이 가능해집니다.

Lazy Evaluation이 적용될 경우 해당 parameter가 함수 내의 여러 번 사용되는 경우 evaluation이 여러 번 일어나는 것을 예방하기 위해 caching 이 일어납니다.


Tail recursion and fibonacci programming

Tail Recursion

def sum(n):
    if n == 0:
        return 0
    else:
        return n + sum(n - 1)


sum(4)

위와 같은 코드를 실행한다고 합시다. 그럼 코드의 실행은 이런 식으로 전개됩니다.

sum(4)
4 + sum(3)
4 + (3 + sum(2))
4 + (3 + (2 + sum(1)))
4 + (3 + (2 + (1 + sum(0))))
4 + (3 + (2 + (1 + 0)))
4 + (3 + (2 + 1))
4 + (3 + 3)
4 + 6
10

이런 식으로 전개되며 stack frame은 sum n개가 쌓임을 볼 수 있습니다. 함수 내에서 두 번의 호출이 일어나는 fibonacci 함수는 \(2^n\) 개의 stack frame이 쌓입니다.

반면에 아래와 같이 함수를 정의한다고 합시다.

def sum(n, acc):
    return 0 if n == 0 else sum(n - 1, acc + n)


sum(4, 0)

이렇게 정의한다면 if문이 먼저 검증되고 sum() 함수가 호출되며 return 값이 돌아온 이후에 해야할 operation은 그대로 return 하는 것밖에 남지 않습니다.

sum(4, 0)
sum(3, 4)
sum(2, 7)
sum(1, 9)
sum(0, 10)
10

코드의 실행은 이런 식으로 전개되며 됩니다. javascript engine이나 jvm, cpython은 기본적으로 tail recursion optimization을 지원하지 않아 stack-frame이 4개 그대로 생성되지만 gcc나 functional programming language는 tail recursion optimization을 지원하여 return 값을 받은 후 추가적으로 해야할 operation이 없는 경우 stack-frame을 덮어씌워 새로 생성하지 않고 recursion을 iteration으로 변환합니다.


Garbage collection (GC)

Garbage Collection (GC)

C나 C++ 같은 low-level(엄밀히 말하자면 C++는 High level 입니다만) language는 변수선언, malloc()과 free()를 통해 메모리 할당과 해제가 직접 이루어집니다. 반면에 Python이나 Javascript 같은 high-level language는 Garbage Collector가 자동으로 활동하며 메모리 해제를 해줍니다.

중요한 점은 GC가 할당된 메모리에 대해 특정 시점에서 필요유무를 판단하고 해제하는 방식입니다.

CPython에서는 Reference Counting을 기반으로 한 GC가 돌아간다고 합니다.


Reference Counting

  • 모든 record(data를 담은 structure)에 대해 초기에 count 0를 부착합니다.

  • 해당 record를 가르키는 pointer(이또한 record)가 생성될 때 record의 count에 1을 더합니다.

  • 해당 record를 가르키는 pointer가 다른 곳을 가르키거나 사라지면 count에 1을 뺍니다.

  • record의 count가 0이 되면 해당 record가 가르키는 record들의 count에서 모두 1을 빼고 기존의 record를 free 해줍니다. (root record는 제거하지 않습니다.)

여기서 root record란 모든 global variable들과 현재 실행되는 함수 내의 모든 local variable을 뜻합니다. 얘네들은 free 되지 않으므로 위 알고리즘이 성립할 수 있습니다.

명시적이든 암시적이든 A라는 memory를 통해 B라는 memory를 통해 B라는 memory에 접근할 수 있다면 그것이 명시적이든 암시적이든 B는 A에 의해 reference 된다고 정의합니다. 예를 들어 Javascript object는 prototype을 암시적으로 참조하죠. 그리고 기존의 Javascript object 뿐만 아니라 function scope도 포괄됩니다.


Limitations

Cycle이 발생할 경우 free 해줄 수 없습니다. 실제로 IE6, 7은 이 reference counting algorithm을 이용하며 다음과 같은 메모리 누수가 발생합니다.

// div object는 EventHandler인 onclick 속성을 통해 참조되며, EventHandler scope에도 div object가 있으므로 cycle이 발생합니다.
var div = document.createElement("div");
div.onclick = function(){
    doSomething();
};

count를 유지하는 것은 시간을 잡아먹습니다.

locality가 좋지 않답니다.

free list를 만들어 available memory를 track 해줘야 합니다.


Mark & Sweep Garbage Collection

  • 모든 record를 흰색으로 칠합니다.

  • root로 인해 reference된 record들은 회색으로 칠합니다.

  • 아래 과정을 회색 record가 없어질 때까지 반복합니다.
    • 회색 record r을 고릅니다.
    • r이 가르키는 모든 흰색 record를 회색으로 칠합니다.
    • r을 검은색으로 칠합니다.
  • root를 제외한 모든 흰색 record를 free합니다.


Limitations

Cycle에 의해 생기는 문제는 해결하지만 Reference Counting의 나머지 문제점은 해결하지 못합니다.

  • Cost가 heap 전체에 비례하게 됩니다.
  • Locality가 좋지 않습니다.
  • free list를 유지해야 합니다.


Two-Space Copying Collectors

to-space, from-space 두 메모리 공간으로 나누어 이용합니다.

  • Allocator:
    • memory를 to-space와 from-space로 파티션합니다.
    • 메모리 할당을 to-space로만 합니다.
  • Collector:
    • to-space와 from-space의 record를 스왑해줍니다.
    • Mark & Sweep에서 회색으로 칠하는 역할을 대신 from-space에서 to-space로 보내줍니다.
    • 회색 record를 고르는 것은 to-space에서만 시행합니다.


Lambda algebra

Lambda Algebra, Lambda Function

이는 Anonymous Function이면서 First-class Function을 부르는 말입니다.


Type System

  • Type system and type checking, strong/weak type, dynamic/static type checking


Type System

Type System은 variable, expression, function, module 등 프로그램의 구성품들에 Type을 부여하는 것입니다. 기본적으로 Type System의 목적은 버그를 Runtime 이전에 미리 포착하고 방지하기 위함입니다. (동적 타입 언어는 Runtime에 Type Check가 이루어집니다.)


Polymorphic Types

Typecheck 중 (alpha -> alpha) 와 같은 타입은 어떠한 타입도 될 수 있는 alpha를 받고 해당 타입을 return한다는 뜻입니다. 따라서 명확히 적으면 ∀ alpha (alpha -> alpha) 이 됩니다.


Statc Type / Dynamic Type Checking

Static Type Checking Language에서는 Typecheck가 compile time에 이루어지며 Dynamic type에서는 runtime에 이루어집니다.


Strong Typed / Weak Typed Language

Strong Typed Language 에서는 암묵적 형변환을 허용하지 않습니다.

근데 제가 찾다보니 이 부분은 사람들마다 생각하는게 다른 것 같은데(;;) 이건 각잡고 다시 알아봐야겠습니다.


Type Soundness / Type Completeness

  • Type Soundness: 모든 well-typed program은 error를 만들지 않는 올바른 program 입니다. (no false negative)
  • 모든 올바른 program은 type-check에 통과합니다. (모든 ill-typed program은 incorrect program 입니다. => no false positive)


Compiler, interpreter

Compiler

  • Program을 통해 program을 만들어냅니다.


Interpreter

  • Program을 통해 result를 만들어냅니다.


Compiled Language

  • Runtime 이전에 Assembly Language 등으로 변환되는 언어입니다.


Interpreted Language

  • Runtime 중에 Instruction 단위로 interpret 되는 언어입니다.


Network

Packet Switching vs Circuit Switching

서킷 스위칭은 대표적으로 전화에서 쓰이는 데이터 전달 방법입니다. 전화는 시간단위로 요금을 청구하며 실시간성이 중요하기 때문에, 중간에 누군가 그 회선에 끼어들면 안되며 서킷 전체를 독점하며 속도도 일정하게 됩니다.

패킷 스위칭은 데이터를 패킷단위로 쪼개서 보내는 것이며, 서킷을 독점하지 않고 공용선을 이용합니다.


How Internet works?

Internet은 IP(Internet Protocol), TCP(Transport Control Protocol) 등 프로토콜에 합의된 방식으로 Packet을 주고 받는 거대한 네트워크입니다.

What’s a protocol

프로토콜은 컴퓨터가 네트워크 내에서 어떤 방식으로 통신해야하는지 정한 규칙의 집합입니다.


What’s a packet

Internet으로 전달되는 데이터를 Message라고 할 때, Message가 전송될 때, 먼저 해당 Message를 packet이라는 조각으로 잘게 나눕니다. 이 패킷들은 서로 독립적으로 전송되며 IP(Internet Protocol)은 어떤식으로 패킷화되어야 하는지 명시하고 있습니다.


What’s a packet routing network

Packet Routing Network란 패킷을 시작 지점 컴퓨터로부터 도착 지점 컴퓨터까지 전달하는 네트워크입니다. 인터넷은 수많은 Router들로 이루어져 있으며 각 router의 역할은 패킷을 출발지점으로부터 목적지로 옮기는데에 있습니다. 패킷은 도착지까지 도달하기 위해 다수의 Router를 지나게 됩니다.

한 Router로부터 다음 Router까지 이동하는 것을 Hop이라고 부릅니다. Internet Protocol에 의하면 Router는 packet의 header에 address를 명시하여 보내야 합니다.


Where did these Internet routers come from? Who owns them?

1960년대 ARPANET이 인터넷의 시초가 된 이후 ISP(Internet Service Providers)가 router들을 네트워크 내로 추가하였습니다. 인터넷 라우터의 주인이 되는 개인은 없습니다. ARPANET 이후 정부기관, 대학, AT&T와 같은 기관이 router를 점진적으로 추가하였습니다.


Do the packets always arrive in order? If not, how is the message reassembled?

Internet Protocol은 패킷이 목적지에 도달한다는 것에 대해 확신을 제공하지 않습니다. Packet Loss 가 일어날 수 있습니다. Transmission Control Protocol은 packet loss를 retransmission으로 해결합니다. 도착지에서 출발지점으로 ACK 패킷을 보내게 합니다. 도착지에서 누락된 패킷이 있음을 인식하면 출발지에 retransmission을 요청합니다. 이 과정은 사실 더 복잡한데 아래에서 차근차근 다루겠습니다.


What do these Internet addresses look like?

이 주소들은 IP 주소로 불리며 2가지 표준이 있습니다.

IPv4는 예를 들어 212.78.1.25와 같이 생겼으며 이는 IPv4가 \(2^{32}\)개의 주소값을 허용하기 때문이며, 새로 제시된 IPv6 표준에서는 주소가 3ffe:1893:3452:4:345:f345:f345:42fc와 같이 생겼으며 \(2^{128}\)개의 주소값을 허용합니다. 2014년 구글에 의하면 당시 IPv6 트래픽은 전체의 3% 밖에 되지 않았다고 합니다.


How can there be over 8 billion networked devices on the Internet if there are only about 4 billion IPv4 addresses?

이유는 public IP address와 private IP address가 존재하기 때문입니다. Local Network로 접속하는 기기들은 같은 public IP address를 공유합니다. 그리고 이 local network 내에서 기기들은 서로 다른 private IP address로 구별됩니다. 일반적으로 192.168.xx, 172.16.x.x, 10.x.x.x 등의 구조를 가집니다. 그리고 이 private IP address는 Dynamic Host Configuration Protocol (DHCP)에 의해 할당됩니다.

예를 들어 같은 local network 내에 있는 노트북과 스마트폰으로 www.google.com에 요청을 보낼 시, 모뎀을 떠나는 패킷은 패킷 헤더에 기기에 배정되는 포트번호를 담고, 응답이 돌아왔을 시 그 포트번호를 이용해 올바른 기기에게 응답을 전달해줍니다.

private IP address를 public IP address에 매핑하는 프로토콜은 NAT(Network Address Translation) protocol을 통해 이루어집니다.

이 관점에서 IP address는 기기에 특수하게 부여되지 않은 것으로 보입니다. 기기에 유니크하게 부여되는 주소는 MAC address 입니다. MAC address는 기기의 life를 통틀어 하나로 특정됩니다.


How does the router know where to send a packet? Does it need to know where all the IP addresses are on the Internet?

라우터는 IP 주소가 어디를 가르키는지 전부 알지는 못합니다. 오직 Outbound Link 라 불리는 이웃한 주소만 알고 있죠.

IP address는 Network Prefix와 Host Identifier 두 부분으로 나누어 집니다.

예를 들어 129.42.13.69는 아래와 같이 나누어집니다.

Network Prefix: 129.42
Host Identifier: 13.69

대학, 기관, ISP(Internet Service Provider) 등 큰 단위의 단일 위치로 연결되는 라우터들은 모두 같은 Network Prefix를 가집니다.

모든 라우터는 129.42.*.* 형식의 IP address를 같은 곳으로 먼저 보내게 되는것이죠. 이 방법으로 라우터가 기억해야할 주소는 확 감소됩니다.


If a new router is added to the Internet how does it know how to handle packets for all these network prefixes?

새로 설치된 라우터가 패킷을 어디로 라우트해야할 지 모르는 경우가 나올 수 있습니다. 그럴 때는 라우터가 이웃하는 라우터들에게 해당 패킷을 전송해야할 곳의 정보를 알고 있는지 쿼리를 보냅니다. 그리고 이웃한 라우터들은 정보를 파악하여 시작점이었던 라우터에게 되돌려 줍니다. 그리고 라우터는 그 정보를 저장하여 다음에 바로 전송할 수 있도록 준비합니다. 이 알고리즘은 원래 더 복잡한데 생략합니다. 이 방법으로 라우터는 Routing Table이라는, Network Prefix와 Outbound Link를 묶은 정보들을 가집니다.


How do networked computers figure out IP addresses based on domain names?

컴퓨터는 www.google.com과 같은 domain name을 이용해 IP address를 얻어내야 합니다. 이는 Domain Name System(DNS)를 이용해 이루어집니다.

IP address를 얻기 위해 컴퓨터는 먼저 local DNS cache를 참조합니다. local DNS cache에는 최근 방문했던 domain name과 IP address가 저장되어 있습니다. 캐시에서 찾아내지 못했거나, 해당 IP address 기록이 만료되었다면(TTL: Time To Live가 처음 요청을 받아올 때 적혀옵니다.) ISP의 DNS server로 요청을 보냅니다. 같은 방식으로 ISP의 DNS server에서도 IP address를 구하지 못하면 Root Name Server로 요청을 보냅니다. Root Name Server는 해당 도메인의 IP를 전부 갖고 있진 않고 주소 맨 오른쪽에 있는 .com .net 같은 Top-level Domain을 보고 해당 도메인들을 관리하는 서버의 주소를 알려줍니다. 그를 통해 ISP는 해당 Top-level Domain 관리 서버로 요청을 보내 IP address를 받아옵니다.


How do applications communicate over the Internet?

Internet은 몇 개의 층으로 나눌 수 있습니다. OSI 7 Layer나 TCP/IP 4 Layer가 있지만 여기서는 후자의 구조를 거론하겠습니다. Internet은 Internet Network Layers로 나뉘며 Link Layer, Internet Layer, Transport Layer, Application Layer가 있습니다. 이들이 Layer라 불리는 이유는 각 레이어가 다른 레이어 위로 쌓아 올려졌기 때문이며, 각 레이어는 해당 레이어 아래 레이어들의 기능을 상세히 고려하지 않고도 모두 포함하며 작동합니다.

Internet Application은 Application Layer에 기반하여 작동하며 그 아래 레이어들의 기능을 자세히 고려하지 않아도 됩니다. 예를 들어, 어플리케이션이 네트워크 다른 어플리케이션과 TCP를 이용하여 통신할 때는 Socket이라는 구조를 이용하며, 이는 packet routing과 re-assembling의 복잡한 구성에 대한 걱정을 없애줍니다.


What do each of these Internet Layers do?

  • Link Layer

가장 낮은 레벨의 Link Layer는 “physical layer”라고도 불리며 데이터를 bit 단위에서 케이블이나 wifi signal을 통해 어떻게 전달되는지를 고려합니다.

  • Internet Layer

Link layer 위에는 Internet Layer가 위치합니다. Internet Layer는 패킷을 목적지로 라우팅하는 것을 고려합니다. 앞의 언급된 Internet Protocol이 이 레이어에서 사용합니다. Internet Protocol에 따라 network load나 outage를 따져 패킷의 목적지를 동적으로 조정하고 reroute합니다.

  • Transport Layer

그 위로는 Transport Layer가 있습니다. 이 레이어에서는 아래의 Internet과 Link Layer에서 data 전송이 완전히 되지 않을 시를 위해 보정하는 작업이 일어납니다. 주로 Transmission Control Protocol(TCP)에 따라 packet loss에 반응하여 해당 packet을 재전송합니다.

  • Application Layer

맨 위에는 Application Layer가 있습니다. 패킷 통신 관련 복잡한 작업은 아래 레이어에서 해주며 이 레이어에서는 그를 이용하여 인터넷의 다른 어플리케이션들과 통신합니다. 이곳에는 HTTP Protocol이 적용되어 웹 브라우저와 웹 서버가 어떻게 상호 작용하는지 정해집니다. email client와 관련된 작업에는 IMAP protocol이, File-downloading client와 file-hosting server 사이의 통신에는 FTP protocol이 적용됩니다.


What’s a client versus a server?

Client와 Server는 모두 인터넷을 통해 통신하는 어플리케이션입니다. 그 중 Client는 “유저와 더 가까운 편”이라고 말할 수 있습니다. Web browser나 email client, smart phone app 등을 통해 유저를 직접 상대하는 어플리케이션이죠. 그리고 Sever는 remote computer에서 작동하며 client가 필요에 의해 통신하는 어플리케이션입니다.


How can sensitive data like credit cards be transmitted securely over the Internet?

초기의 인터넷에서는 서로 다른 위치에서 router와 link를 통해 네트워크 안에서 연결되어있음을 확인하면 그것만으로 충분했습니다. 하지면 이젠 인터넷의 크기가 커지고, 라우터가 늘어났습니다. 통신을 통해 거치는 라우터의 수가 늘어난다는 것은 취약한 지점이 많아짐을 뜻하고, 더 나아가 WiFi와 같이 무선통신이 이용되면서 해커들이 패킷을 허공에 뿌려서 공격할수도 있게 되었습니다.

이전의 구조만으로는 네트워크 연결이 안전한지 장담할 수 없게 되었고 그에 대한 해답으로 SSL/TLS를 통한 encryption과 authentication이 생겼습니다.


What is SSL/TLS?

SSL은 Secured Sockets Layer를, TLS는 Transport Layer Security를 뜻합니다. SSL은 Netscape에 의해 1994년 생겼으며 시간이 지나 수정을 거쳐 TLS로 이름이 정정되어 현재는 SSL/TLS라는 명칭으로 합쳐서 불립니다.

SSL/TLS는 선택적으로 사용되어 Transport Layer와 Application Layer 사이에 위치합니다. SSL/TLS는 민감한 정보를 encryption과 authentication을 통해 보호합니다.

Encryption은 client가 server로 보내는 TCP connection을 요청을 암호화하는 것을 말합니다. message가 packet으로 나뉘기 전에 일어나기에, 해커가 packet을 가로챈다해도 기존의 message를 파악할 수 없게 됩니다.

Authentication은 client가 server로 보이는 녀석을 믿을 수 있는지 판단하는 것입니다. 이를 통해, client와 server 사이에서 악의적인 간섭을 일으키는 Man-in-the-middle attack을 막을 수 있습니다.

SSL이 적용된 웹사이트는 http가 아닌 https 프로토콜을 사용합니다.


How does SSL authenticate the identity of a server and encrypt their communication?

SSL은 Asymmetric Encryption과 SSL Certificate를 이용합니다.

Asymmetric Encyption은 소수로 이루어진 public key와 private key를 이용합니다. private key는 decryption, public key는 encryption에 이용되며 “Asymmetric”인 이유는 Symmetric encryption과 달리 encryption과 decryption에 이용되는 key의 값이 다르기 때문입니다.

SSL certificate은 public key를 내장한 digital document입니다. SSL certificate는 CA(certificate authority: 인증기관)을 통해 발급됩니다.

Client가 SSL-encrypted connection을 서버에 요청할 시, 서버는 SSL certificate(인증서)를 client로 먼저 보냅니다. 그리고 client는 SSL certificate을 확인하여 아래 사항들을 확인합니다.

  • 인증서가 해당 서버를 담고 있는지,
  • 인증서가 믿을 수 있는 CA를 통해 발급되었는지,
  • 만료되지 않았는지

그 후 client는 인증서의 public key를 이용해 temporary secret key를 만들어 server로 보냅니다. 이제 server는 private key를 이용해 해당 secret key를 해석하며 양쪽은 secret key를 이용해 secret key의 기간이 만료될 때까지 encryption과 decryption을 하며 패킷을 주고 받습니다.


What happens if a hacker intercepts an SSL-encrypted session?

만약 해커가 client와 server 사이 message를 가로챈다면 SSL certificate과 temporary secret key를 볼 수 있지만 private key가 없으므로 secret key를 해석할 수 없으며 그러므로 message를 해석할 수 없습니다.


Summary

  • 인터넷은 탈중앙화된 컴퓨터 네트워크를 목적으로 개발된 1960년대 ARPANET로부터 시작되었습니다.
  • 물리적으로 인터넷은 wire, cable, radio signal을 이용해 bit를 전달하는 컴퓨터의 집합입니다.
  • 인터넷은 각각 더 작은 문제들을 해결하는 여러 개의 레이어로 구성됩니다.
  • 서로 다른 레이어에서 인터넷과 어플리케이션이 어떻게 작동하는지 기술하는 HTTP, IMAP, SSH, TCP, UDP, IP 등의 프로토콜들이 있습니다. 이 관점에서 인터넷은 컴퓨터와 프로그램이 네트워크를 이루기 위해 어떻게 행동하는지 정한 양식의 집합입니다.
  • 인터넷이 거대해지고 WiFi, 전자 상거래가 생기며 보안을 위해 SSL/TLS가 개발되었습니다.


UDP, Handshake, HTTP

Difference between TCP and UDP

Transport Layer에 사용되는 Transport Protocol에는 TCP(Transmission Control Protocol) 뿐만 아니라 UDP(User Datagram Protocol)도 사용될 수 잇습니다. TCP는 신뢰성이 있는 연결을 지향하며 UDP(User Datagram Protocol)는 빠른 전송을 지향합니다.


UDP (User Datagram Protocol)

Datagram은 packet에 비해 추상적인 개념으로 message를 뜻합니다. 이름에 굳이 Datagram이 들어갔는지 잘 모르겠습니다만 UDP도 packet을 이용해 통신합니다.

UDP에서는 TCP와 달리 비연결형 프로토콜로 3-way handshaking과 같은 연결 설정 없이 전송이 이루어집니다. UDP헤더의 checksum을 이용해 최소한의 오류만 검출하며 신뢰성이 낮지만 TCP보다 속도가 빠릅니다. 때문에 신뢰성보다 연속성이 중요한 streaming에 자주 사용됩니다.


TCP (Transmission Control Protocol)

TCP에서는 보낸 데이터가 확실히 상대방에게 전달이 잘 되었는지 확인하는 과정이 존재합니다. 전송 순서와 수신 여부를 보장하며 1:1 통신으로 이루어지고 UDP에 비해 속도가 느립니다.

먼저 연결 설정으로 3-Way Handshaking 과정을 통해 목적지와 수신지를 확실히 하여 정확한 전송을 보장합니다. 연결 해제 시에는 4-way handshaking(teardown) 과정을 거칩니다.

flow-control: 상대방의 buffer overflow를 막기 위해 데이터 처리 속도가 조절됩니다.

congestion-control: 네트워크 내의 패킷 수가 넘치게 증가하지 않도록 방지합니다.

full-duplex: 전송이 양방향으로 동시에 일어날 수 있습니다.

point-to-point: 각 연결이 정확히 2개의 종단점을 가지고 있습니다.


3-Way Handshake

  1. 클라이언트는 서버에 접속을 요청하는 SYN(x) 패킷을 보냅니다.
  2. 서버는 클라이언트의 요청인 SYN(x)를 받고 클라이언트에게 요청을 수락한다는 ACK(x+1)과 SYN(y)가 설정된 패킷을 보냅니다.
  3. 클라이언트는 서버의 수락 응답인 ACK(x+1)와 SYN(y) 패킷을 받고 ACK(y+1)를 서버로 보내며 ESTABLISHED 상태가 됩니다.


4-Way Teardown

  1. 클라이언트는 연결을 종료하겠다는 FIN(x) 패킷을 전송합니다.
  2. 서버는 FIN(x)를 받고 ACK(x+1)을 보냅니다. 미리 전송되었던 데이터를 모두 받기 때까지 서버는 잠시 CLOSE_WAIT 상태로 머무릅니다.
  3. 시간이 지난 후 서버는 FIN(y) 패킷을 보냅니다.
  4. 클라이언트는 FIN(y)를 받고 ACK(y+1)를 보내고 잠시 기다립니다. 서버는 ACK(y+1)를 받고 CLOSED되며 클라이언트또한 시간이 지난 후 CLOSED됩니다.


What are HTTP methods? List all HTTP methods that you know, and explain them.

HTTP란 Hyper Text Transfer Protocol의 두문자어로, application layer에서 어플리케이션이 데이터를 주고받기 위해 설정된 프로토콜입니다.

HTTP에 맞추어 이루어지는 요청에는 아래와 같은 메소드들이 있습니다.

  • GET 메소드는 특정 리소스의 표시를 요청합니다. GET을 사용하는 요청은 오직 데이터를 받기만 합니다.

  • HEAD 메소드는 GET 메소드의 요청과 유사한 응답을 요구하지만, 응답 본문을 포함하지 않습니다. 헤더 정보 이외에는 어떤 데이터도 보내지 않으며 웹 서버의 다운 여부 점검(Health Check)나 웹 서버 정보(ex. version) 등을 얻기 위해 사용될 수 있습니다.

  • POST 메소드는 서버에 데이터를 보내기 위해 쓰입니다. customer info, 파일 업로드 등이 있습니다.

  • PUT 메소드는 타겟 리소스를 제출하는 데이터로 완전 교체합니다.

  • DELETE 메소드는 타겟 리소스를 제거합니다.

  • CONNECT 메소드는 URI(Uniform Resource Identifier)로 인식된 서버로의 연결을 맺습니다.

  • OPTION 메소드는 타겟 리소스를 위한 communication option 설명을 얻습니다.

  • TRACE 메소드는 타겟 리소스의 경로를 따라 메시지 loop-back 테스트를 합니다.

  • PATCH 메소드는 PUT과 유사하지만 여기서는 전체를 교체하지 않고 일부를 변경합니다.


Keep-Alive

  • TCP/IP 에서의 Keep-Alive

두 소켓간 아무런 통신도 하지 않는 상태가 된지 어느 정도 시간이 지난 후 payload가 없는 패킷을 health-check 용도로 주기적으로 보내는 것입니다. 반응이 없으면 접속을 끊으며, 이를 사용하는 주된 이유는 종단 시스템 중의 하나가 다운될 때 발생할 수 있는 한쪽만 열린 연결 상태를 정리하기 위함입니다.

  • HTTP 에서의 Keep-Alive

HTTP는 본디 종단의 연결상태를 유지하지 않지만 keepalive 설정을 사용하면 유지하게 됩니다.


REST, RESTful

REST (Representational State Transfer)

HTTP URI를 통해 리소스를 명시하고, HTTP Method를 통해 해당 리소스에 대한 CRUD Operation을 적용하는 것을 의미합니다.

  • CRUD: Create, Read, Update, Delete 를 묶는 약어로 데이터베이스에 해당되는 용어입니다.

즉 REST는 Resource Oriented Architecture로, 리소스가 있고 HTTP 메소드를 통해 리소스를 처리하도록 설계된 아키텍쳐를 의미합니다. 웹 사이트의 이미지, 텍스트, DB 내용 등 자원에 고유한 ID인 HTTP URI를 부여합니다.

최근의 서버 프로그램은 다양한 브라우저와 안드로이드, 아이폰과 같은 모바일 디바이스와도 통신할 수 있어야 하며, REST 구조와 범용성은 이를 효과적으로 실현해줍니다.

REST API란 REST 기반으로 구현한 API를 말합니다.


RESTful

RESTful은 일반적으로 REST 아키텍쳐를 구현하는 웹서비스를 나타내기 위해 사용되는 용어입니다.


Proxy, CORS

Proxy

프록시는 웹 클라이언트의 요청 URI를 클라이언트에서 서비스의 서버로 직접 보내는 것이 아닌 프록시 서버로 요청하게 하여 중계기로서 대리로 통신을 수행하는 기능을 가르킵니다.

프록시 서버를 이용하는 목적은 주로 두 가지가 있습니다.

  1. 프록시 서버를 사용하여 고객이 프록시서버를 통해 웹서핑을 하도록 만들게 되면, 프록시서버에서 자주 가는 웹사이트에 대한 캐시를 쌓아놓고 좀 더 빠르게 웹서핑을 가능하게 하는 이점이 있습니다.
  2. 익명성 혹은 막혀있는 웹사이트를 우회하여 접속할 수 있기에 내부 네트워크 및 방화벽으로 인해 P2P 사이트, 한국 IP를 막아놓은 사이트 등에 접속할 수 있는 경우가 있습니다.


CORS (Cross Origin Resource Sharing)

HTTP 요청은 기본적으로 Cross-Site HTTP Request가 가능합니다.

다시 말해, <img> 태그로 다른 도메인의 이미지 파일을 가져오거나, <link> 태그로 다른 도메인의 CSS를 가져오거나, <script> 태그로 다른 도메인의 Javascript 라이브러리를 가져오는 것이 모두 가능합니다.

하지만 스크립트 내에서 생성된 요청는 Same-Origin Policy를 적용 받기 때문에 Cross-origin HTTP 요청이 불가능합니다. AJAX가 널리 사용되면서 스크립트에서 생성되는 요청에도 Cross-origin HTTP 요청이 가능해야 한다는 요구가 늘어나 W3C에서 제시한 것이 바로 CORS입니다. 모던 브라우저들은 cross-origin HTTP 요청의 위험성을 완화시키기 위해 (XMLHttpRequest와 같은) API 컨테이너 내에서 CORS를 사용합니다.


Domain 입력부터 화면이 나타날 때까지

The process from the time you type in google.com to it finishing loading on your screen.

  1. 브라우저는 대체로 URI를 HTTP를 사용하는 http://google.com, 재설정합니다. 아래의 과정을 통해 요청이 전달되고 해당 uri에서 HTTPS를 강제한다면 https://google.com로 다시 요청 과정을 반복하게 됩니다. 단, 크롬과 파이어폭스는 HTTP Strict Transport Security라 불리는 preload list를 이용하여 어떤 웹사이트가 HTTPS를 통해야 하는지 명시하기 때문에 이 리스트가 먼저 참조됩니다.
  2. DNS의 IP 주소를 조회해야 하는데, 먼저 브라우저의 캐시에 도메인이 저장되어 있는지 확인합니다. 없을 경우 컴퓨터에 저장된 hosts라는 파일을 확인합니다. 여기에도 없을 경우 Local Network의 local DNS cache를 참조합니다. 여기도 없으면 ISP의 DNS 서버로 요청을 보냅니다. 같은 방식으로 또 찾지 못하면 Root Name Server로 요청을 보내며, Top-level DNS server를 찾아가 IP address를 공수해옵니다. 이 과정에서 쓰이는 Transport Protocol은 UDP입니다. 이는 Domain의 IP 주소를 찾는 과정이 신뢰성 확보를 필요로 하지 않기에 UDP를 이용해 고속으로 동작시키기 위함입니다.
  3. 클라이언트(내 컴퓨터)와 구글 서버 사이에서 TCP 3-Way Handshake를 통해 TCP 연결이 ESTABLISHED 됩니다.
  4. 이후 SSL Handshake가 진행됩니다. 클라이언트가 서버로 SSL-encrpyted connection을 요청하고, 서버는 클라이언트로 SSL certificate(인증서)를 보냅니다.
  5. 클라이언트는 CA의 Public Key를 이용하여 Certificate을 해독하여 서버의 public key를 획득하며 해당 서버가 믿을 수 있는 실제 구글 서버임을 확인합니다.
  6. 클라이언트는 public key를 이용하여 temporary secret key를 만들어 서버로 보냅니다. 이제 서버는 서버가 가진 private key를 이용해 secret key를 해석하며 양쪽은 그 secret key를 이용해 secret key의 기간이 만료될 때까지 encryption과 decryption을 하며 패킷을 주고 받습니다.
  7. 이제 클라이언트는 서버로 HTTP GET 메소드를 통한 요청을 보냅니다. (HTTP 코맨드들은 SSL/TLS 암호화와 독립적으로 사용됩니다.)
  8. 서버는 상태를 나타내는 코드(200)와 함께 google.com의 HTML 내용의 Payload를 보냅니다.
  9. 클라이언트는 HTML에서 참조하는 모든 자원(image, CSS, favicon 등)에 대해 GET 요청을 보내는 프로세스를 반복합니다.
  10. 서버가 모든 리소스를 제공하면 브라우저가 페이지를 그리게 됩니다. HTML, CSS, JS의 구문 분석과 렌더링이 이루어집니다. 렌더링은 DOM Tree를 구성하고 렌더트리 구성, 렌더트리 레이아웃 배치, 렌더트리 그리기로 이루어집니다.


DOM Tree, Render Tree?

  • DOM Tree

DOM은 문서의 객체 모델(Document Object Model)로 HTML이나 XML내에 들어있는 요소를 구조화 객체 모델로 표현하는 양식입니다. 트리 구조를 가집니다.

  • Render Tree

Render Tree란 DOM Tree와 CSS 마크업을 처리한 CSSOM Tree를 결합하여 형성된 트리입니다.


etc

Traditionally, why has it been better to serve site assets from multiple domains?

  1. asset을 여러 도메인에서 받아온다는 것은 여러 서버를 이용한다는 것이므로 병렬화가 이루어져 효율적으로 통신이 됩니다.
  2. HTTP 요청 시 HTTP 헤더에는 이전 요청에 대한 정보가 담긴 cookie가 포함되는데, 한 도메인으로 모든 asset의 요청을 보낸다면 축적된 cookie를 계속 들고 다녀야하므로 여러 도메인에 따로 요청이 이루어지면 자연스레 cookie-less 도메인을 이용하게 되므로 부하를 줄일 수 있습니다.


What is domain pre-fetching and how does it help with performance?

domain pre-fetching은 클라이언트가 한 페이지에 머무는 동안 해당 페이지의 백그라운드에 존재하는 link들에 대해 DNS lookup를 미리 진행하고 cache에 담아두는 작업입니다. 유저가 페이지에 머무는 시간을 이용해 후에 진행될 수도 있는 작업을 미리 해두므로 후에 이루어질 작업에 걸리는 시간을 최소한으로 줄이고 성능을 향상시킵니다.


OS

What is an OS(Operating System)?

Operating System Definition

  • 엄밀한 정의는 없습니다.

  • 사용자가 컴퓨터를 쉽게 다룰 수 있게 해주는 인터페이스 정도..


System Call

운영체제는 Kernel Mode와 User Mode로 나뉘어 구동됩니다. 어플리케이션이 하드웨어에 직접 접근하는 것을 막기 위해 파일 수정, 프로세스 실행, 프로세스 종료 등 low-level 명령들은 kernel-mode에서 실행됩니다.

이렇게 커널모드로의 전환과 로우레벨 명령(시스템 콜)은 시스템 콜 인터페이스의 도움으로 이루어집니다.


Program, Process, Thread

Program

프로그램은 실행 가능한 명령어의 집합입니다.


Process

프로그램의 명령어와 정적 데이터가 메모리에 적재되어 실행 중인 상태를 말합니다. 프로그램당 최소 1개의 스레드 (메인 스레드)를 가집니다.


Thread

프로세스가 할당받은 자원을 이용하는 실행의 단위를 말합니다.


Context Switch

CPU가 현재 진행 중인 프로세스가 아닌 다른 프로세스를 진행하기 위해 현재 프로세스의 상태를 저장하고 다음 진행할 프로세스의 상태값을 읽어오는 과정을 말합니다.

스레드 간의 switch도 context switch라고 부르는지는 확실히 모르겠습니다만 스레드 교체의 경우 페이지테이블, heap, static, code 영역을 교체할 필요가 없기 때문에 process switching 보다 빠릅니다.


Memory allocation for a program

왼쪽은 단일 쓰레드 프로세스, 오른쪽은 멀티쓰레드 프로세스의 구성입니다.


프로레스 내의 논리적 주소 구조


Code (혹은 Text) 영역

프로그램의 명령어들이 올라가 있습니다.


Data (혹은 Static) 영역

Global variable, static variable, array, structure 등이 저장됩니다.

초기화된 데이터의 영역과 초기화 되지 않은 데이터(bss)의 영역이 분리되어 있습니다.


Heap 영역

Dynamic memory allocation은 이 영역을 할당합니다. (ex. malloc(), realloc(), free())

DS에서 배운 Heap과는 관계가 없다고 합니다;


Stack 영역

local variable, parameter, return value 등 잠시 사용되었다가 사라지는 데이터를 위해 할당되는 공간입니다.


Scheduling, Synchronization

Scheduling

CPU는 한번에 여러 프로세스를 처리할 수 없기 때문에 순간 어떤 프로세스가 CPU를 사용해야 효율적으로 작업할 수 있는지 정리하는 것입니다.

FCFS, SJF, RR, Priority-based Schduling, Multi-level Queue Scheduling 등의 스케쥴링 알고리즘이 있습니다.


Synchronization

Synchronization은 아래의 mutex, semaphore 등을 이용하여 공유 자원 접근으로 인해 발생될 수 있는 conflict를 피하는 것입니다.


Mutex, Semaphore, Monitor

Mutex

멀티스레드, 멀티프로세스 환경에서 공유 자원에 대한 접속을 제어하기 위해 사용됩니다. 하나의 스레드만 뮤텍스 객체를 소유할 수 있으므로 공유 자원에 대한 접근이 있는 Critical Section 앞에 mutex에 대한 요청을 추가한다면, 오직 한 스레드만 해당 섹션에서 작동할 수 있습니다.


Semaphore

뮤텍스와 유사하지만 최대 한 스레드가 아닌 설정된 수의 스레드가 접근할 수 있게 한 것입니다.


Monitor

Semaphore 보다 높은 레벨의 객체로, mutex나 semaphore로 구성된 lock을 갖고 해제하고, 그 다음 스레드가 실행되고 이 과정을 처리하는 함수들을 구현해 놓은 것입니다.


Deadlock

Deadlock이란 모든 스레드가 락이 플리기를 기다리고 있는 무한 대기 상태(교착 상태)에 빠진 것을 말합니다.

Deadlock의 조건

  1. Mutual Exclusion: 한 번에 한 스레드만 공유 자원을 사용할 수 있습니다.
  2. Hold and Wait: 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가 해당 권한을 양보하지 않은 상태에서 또 다른 자원에 대한 권한을 요구합니다.
  3. No Preemption: 한 스레드가 다른 스레드의 자원을 강제로 뺏어갈 수 없습니다.
  4. Circular Wait: 이 자원 접근 관계에 순환이 존재합니다.

교착상태는 예방하여 회피하거나, 현재 교착을 탐지하여 회복하거나, 무시하는 방식이 있습니다. 예방은 banker’s algorithm 등을 이용하며 회복은 deadlock의 조건 중 하나를 제거함으로 이루어집니다. 둘다 cost가 비싸서 모던 OS는 그냥 무시하고 있습니다.


Virtual Memory

Virtual Memory

Logical Memory와 Physical Memory를 분리해주는 테크닉입니다. 또한 프로세스 전체가 메모리에 올라오지 않더라도 실행이 가능하며, Copy-on-Write 등으로 가상 메모리가 물리적 메모리의 크기보다 커질 수 있습니다.

Demand Paging 기법을 사용하지 않고 프로세스를 위한 메모리를 연속적으로 할당한다면,

  • External Fragmentation: 남는 공간을 합치면 요청을 만족시키지 않지만 연속직이지 않기 때문에 메모리 할당 불가능

  • Internal Fragmentation: partition보다 살짝 작은 메모리가 할당되어 남는 공간이 버려짐

등의 문제가 생깁니다.


Translation Lookaside Buffer (TLB)

Page Table은 Main memory에 적재되며 CPU와 Main memory 사이의 TLB는 페이지 테이블의 최근 쓰인 엔트리들을 캐싱하는 역할을 합니다.


Difference between L1 and L2 cache

CPU는 여러 레벨의 캐시를 가지고 있습니다. 캐시는 CPU에서 Main Memory로 접근하는데 걸리는 시간을 절약하기 위해 메인 메모리의 instance를 가져와 캐싱합니다. CPU와의 거리에 따라 L1, L2, L3 캐시로 나뉘며 낮은 레벨의 캐시를 먼저 참조하게 됩니다.


etc

Difference between out-of-memory and stack-overflow

out-of-memory는 heap, stack-overflow는 stack의 공간 부족을 의미합니다.


Difference between 64bit and 32bit processor

기본적으로, CPU가 읽고 처리하는 instruction(?)의 길이가 32bit와 64bit로 다릅니다. 32bit의 instance는 \(2^32\) 개의 서로 다른 메모리 주소를 표현하므로 4GB의 메인 메모리(RAM)을 표현할 수 있으며 64bit에서는 훨씬 큽니다… 엄청 커요.


Languages

OOP

OOP(Object-Oriented Programming) basic

OOP basic

객체 지향 프로그래밍은 프로그램을 명령어의 목록으로 보는 시각을 벗어나 필요한 데이터를 추상화시켜 객체의 모임으로 파악하고자 하는 것입니다.


장점

OOP(객체 지향 프로그래밍)와 다른 개념으로는 C 언어를 사용한 절차적 프로그래밍이 있습니다. 물론 C언어로도 객체 지향 프로그래밍이 가능합니다. 기존의 절차적 프로그래밍을 이용하면 프로그래밍을 어떠한 논리를 어떤 순서대로 써나가는 것인가가 지배적인 관점이었습니다. 이 방식으로는 실제 프로그램 내에서 많은 상호작용이 있을수록 코드가 복잡해지고 파악이 힘들어집니다. 스타크래프트를 순서도로 그려야 된다고 생각하면 이를 예감할 수 있습니다. 이런 경우 객체 지향 프로그래밍을 이용해 캡슐화, 다형성, 상속을 이용해 코드 재사용을 증가시키고, 유지보수를 감소시키는 장점을 얻을 수 있습니다.

명확히 장점을 제대로 이해하기 위해서는 아래 아래의 원칙 5가지를 봐야합니다.


단점

하지만 캡슐화와 격리 구조 설계로 인해 기능을 묶으면 결국 함수 호출이 추가로 들어가거나 계산식 중간에 포인터 연산 등이 필요해지며, 멤버 함수 같은 경우 어느 객체의 함수인지 지정해야 하기 때문에 역시나 절차적 프로그래밍보다는 무거워지고 성능 하락이 있습니다. 또한 개념을 기준으로 나누다보니 객체마다의 메모리 크기가 달라지며, 결국 고정된 연속 메모리에 담을 수가 없게 됩니다. 메모리 할당을 배열로 하지 못하게 되니 따로따로 생성하며 이렇게 각각의 객체의 생성과 파괴가 반복되면 fragmentation 문제가 생기게 됩니다.

절차지향프로그래밍이란, 단순히 특정 프로그래밍 언어들을 이루는 말이 아닌 프로그램 설계방법론이자 개념의 일종입니다. 하지만 일반적으로 아래 5개의 특성을 제공한다면 그 언어는 객체지향언어로 불립니다.


특성 6가지

클래스 + 인스턴스(객체)

  • 클래스: 어떤 문제 해결을 위한 데이터를, 추상화를 거쳐 집단에 속하는 속성(attribute)와 행위(behavior)를 변수와 메소드로 정의한 것입니다.

  • 인스턴스(객체): 클래스에서 정의한 것을 토대로 실제 메모리 상에 할당된 것을 말하며 실제 프로그램에서 사용되는 데이터입니다. 인간은 클래스이며 저는 인스턴스가 됩니다.

함수와 메소드의 차이는, 함수는 이름으로 호출할 수 있는 코드 조각이지만, 메소드는 객체의 연결된 이름으로 불리며 메소드를 호출할 때 객체도 호출되는 것입니다. 또한 메소드는 해당 객체의 속성에 접근할 수 있습니다.


추상화

변수와 함수를 하나의 단위로 묶는 것을 의미합니다. 구체적은 것을 분해해서 관심영역에 있는 특성만을 가지고 재조합하는 것입니다.

대개 프로그래밍 언어에서 이 번들링은 클래스를 통해 구현됩니다.


캡슐화

클래스가 제공하는 메소드의 기능만을 사용할 뿐 실제 그 메소드가 어떻게 동작하는지는 보여주지 않고 감추는 것입니다.


정보 은닉

프로그램의 세부 구현을 외부로 드러나지 않도록 감추는 것입니다. 실제로 접근제어자(private)을 사용하여 이루어집니다. 모듈 간의 결합도를 떨어뜨려 유연함과 유지보수성을 높입니다. 파이썬의 경우 속성이름 앞에 _(underscore)를 붙여서 private 속성이라는 의사표현은 가능합니다.


상속 (재사용 + 확장)

객체지향적 관점에서 상속이란 자식 클래스가 부모 클래스의 특성과 기능을 물려받는 것을 말합니다. 기능의 일부를 변경해야 할 경우 자식 클래스에서 상속받은 그 기능만을 수정하여 다시 정의합니다. 이러한 작업을 오버라이딩이라고 합니다. 상속은 캡슐화를 유지하면서도 클래스의 재사용이 용이하도록 해줍니다.


다형성

하나의 변수명, 함수명 등이 상황에 따라 다른 의미로 해석될 수 있는 것을 말합니다.

세부적으로 여러 경우가 있고 그 중 하나로 오버라이딩, 오버로딩(같은 이름의 함수를 여러 개 정의하고 매개변수에 따라 다르게 호출하게 하는 것), 덕타이핑을 생각하시면 됩니다.


원칙 5가지

객체지향프로그래밍에서 꼭 지켜야 할 5개의 원칙을 말합니다. 5개의 원칙의 앞글자를 따서 SOLID라고도 불립니다.


SRP(Single Responsibility Principle): 단일 책임 원칙

  • 모든 객체는 오직 하나의 책임을 가져야 합니다.
  • 다시 말해 객체는 오직 하나의 변경의 이유만을 가져야 하는 것입니다.
  • 예를 들어 계산기를 만들 때, 계산을 하는 책임과 GUI를 나타낸다는 책임은 서로 분리되어야 합니다. 계산기 클래스에 GUI를 나타내는 부분까지 있을 경우, 이는 SRP를 위반합니다.


OCP(Open-Closed Principle): 개방-폐쇄 원칙

  • 확장에 대해서는 개방되어 있어야 하지만, 수정에 대해서는 폐쇄되어야 합니다.
  • 예를 들어, 캐릭터를 생성한다고 할 때, 각각의 캐릭터가 움직임이 다를 경우 움직임의 패턴을 정의만 하고 구현을 하위 클래스로 보내 캐릭터 클래스의 수정은 막고 재정의만을 맡기게 됩니다.


LSP(Liskov Substitusion Principle): 리스코프 치환 법칙

  • 자식 클래스는 언제나 자신의 부모 클래스를 대체할 수 있습니다.
  • 즉, 부모 클래스가 들어갈 자리에 자식 클래스를 넣어도 잘 작동해야 한다는 것입니다.


ISP(Interface Segregation Principle): 인터페이스 분리 원칙

  • 클라이언트가 자신이 이용하지 않는 메소드에 의존하지 않아야 합니다.
  • 한 클래스는 자신이 사용하지 않는 인터페이스는 구현하지 말아야 합니다.
  • 예를 들어 전화, 웹서핑, 사진 촬영 등 다양한 기능이 있는 스마트폰을 정의할 경우, 각 기능은 독립된 인터페이스로 구현하여 서로에게 영향을 받지 않도록 설계해야 합니다. (참고: 인터페이스는 무엇을 할 수 있는지, 클래스는 어떤 분류인지에 대한 정의)
  • 시스템의 내부 의존성을 약화시켜 리팩토링, 수정, 재배포를 쉽게 할 수 있습니다.


DIP(Dependency Inversion Principle): 의존성 역전 법칙

  • 고수준의 클래스는 저수준의 클래스에 의존해서는 안됩니다.
  • 예를 들어 자동차가 스노우 타이어에 의존한다고 합시다. 이를 타이어로 변경하고 스노우 타이어가 타이어를 상속바도록 하면 본 원칙을 지킬 수 있습니다.


Functional Programming

데이터 처리를 수학적 함수의 계산으로 취급하고 상태와 가변 데이터를 멀리하는 프로그래밍 패러다임입니다.

함수형 프로그래밍이 객체 지향 프로그래밍과 완전히 대비되는 개넘은 아닙니다만, 다소 상반된 위치에 있습니다.

함수형 프로그래밍은 순수 함수를 작성하는 것, 그러니까 숨겨진 입력이나 출력을 최대한 제거하여 가능한한 우리 코드의 대부분이 단지 입력과 출력의 관계를 기술하게끔 하는 것을 말합니다.

함수형 언어는 여러분이 가능한한 부작용을 제거하고 그렇지 않은 곳에는 철저히 제어 할 수 있도록 적극적으로 도와주는 언어입니다.


Python

args, kwargs

args는 함수에 임의 갯수의 argument를 넘겨주기 위해 사용됩니다.

kwargs는 args와 마찬가지로 함수 선언에 사용되는 마법 변수지만 차이점은 함수에 kewworded argument를 dictionary 형태로 넘겨줄 수 있다는 것입니다.


How is dict implemented in Python?

파이썬의 dict는 해시테이블입니다.

먼저 해시함수는 dictionary보단 object에 따라 다르게 정의되어있습니다. 예를 들어 string의 해시함수는 약간 간단화시켜 아래와 같습니다.

def hash(string):
    x = string[0] << 7
    for chr in string[1:]:
        x = ((1000003 * x) ^ chr) & (1<<32)
    return x

튜플의 경우 아이템의 해시함수를 참고합니다.

해시테이블은 collision에 대응해야 합니다. dict에서는 chaining이 아닌 충돌이 일어날 때 정해진 칸을 더 나아간 후 다시 확인하는 open addressing이 사용됩니다.


Can class be used as a key of dictionary

class 객체는 dictionary의 key로 사용될 수 있으며 기본적으로 id() 값을 이용해 해싱됩니다.

새로운 해시함수를 이용하고 싶으면 class에 __hash__() 메소드가 정의되어 있어야 하며, 라이프사이클 동안 변하지 않아야 합니다. 또한 __hash__()의 리턴값들을 비교하여 boolean 값을 반환해주는 __eq__() 함수도 정의되어 있어야 합니다.


Mutable, Immutable

  • Mutable

Mutable은 변할 수 있다는 의미입니다. list, set, dict, byte array 등이 있습니다. mutable object는 함수의 parameter로 전달될 때 call-by-reference가 적용되며, 같은 값으로 x, y 두 변수를 선언하여도 서로 다른 메모리와 id를 가집니다. y를 y=x로 선언한다면 x와 y는 같은 메모리를 가르키게 됩니다.

  • Immutable

Immutable은 값이 변할 수 없다는 의미입니다. int인 x에 얼마든 값을 더하거나 뺄 수 있지 않느냐 혼동하실 수 있지만, Immutable object의 값이 변할 경우 새로운 메모리가 할당됩니다.

Immutable object에는 int, float, str, tuple 등이 있습니다. immutable object는 call-by-value가 적용되며 x, y 두 변수를 같은 값으로 선언하면 서로 같은 메모리와 id를 가집니다. y를 y=x로 선언하여도 서로 다른 메모리와 id를 가집니다.


Difference between method and function

함수와 메소드의 차이는, 함수는 이름으로 호출할 수 있는 코드 조각이지만, 메소드는 객체의 연결된 이름으로 불리며 메소드를 호출할 때 객체도 호출되는 것입니다. 또한 메소드는 해당 객체의 속성에 접근할 수 있습니다.


Is len() is function? or method?

len()은 Python built-in function으로 특정 object 내에 존재하는 메소드가 아닌 함수입니다.


Closure

클로져란 first-class function(객체로 취급되는 파이선의 모든 함) static scope의 name binding을 들고 다니는 녀석입니다.

def outer_func(tag):
    tag = tag

    def inner_func(txt):
        text = txt
        print '<{0}>{1}<{0}>'.format(tag, text)

    return inner_func


h1_func = outer_func('h1')
p_func = outer_func('p')

h1_func('h1태그의 안입니다.')
p_func('p태그의 안입니다.')

이렇게 함수(inner_func)를 객체로 h1_func, p_func에 전달하였을 시, 아래와 같이 기존의 tag 값이 이용되는 이유는 그 바인딩들을 __closure__가 들고 다니기 때문입니다.

$ python closure.py
<h1>h1태그의 안입니다.<h1>
<p>p태그의 안입니다.<p>


Decorator

decorator를 한마디로 얘기하자면, 대상 함수를 wrapping 하고, 이 wrapping 된 함수의 앞뒤에 추가적으로 꾸며질 구문 들을 정의해서 손쉽게 재사용 가능하게 해주는 것입니다.

아래와 같은 코드를 실행하면

# 얘가 데코레이터
def decorator(func):
    def decorator(*args, **kwargs):
        print("%s %s" % (func.__name__, "before"))
        result = func(*args, **kwargs)
        print("%s %s" % (func.__name__ , "after"))
        return result
    return decorator

# 함수에 데코레이터를 붙여준다.
@decorator
def func(x, y):
    print(x + y)
    return x + y

func(1,2)

이와 같은 결과가 나옵니다.

func before
3
func after

class로 데코레이터를 부르려면 class 내에 아래와 같은 방식으로 __call__ 함수를 정의하면 됩니다.

def __call__(self, *args, **kwargs):
    ...


Type casting

  • Explicit type casting

float(a)과 같이 타입(변수)로 가능합니다.

  • Implicit type casting

파이썬은 weak typed language이기 때문에 암묵적 형변환이 이루어집니다. -, + 연산자가 데이터형에 따라 덧셈이나 문자열 병합으로 오버로딩되며, -, +로 인해 서로 다른 데이터 타입 (3 + 3.2)가 연산될 경우 표현범위가 좁은 데이터 타입에서 넓은 데이터 타입으로 암묵적 형변환이 일어납니다.

print(3 + True)를 했을 시에 무려 4가 출력됩니다.


HTML

HTML (HyperText Mark-up Language)

웹 페이지의 모습을 기술하기 위한 규약으로, 프로그래밍 언어가 아닌 마크업 언어입니다. 마크업 언어란 문서가 화면에 표시되는 형식을 나타내거나 데이터의 논리적인 구조를 명시하기 위한 규칙들을 정의한 언어로, 데이터를 기술한 언어라는 점에서 프로그래밍 언어와는 차이가 있습니다.

현재 HTML5가 최신버전으로, 완전 표준화되어 있습니다.


What does a doctype do?

DOCTYPE이란 Document Type Definition의 약자로 흔히 더 줄여말해 DTD라고 부릅니다. HTML 문서를 읽을 때, 이 문서는 HTML 문서이고 어떤 버전을 사용했으며 그 버전에 맞는 방법으로 해석하라고 브라우저에게 알려주는 선언문입니다.

HTML5 이전의 HTML과 XHTML(XML 바탕으로 만들었던 HTML, 이젠 쓰이지 않습니다.)은 유효성 검사를 위한 선언문이 쓸데없이 길었던 반면, HTML5에서는 간단하게 이렇게만 적으면 됩니다.

<!DOCTYPE html>


What’s the difference between standards mode and quirks mode?

브라우저가 HTML 문서를 처리할 때, 위의 HTML DTD(<!DOCTYPE html>)이 있다면 표준모드가 설정되며, 그렇지 않으면 쿼크모드가 설정됩니다. 쿼크모드로 렌더링을 할 경우 이전 세대의 브라우저에 맞는 비표준적 방법의 CSS를 적용하며 이는 오래된 웹페이지들의 최신 버전의 브라우저에서 깨져 보이지 않으려는 목적을 가집니다.


meta tag

태그는 HTML 문서가 어떤 내용을 담고 있고, 문서의 키워드는 무엇이며, 누가 만들었는지 등의 문서 자체의 특성을 담고 있습니다.


<meta name="viewport" content="width=device-width">

viewport 란 컴퓨터나 휴대 단말기 등 장치에 Display 요소가 표현되는 영역을 말합니다. 모바일 웹의 경우 아이폰 사파리 브라우저에서 웹 페이지가 표시되는 영역으로 해석할 수 있습니다

위와 같은 메타태그로 설정하면 뷰포트의 가로 너비와 단말기의 가로너비가 동일하기 때문에 페이지의 배율 조정이 일어나지 않고 기기의 너비 만큼만 브라우저에 표시됩니다. (물론 좌/우 스크롤 기능으로 모든 컨텐츠를 탐색할 수 는 있습니다.)


How do you serve a page with content in multiple languages?

일단 lang이 있습니다. <html lang="kr">과 같이 문서의 기본 언어 속성을 선언하여 줍니다. 이는 screen read나 search engine에 관여합니다.

질문의 대한 답으로는 정말 다양한 방법이 있을 수 있습니다만, 제 블로그 같은 경우 아래와 같이 텍스트마다 yml 파일에 여러 언어에 따라 정리해놓고 lang 속성을 불러와 variable[lang]과 같은 방식으로 불러옵니다.

READMORE:
  en:      "Read more"
  kr:      "더 보기..."


What kind of things must you be wary of when design or developing for multilingual sites?

  • 사용자가 쉽게 국가/언어를 변경할 수 있도록 합니다.
  • 언어에 따라 텍스트의 길이가 달라질 수 있음에 주의합니다.
  • 문화에 따라 민감한 색상을 고려합니다.
  • 국가에 따라 날짜의 표현 방식이 다릅니다.


What are data- attributes good for?

JS 없이 HTML element에 non-standard attribute로써 새로운 데이터를 저장하기 위해 data- 속성을 사용합니다.

요즘 data-는 잘 쓰지 않고 라이브러리나 프레임워크의 데이터 바인딩을 통해 이 역할을 대신 수행합니다.


Describe the difference between a cookie, sessionStorage and localStorage

위 세 기술은 모두 클라이언트 측에서 데이터를 저장하는 key-value 저장소 매커니즘입니다.

cookie는 4KB의 크기를 가지고 뒤에 둘과 같은 web storage가 나오기 이전에 저장소 역할을 해왔습니다만, 일반적인 저장소라기보다 매 HTTP 요청에 첨부되어 클라이언트의 신상과 같은 역할을 하였습니다.

localStorage와 sessionStorage는 HTML5에 추가된 저장소입니다. 이 데이터는 HTTP 요청에 첨부되지 않으며 최대 5MB의 용량을 가집니다. 둘의 차이점으로 localStorage는 모든 윈도우끼리 공유되며 만료되지 않지만 sessionStorage는 한 탭 내에서만 공유되며 탭을 닫을 때 초기화됩니다.


Describe the difference between <script>, <script async> and <script defer>

  • <script>의 경우 렌더링 중단 후 script를 즉시 가져와 실행합니다.
  • <script async>는 렌더링을 멈추지 않고 비동기적으로 script를 가져옵니다. 그리고 실행이 가능할 때가 되면 렌더링을 멈추고 script를 실행합니다.
  • <script defer>는 async와 같이 렌더링을 멈추지 않고 script를 가져오며 렌더링이 끝난 이후에 script를 실행합니다.


What is progressive rendering?

프로그레시브 렌더링이란 콘텐츠를 가능한 빠르게 유저에게 보여주기 위한 기술로, HTTP response가 여러 번 일어날 때 브라우저는 모든 요청이 끝날 때까지 기다리지 않고 각각의 아이템을 차례대로 렌더링하게 합니다.


Why you would use a srcset attribute in an image tag? Explain the process the browser uses when evaluating the content of this attribute.

<img srcset="small.jpg 500w, medium.jpg 1000w, large.jpg 2000w" src="..." alt="">

위와 같이 기기 디스플레이의 너비에 따라 다른 이미지를 제공하기 위해 사용됩니다.


CSS

CSS (Cascading Style Sheet)

CSS는 HTML, XHTML, XML 같은 문서의 스타일을 꾸밀 때 사용하는 스타일 시트 언어입니다. 문서가 사용자에게 어떻게 보여질까를 기술합니다.


difference between css and sass

Sass는 css를 만들어주는 언어로 자바스크립트처럼 특정 속성(ex. color, margin, width … )의 값(ex. #000, 3px, 420px … )을 변수로 선언하여 필요한 곳에 선언된 변수를 적용할 수도 있고, 반복되는 코드를 한번의 선언으로 여러 곳에서 재사용할 수 있도록 해주는 등의 기능을 가졌습니다.

scss로 사용하면 css와 거의 같은 문법으로 Sass 기능을 사용할 수 있습니다.

변수 지원 뿐 아니라 함수 선언하듯이 @mixin으로 custom 속성을 정의하고 @include로 불러와 사용 가능합니다.


What’s the difference between “resetting” and “normalizing” CSS? Which would you choose, and why?

  • Resetting - 요소의 모든 기본 브라우저 스타일을 제거하기 위한 것입니다.
  • Normalize - 브라우저가 달라도 일관된 스타일을 유지하기 위한 것입니다.

reset.css를 이용해 초기화한 후에도 새로 스타일을 정의해줘야 하는데, 저는 normalize.css를 이용하고 결과를 확인하면서 수정합니다.


Describe Floats and how they work

Float는 CSS 위치지정 속성입니다. Float된 요소는 페이지의 흐름의 일부가 되며, 페이지의 흐름에서 제거되는 position: absolute 요소와 달리 다른 요소(예: 플로팅 요소 주위로 흐르는 텍스트)의 위치에 영향을 줍니다.

left, right, none의 값을 가지는데, 값에 따라 어떤 방향으로 element가 쌓일지를 결정합니다.


Describe z-index and how stacking context is formed

z-index는 어떤 element가 앞으로 나오고, 뒤에 나올지 배치 순서를 결정하는 속성입니다.

스택 컨텍스트란, z-index값이 루트가 아닌 해당 요소를 기준으로 설정됨을 말합니다. B가 A의 상단에 위치하는 경우 A의 하위 요소인 C는, C의 z-index가 B보다 더 높은 경우에도 B보다 위로 올 수 없습니다.


How would you approach fixing browser-specific styling issues?

reset.css를 사용하고, scss의 @mixin을 통해 vendor prefix가 필요한 속성의 경우 전부 포함시켜 따로 불러오게 합니다.


Have you ever used a grid system, and if so, what do you prefer?

bootstrap의 grid system을 써봤지만 상세한 조정이 힘들기에 flex-box를 이용한 반응형 레이아웃을 작성하는 것을 선호합니다.


Can you give an example of an @media property other than screen?

@media print {
    ...
}

인쇄를 위한 디자인을 명시해줍니다.


What are some of the “gotchas” for writing efficient CSS?

tag selector 보다는 class나 id selector를 사용하며, 페이지마다 전부 적시하기보다 재사용 가능한 style을 최대한 이용해주는 것이 좋습니다.


How would you implement a web design comp that uses non-standard fonts?

@font-face {
  font-family: 'SpoqaHanSans';
  font-weight: 200;
  src: url('./fonts/SpoqaHanSansThin.woff2') format('woff2'),
       url('./fonts/SpoqaHanSansThin.woff') format('woff'),
       url('./fonts/SpoqaHanSansThin.ttf') format('truetype');
}

body {font-family: 'SpoqaHanSans', 'serif';}


Describe pseudo-elements and discuss what they are used for

:before, :hover 등이 있으며 element 이전에 special symbol을 더하거나 첫 문자의 색을 바꾸거나, 마우스를 올려 놓을 시 스타일 변화 등을 위해 쓰입니다.


What is the CSS display property and can you give a few examples of its use?

  • none, flex, block, inline, inline-block, table, …


What’s the difference between inline and inline-block?

display:inline-block element들은 각자 width와 height를 가질 수 있으며 inline은 내용에 의존합니다.

inline-block은 모든 방향에서 margin과 padding이 가능하지만 inline은 좌우로만 가능합니다.


What’s the difference between a relative, fixed, absolute and statically positioned element?

  • static은 기본값입니다.
  • relative는 별도의 프로퍼티를 지정하지 않는 이상 static과 동일하지만 top, right, bottom, left를 지정하여 기본 위치와 다르게 위치가 조정됩니다.
  • fixed는 viewport에 상대적으로 위치가 지정되며 페이지가 스크롤되더라도 늘 같은 곳에 위치합니다.
  • absolute는 viewport가 아닌 부모 element에 상대적으로 위치가 지정됩니다.


How is responsive design different from adaptive design?

  • Responsive: 하나의 기본 레이아웃이 있고 스크린에 따라 반응하여 변형됩니다.
  • Adaptive: 모든 스크린에 대해 다른 레이아웃을 가집니다.


Javascript

ECMAScript

자바스크립트는 1990년대 Netscape 회사의 Brendan Eich 라는 사람에 의해 개발되었습니다. 바라스크립트가 잘되자, MS에서는 Jscript라는 언어를 개발해 IE에 탑재하였는데, 이 두 스크립트가 너무 제각각이라 표준이 필요하게 되었습니다.

이해당사자 간의 이름을 둘러싼 합의 끝에 ECMAScript라는 이름이 탄생하였습니다. 종종 마주치는 ES란 ECMAScript의 약자입니다.

Javascript는 언어이고, ECMAScript는 규격, 표준이 됩니다.


ES3 (1999)

흔히 알고 있는 그냥 Javascript입니다. 함수 단위의 스코프와, Hoisting, closure, prototype 등 기본적인 특징들을 가지고 있습니다.


ES4 (?)

이것저것 생겼다가 폐기되었다고 하네요.


ES5 (2009)

  • 배열에 forEach, map, filter, reduce, some, every와 같은 메소드가 생겼습니다. 이 메소드들로 불필요한 중복 코드를 줄이고 가독성을 높이게 되었습니다.
  • Object에 대한 Object.Create(), Object.defineProperty(), Object.freeze(), Object.assign() 등과 getter / setter 지원
  • strict 모드라는, 문법을 좀 더 깐깐하게 체크하는 모드가 생겼습니다.
  • JSON 지원


ES6 (2015)

  • let, const 키워드가 추가되었습니다. 기존의 변수는 함수 scope를 가진 var 키워드를 이용하여 선언하였습니다. 때문에 block scope를 가진 let과 const 키워드를 추가하였습니다. var과는 다르게 변수 재선언이 불가능하며 const는 재선언또한 불가능합니다.

  • arrow 문접을 지원합니다. 일반 함수의 자신을 호출하는 객체를 가리키는 dynamic this와 달리 arrows 함수는 코드의 상위 스코프(lexical scope)를 가리키는 lexical this를 가집니다.

  • class가 추가되었습니다. 기존의 prototype 기반으로 클래스를 만드는 것보다 명료하게 클래스를 만들 수 있게 되었습니다. 또한 클래스 선언은 함수 선언과 달리 Hoisting 되지 않습니다. 클래스를 사용하려면 사용하려는 위치 이전에 정의한 상태여야 합니다. constructor 객체의 생성과 초기화를 하는 특별한 메소드입니다. 클래스에서 constructor 이름을 갖는 메소드는 하나여야 합니다. 생성자 메소드에서 super 키워드를 통해 상위 클래스의 생성자 메소드를 호출 할 수 있습니다.

class Polygon {
    constructor(height, width) {
        this.height = height;
        this.width = width;
    }
}
 
class Square extends Polygon {
    constructor(length) {
        // length로 다각형의 넓이와 높이를 정의하기 위해 부모클래스의 생성자를 호출합니다.
        super(length, length);
        // Note: 파생 클래스에서, 'this'를 사용하기 전에는 반드시 super()를
        // 호출하여야 합니다. 그렇지 않을 경우 참조에러가 발생합니다.
        this.name = 'Square';
    }
 
    get area() {
        return this.height * this.width;
    }
 
    set area(value) {
        this.area = value;
    }
}
 
var test = new Square(4);
console.log(test.area);
  • 콜백 지옥에서 구원해 줄 Promise
  • Module Loader, Proxy, Reflect, Generator 등등… 많이 추가되었습니다. 설마 이런 것까지 상세히 물어보진 않겠죠?


ES7 (2016)

  • 제곱 연산자(**)가 등장하였습니다.
  • 배열.includes(찾을 요소, 시작 순서)가 추가되었습니다.
[1, 2, 3].includes(1); // true
[1, 2, 3].includes(1, 1); // false


ES8 (2017)

  • async, await이 추가되었습니다. 사실 promise가 어렵지 async, await의 기능만 따로 설명하라하면 별로 안 어려운 것 같긴 한데 아래에서 따로 풀어보겠습니다.
  • 객체의 심화된 메소드가 등장했습니다. Object.keys()에 대응되는 메소드인 Object.values(), Object.keys()와 Object.values()를 합쳐 놓은 Object.entries(), Object.getOwnPropertyDescriptor의 복수 형태인 Object.getOwnPropertDescriptors()로써 상속받지 않은 속성들의 설명만 보여줍니다.
  • 문자열 단순 편의기능으로 문자열 앞부분에 공백을 넣어 자리수를 맞춰주는 String.padStart(), 문자열 뒷부분에 공백을 넣어 자리수를 맞춰주는 String.padEnd()가 추가되었습니다.
  • 매개변수 마지막에 콤마를 붙이는걸 허용합니다.


ES9 (2018)

  • Rest, Spread 속성이 생겼습니다.

Rest Properties

const data = { a: 1, b: 2, c: 3, d: 4};
const { a, b, ...remain} = data;

console.log(a);    // 1
console.log(b);    // 2
console.log(remain)  //{ c:3, d:4 }

Spread Properties

const Arr1 = { a: 1, b: 2, c: 3, d: 4};
const newArr = { a: 2, e: 5, ...Arr1 };

console.log(newArr);   //{a: 1, e: 5, b: 2, c: 3, d: 4}

  • for-await-of로 비동기 iterable 객체를 반복하는 구문이 생겼습니다.

  • Promise에 finally()라는 메소드가 추가되었습니다. 실행결과에 상관없이 맨 마지막에 실행되는 메소드입니다.


Explain how this works in JavaScript

  1. 함수를 호출할 때 new 키워드를 사용하는 경우 함수 내부에 있는 this는 완전히 새로운 객체입니다.
  2. apply, call, bind 가 함수의 호출 / 작성에 사용되는 경우 함수 내의 this는 인수로 전달된 객체입니다.
  3. obj.method()와 같이 함수를 메소드로 호출하는 경우 this는 함수가 프로퍼티인 객체입니다.
  4. 함수가 자유함수로 호출되는 경우, 즉 위의 조건없이 호출되는 경우 this는 전역 객체입니다. 브라우저에서는 window 객체입니다.
  5. 위의 규칙 중 다수가 적용되면 더 높은 규칙이 적용되며 this 값을 설정합니다.
  6. 함수가 ES6의 arrow 문법을 이용할 경우 위의 규칙을 무시하고 생성된 시점의 주변 스코프의 this 값을 받습니다.


Call, Apply, Bind

  • call 메소드는 모든 함수에서 사용할 수 있으며, this를 특정값으로 지정할 수 있습니다. 함수를 호출하면서 call을 사용하고 this를 사용할 객체로 넘기면 해당 함수가 주어진 객체의 메소드인 것처럼 사용할 수 있습니다. call의 첫 번째 매개변수는 this로 사용할 값이고, 매개변수가 더 있으면 그 매개변수는 호출하는 함수로 전달됩니다.

  • aplly 메소드는 함수 매개변수를 처리하는 방법을 제외하면 call과 같습니다. call은 일반적은 함수와 마찬가지로 매개변수를 직접 받지만, apply는 매개변수를 배열로 받습니다.

  • bind 메소드는 함수의 this값을 영구히 바꿉니다.


Can you give an example of one of the ways that working with this has changed in ES6?

화살표 함수는 항상 익명 함수이며 this의 값을 현재 문맥에 바인딩 시킵니다. ES6 이전의 경우 자유 함수에서 this는 전역객체(window)를 가집니다.

아래의 예시는 화살표 함수가 지원되지 않는 ES5에서 this를 사용하기 위한 처리 예시입니다.

var _this = this
$('.btn').click(function(event){
  _this.sendData()
})

다음은 위 예시를 화살표 함수로 대체한 ES6 예시입니다.

$('.btn').click((event) => {
  this.sendData()
})


Prototype

자바스크립트에서 프로토타입은 두 가지의 의미를 혼용해서 사용합니다.

  1. __proto__: 사우이에서 무려 받은 객체의 프로토타입에 대한 정보 (prototype link)
  2. prototype: 자신의 프로토타입 객체, 다시 말해 하위로 물려줄 프로토타입의 정보 (prototype object)

단, 접근 시에는 object.prototype 이용하여 1번의 경우에 접근합니다.

function Animal() {};
Animal.prototype.bark = function () { console.log("왈왈!"); };
var dog = new Animal();
dog.bark(); // 왈왈!

dog.bark() 를 실행했을 때, dog 객체에는 bark라는 함수가 정의되어 있지 않지만, Animal 프로퍼티에 bark라는 함수가 정의되어 있고, “왈왈!”이라는 결과를 얻게 됩니다.

이는, 현재의 객체에서 어떠한 기능을 호툴하였는데, 찾지 못하면 상위로 올라가 찾게 되기 때문입니다. 이러한 개념(반복하여 상위로 올라가면서 찾는)을 프로토타입 체인(prototype chain)이라고 합니다.


Explain how prototypal inheritance works

자바스크립트는 ES6 이전까지 클래스가 존재하지 않았으며 prototype을 이용하여 클래스와 상속을 흉내냈습니다.

모든 자바스크립트 객체는 다른 객체에 대한 참조인 __proto__ 프로퍼티를 가지고 있습니다. 객체의 프로퍼티에 접근할 때 해당 객체에 해당 프로퍼티가 없으면 자바스크립트 엔진은 객체의 __proto__와 __proto__의 __proto__ 등을 보고 프로퍼티가 정의될 때까지 찾고 만약 객체의 프로퍼티에 접근할 때 해당 객체의 해당 프로퍼티가 없으면 프로토타입 체인 중 하나에 있거나 프로토타입 체인의 끝에 도달할 때까지 찾습니다.


What’s the difference between a variable that is: null, undefined or undeclared?

  • undeclared 는 이전에 var, let, const를 사용하여 생성되지 않은 식별자에 값을 할당할 때 생성됩니다. undeclared는 전역 변수로 정의되며 strict 모드에서는 ReferenceError가 throw 됩니다.
function foo() {
  x = 1; // strict 모드에서 ReferenceError를 발생시킵니다.
}

foo();
console.log(x); // 1
  • undefined 변수는 선언되었지만 값이 할당되지 않은 변수입니다. 또한 undefined 타입을 가집니다.
var foo;
console.log(foo); // undefined
console.log(foo === undefined); // true
console.log(typeof foo === 'undefined'); // true

console.log(foo == null); // true. 옳지않습니다. 확인하는 데 사용하지 마세요.

function bar() {}
var baz = bar();
console.log(baz); // undefined
  • null 변수는 null 값에 할당됩니다. 값을 나타내지 않지만 명시적으로 할당된다는 점에서 undefined와는 다릅니다.
var foo = null;
console.log(foo === null); // true

console.log(foo == undefined); // true. 옳지않습니다. 확인하는 데 사용하지 마세요.


What is a closure, and how/why would you use one?

closure란 함수 내에서 그 함수가 선언된 lexical scope를 담고 있습니다.


Can you describe the main difference between the Array.forEach() loop and Array.map() methods and why you would pick one versus the other?

.forEach(() => {})와 .map(() => {})의 주된 차이점은 .map()이 새로운 배열을 반환한다는 것입니다. 결과가 필요하지만 원본 배열을 변경하고 싶지 않으면 .map()이 확실한 선택입니다. 단순히 배열을 반복할 필요가 있다면, .forEach()가 좋은 선택입니다.


What’s a typical use case for anonymous functions?

한 번 사용되며 다른 곳에서는 사용할 필요가 없는 콜백으로 사용됩니다. 함수 본체를 찾기 위해 다른 곳을 찾아볼 필요 없이 코드를 호출하는 코드 바로 안에 핸들러가 정의되어 있으면 코드가 보다 독립적이고 읽기 쉽게 보일 것입니다.


What’s the difference between host objects and native objects?

  • 호스트 객체는 window, XMLHTTPRequest와 같이 런타임 환경(ex. 브라우저, Node.js)에 의해 제공됩니다.
  • 내장 객체는 String, Math, Function과 같이 Javascript 언어의 일부인 객체입니다.


Explain the difference between: function Person(){}, var person = Person(), and var person = new Person()?

  • Person(){}은 정상정인 함수 선언입니다.
  • var person = Person()은 생성자가 아니며 Person()을 함수로 호출합니다. 일반적으로 생성자는 아무것도 반환하지 않으므로 일반 함수처럼 생성자를 호출하면 undefined가 반환됩니다.
  • var person = new Person()은 Person.prototype을 상속받은 new 연산자를 사용하여 Person 객체의 인스턴스를 생성합니다.
function Person(name) {
  this.name = name;
}

var person = Person('John');
console.log(person); // undefined
console.log(person.name); // Uncaught TypeError: 정의되지 않은 'name' 프로퍼티를 읽을 수 없습니다

var person = new Person('John');
console.log(person); // Person { name: "John" }
console.log(person.name); // "john"


Explain the differences on the usage of foo between function foo() {} and var foo = function() {}

function foo() {...}는 함수 선언문입니다.

var foo = function() {...}는 함수 표현식으로 초기에 function() {...} ()(IIFE) 식으로 적어 foo에 리턴값을 할당하거나 이후에 foo()를 하는 방식으로 실행할 수 있습니다.


Can you explain what Function.call and Function.apply do? What’s the notable difference between the two?

.call과 .apply는 모두 함수를 호출하는데 사용되며 첫 번째 매개 변수는 함수 내에서 this의 값으로 사용됩니다. 단 .call은 쉼표로 구분된 인수를 매개 변수로 전달하지만 .apply는 배열을 매개 변수로 전달합니다.

function add(a, b) {
  return a + b;
}

console.log(add.call(null, 1, 2)); // 3
console.log(add.apply(null, [1, 2])); // 3


Explain Function.prototype.bind

bind() 메소드는 호출될 때 this가 제공된 값으로 설정됩니다.


Explain “hoisting”

객체의 선언을 최상위로 올려주는 것입니다. 할당은 올라가지 않습ㄴ니다.

function getX(){
  console.log(x);
  var x = 100;
  console.log(x);
}
getX();

위와 같은 코드는 다음과 같이 재구성되어 인터프릿됩니다.

function getX(){
  var x;
  console.log(x); // undefined
  x = 100;
  console.log(x); // 100
}
getX();

아래도 마찬가지입니다.

foo();
function foo(){
  console.log("hello");
};
> hello

foo();
var foo = function() {
  console.log("hello");
}
> Syntax Error


Describe event bubbling

element에서 이벤트가 감지되었을 때, 해당 element를 포함하고 있는 부모 element를 통해 최상위까지 이벤트가 전달되는 것을 버블링이라고 합니다.

<form onclick="alert('form')">FORM
  <div onclick="alert('div')">DIV
    <p onclick="alert('p')">P</p>
  </div>
</form>

위 코드를 실행하면 차례대로 p > div > form 창이 뜨게 됩니다. 대부분의 이벤트는 버블링이 일어나지만 예외적으로 focus는 버블링이 없습니다.


Describe event capturing

캡쳐링은 window부터 최초 이벤트가 발생한 자식 요소로 내려가는 과정을 말합니다.


What’s the difference between an “attribute” and a “property”?

attribute 속성은 HTML 마크업에 정의되지만 property 속성은 DOM에 정의됩니다. 차이점을 설명하기 위해 HTML에 <input type="text" value="Hello"> 텍스트 필드가 있다고 합시다.

const input = document.querySelector('input');
console.log(input.getAttribute('value')); // Hello
console.log(input.value); // Hello

여기서 input element는 type과 value 두 attribute를 가집니다. 브라우저가 엘리먼트를 파싱하면서 생성되는 HTMLInputElement 객체에는 accept, accessKey, align, alt 등 많은 property를 존재할 것입니다. 또한 엘리먼트의 attribute도 DOM에서의 객체의 property로 생성되지만 일대일 대응이 지켜지진 않습니다. 예를 들어 텍스트 필드에 “World!”를 추가하면 이렇게 될 것입니다.

console.log(input.getAttribute('value')); // Hello
console.log(input.value); // Hello World!


What is the difference between == and ===?

== 연산자는 타입 변환이 필요한 경우 암시적 타입 변환을 한 후에 동등한지 비교합니다.

=== 연산자는 타입 변환을 하지 않으므로 두 값의 타입이 다를 경우 단순히 false를 반환합니다.

1 == '1'; // true
1 == [1]; // true
1 == true; // true
0 == ''; // true
0 == '0'; // true
0 == false; // true


Explain the same-origin policy with regards to JavaScript

same-origin 정책은 자바스크립트가 도메인 경계를 넘어서 요청하는 것을 방지합니다. origin은 URI 체계, 호스트 이름 및 포트 번호의 조합으로 정의됩니다. 이 정책은 한 페이지의 악의적인 스크립트가 해당 페이지의 문서 객체 모델을 통해 다른 웹 페이지의 중요한 데이터에 접근하는 것을 방지합니다.


What is strict mode? What are some of the advantages/disadvantages of using it?

스트릭트 모드는 use strict를 사용하거나, doctype이 정의되어 있지 않을 때 사용됩니다. 이는 안전한 코딩을 위한 하나의 가이드라인으로 더 엄격한 오류 검사를 적용시킵니다.

ES6에서부터 strict mode가 default라고 합니다.


What are some of the advantages/disadvantages of writing JavaScript code in a language that compiles to JavaScript?

Javascript로 컴파일되는 언어로는 Coffeescript, Purescript, Typescript가 있습니다.

  • 장점으로는, 자바스크립트의 안티 패턴(피해야할 패턴)을 방지하는데 도움을 주는 경우가 있으며, 타입스크립트의 경우 정적 타입을 도입하여 시간 경과에 따라 유지 관리해야하는 대규모 프로젝트에서 장점을 드러낼 수 있습니다.

  • 단점으로 항상 자바스크립트로의 컴파일을 필요로 하며 최신 자바스크립트 표준에 뒤쳐지는 경우가 많습니다.


Explain the difference between mutable and immutable objects

Immutable 객체는 생성된 이후 값의 변경이 일어날 수 없습니다. Primitive 객체들과 같으며 Boolean, null, undefined, Number, String, Symbol이 있습니다.

Mutable 객체는 생성된 이후에도 값의 변경이 일어날 수 있는 객체입니다. Function, Array, Object가 있습니다.


What are the pros and cons of immutability?

장점

  • Call-by-value가 적용되므로 매개변수로 넘겨줄 때 방어적 카피를 만들 필요가 없습니다.
  • 같은 값으로 생성된 객체들을 위해 새로운 메모리가 사용되지 않습니다.

단점

  • 한 번의 메모리 할당 이후 값 변경이 아닌 작은 객체들을 여러 번 생성하는 것은 때론 비효율적입니다.


Explain the difference between synchronous and asynchronous functions

동기 함수는 다음 명령문이 실행되기 전에 명령문이 완료되어야 하지만, 비동기 함수는 일반적으로 비동기 기능이 호출된 이후 즉시 다음 줄로 실행이 진행됩니다.


What is event loop? what is the difference between call stack and task queue?

이벤트 루프는 콜 스택을 모니터링하며 태스크 큐에서 수행할 작업이 있는지 확인하는 단일 스레드 루프입니다. 콜 스택이 비어 있고, 태스크 큐에 콜백 함수가 있는 경우, 함수는 큐에서 제외되고 실행될 콜 스택으로 푸시됩니다.


What are the differences between ES6 class and ES5 function constructors?

// ES5 함수 생성자
function Person(name) {
  this.name = name;
}

// ES6 클래스
class Person {
  constructor(name) {
    this.name = name;
  }
}

생성자의 주요 차이점은 상속을 사용할 때 발생합니다. Person의 하위 클래스이면서 studentId 필드를 추가로 가지고 있는 Student 클래스를 만들고자 한다면, 이것이 우리가 위에 추가해서 해야 할 일입니다.

// ES5 함수 생성자
function Student(name, studentId) {
  // 수퍼 클래스의 생성자를 호출하여 수퍼 클래스에서 상속된 멤버를 초기화합니다.
  Person.call(this, name);

  // 서브 클래스의 멤버를 초기화합니다.
  this.studentId = studentId;
}

Student.prototype = Object.create(Person.prototype);
Student.prototype.constructor = Student;

// ES6 클래스
class Student extends Person {
  constructor(name, studentId) {
    super(name);
    this.studentId = studentId;
  }
}


Can you offer a use case for the new arrow => function syntax? How does this new syntax differ from other functions?

먼저 syntax가 기존보다 간단합니다. function을 적지 않아도 됩니다. 또한, arrow 문법을 이용할 경우 함수 내의 this는 생성된 시점의 주변 스코프의 this 값을 받습니다.


What advantage is there for using the arrow syntax for a method in a constructor?

가장 큰 장점은, constructor 내부의 메소드에 arrow 문법을 이용할 경우 this 값은 함수 생성 당시에 설정되고 변하지 않는다는 것입니다. 그러므로 생성자를 이용해 객체를 만들 경우 this는 항상 해당 객체에 의존합니다.

아래 코드를 예를 들어봅시다.

const Person = function(firstName) {
  this.firstName = firstName;
  this.sayName1 = function() { console.log(this.firstName); };
  this.sayName2 = () => { console.log(this.firstName); };
};

const john = new Person('John');
const dave = new Person('Dave');

john.sayName1(); // John
john.sayName2(); // John

// 기존 문법의 함수는 'this' 값이 변할 수 있지만
// arrow 문법을 이용한 함수는 변하지 않습니다.
john.sayName1.call(dave); // Dave ('this'가 dave 객체이기 때문입니다.)
john.sayName2.call(dave); // John

john.sayName1.apply(dave); // Dave
john.sayName2.apply(dave); // John

john.sayName1.bind(dave)(); // Dave
john.sayName2.bind(dave)(); // John

var sayNameFromWindow1 = john.sayName1;
sayNameFromWindow1(); // undefined ('this'가 window 객체입니다.)

var sayNameFromWindow2 = john.sayName2;
sayNameFromWindow2(); // John

여기서 알아야 할 것은 this가 기존 함수에서는 변한다는 것입니다. 함수가 여러 곳으로 passing되면서 호출될 경우 this를 계속 바인딩할 필요 없이 arrow 문법을 이용하여 초기에 정의한다면 편하게 이용할 수 있습니다.


What is the definition of a higher-order function?

고차 함수는 다른 함수를 매개 변수로 사용하여 일부 데이터에서 작동하거나, 결과로 함수를 반환하는 함수입니다. map, forEach, filter, reduce 등이 있습니다.


Can you give an example for destructuring an object or an array?

디스트럭쳐링은 ES6에서 사용할 수 있는 표현식으로 객체 또는 배열의 값을 추출하여 다른 변수에 배치하는 간결하고 편리한 방법을 제공합니다.

// 변수 할당.
const foo = ['one', 'two', 'three'];

const [one, two, three] = foo;
console.log(one); // "one"
console.log(two); // "two"
console.log(three); // "three"

// 변수 교환
let a = 1;
let b = 3;

[a, b] = [b, a];
console.log(a); // 3
console.log(b); // 1

// 변수 할당.
const o = { p: 42, q: true };
const { p, q } = o;

console.log(p); // 42
console.log(q); // true


Can you give an example of generating a string with ES6 Template Literals?

const person = { name: 'Tyler', age: 28 };
console.log(`Hi, my name is ${person.name} and I am ${person.age} years old!`);
// 'Hi, my name is Tyler and I am 28 years old!'


What are the benefits of using spread syntax and how is it different from rest syntax?

function putDookieInAnyArray(arr) {
  return [...arr, 'dookie'];
}

const { e, f, ...others } = {
  e: 1,
  f: 2,
  g: 3,
  h: 4,
}; // e: 1, f: 2, others: { g: 3, h: 4 }


static class members?

정적 클래스 멤버는 특정 인스턴스에 연결되지 않으며 어떤 인스턴스가 이를 참조하는지에 관계없이 동일한 값을 가집니다.


CallBack 콜백함수란

CallBack 함수란 이름 그대로 나중에 호출되는 함수를 말합니다. 콜백함수는 특정 시점에 도달할 경우 콜백 큐로 들어가며, 콜스택이 비게 될 때 이벤트 루프로 삽입되어 실행됩니다. 콜백함수를 사용하는 이유는, 자바스크립트에서 비동기적 프로그래밍을 할 수 있기 때문입니다.

ajax 코드를 잠시 살펴봅시다.

function getData() {
	var tableData;
	$.get('https://domain.com/products/1', function (response) {
		tableData = response;
	});
	return tableData;
}

console.log(getData()); // undefined

위 예시에서 function (response) {tableData = response}는 콜백함수로 get 요청에 대한 답변이 온 다음에 실행 가능해지므로 맨 아래의 출력함수는 undefined를 출력하게 됩니다. 이는 아래와 같이 출력함수또한 콜백함수로 이용하여 해결할 수 있습니다.

unction getData(callbackFunc) {
	$.get('https://domain.com/products/1', function (response) {
		callbackFunc(response); // 서버에서 받은 데이터 response를 callbackFunc() 함수에 넘겨줌
	});
}

getData(function (tableData) {
	console.log(tableData); // $.get()의 response 값이 tableData에 전달됨
});

비동기 처리 로직을 위해 콜백함수를 연속하여 사용할 경우 콜백지옥이라는 문제가 발생합니다.

$.get('url', function (response) {
	parseValue(response, function (id) {
		auth(id, function (result) {
			display(result, function (text) {
				console.log(text);
			});
		});
	});
});

웹 서비스를 개발하다 보면 서버에서 데이터를 받아와 화면에 표시하기까지 인코딩, 사용자 인증 등을 처리해야 하는 경우가 있습니다. 만약 이 모든 과정을 비동기로 처리해야 한다고 하면 위와 같이 콜백 안에 콜백을 계속 무는 형식으로 코딩을 하게 됩니다. 이러한 코드 구조는 가독성도 떨어지고 로직을 변경하기도 어렵습니다. 이와 같은 코드 구조를 콜백 지옥이라고 합니다.


promise

프로미스는 자바스크립트 비동기 처리에 사용되는 객체입니다.

function getData(callbackFunc) {
  $.get('url 주소/products/1', function (response) {
    callbackFunc(response); // 서버에서 받은 데이터 response를 callbackFunc() 함수에 넘겨줌
  });
}

getData(function (tableData) {
  console.log(tableData); // $.get()의 response 값이 tableData에 전달됨
});

위 ajax 요청 답변을 출력하는 예시에 콜백함수를 이용한 코드에 프로미스를 이용하면 아래와 같은 코드가 됩니다.

function getData(callback) {
  // new Promise() 추가
  return new Promise(function (resolve, reject) {
    $.get('url 주소/products/1', function (response) {
      // 데이터를 받으면 resolve() 호출
      resolve(response);
    });
  });
}

// getData()의 실행이 끝나면 호출되는 then()
getData().then(function (tableData) {
  // resolve()의 결과 값이 여기로 전달됨
  console.log(tableData); // $.get()의 reponse 값이 tableData에 전달됨
});

resolve 함수를 이용하여 then 이후 로직으로 값을 전달할 수 있습니다. then().catch를 이용하면 에러를 처리하는 코드또한 작성할 수 있습니다.

프로미스를 이용하면 이전에 보았던 콜백지옥을 아래와 같이 해결할 수 있습니다.

function getData() {
  return new Promise({
    // ...
  });
}

// then() 으로 여러 개의 프로미스를 연결한 형식
getData()
  .then(function (data) {
    // ...
  })
  .then(function () {
    // ...
  })
  .then(function () {
    // ...
  });


Async / Await

ES8에서 추가된 기능입니다.

먼저 async 함수 선언을 통해 비동기 함수를 정의합니다. 이렇게 생성된 함수는 AsyncFunction 객체를 반환합니다. AsyncFunction 객체는 해당 함수 내에 포함되어 있는 코드를 수행하는 비동기 함수를 나타냅니다.

이렇게 만들어진 비동기 함수가 호출 되면 이것은 프로미스를 반환합니다. 비동기 함수가 프로미스가 아닌 값을 반환하면, 프로미스는 자동으로 생성되며 해당함수로 부터 반환 받은 값을 이행합니다. 이 async 함수가 예외를 던지면 프로미스는 그 던져진 값과 함께 거절됩니다.

async 함수는 await 구문을 포함할 수 있는데 이를 이용하면 함수의 수행을 멈추고 프로미스의 이행 값이 넘어오기를 기다렸다가 async 함수의 수행을 계속해서 이어가다가 마지막에는 이행된 값을 반환할 수 있습니다.

async function loadData() {
    // `rp` is a request-promise function.
    var promise1 = rp('https://api.example.com/endpoint1');
    var promise2 = rp('https://api.example.com/endpoint2');
   
    // Currently, both requests are fired, concurrently and
    // now we'll have to wait for them to finish
    var response1 = await promise1;
    var response2 = await promise2;
    return response1 + ' ' + response2;
}
// Since, we're not in an `async function` anymore
// we have to use `then`.
loadData().then(() => console.log('Done'));

JS Coding questions

  • Make this work:
    • duplicate([1,2,3,4,5]); // [1,2,3,4,5,1,2,3,4,5]
  • 답:
function duplicate(arr) {
  return arr.concat(arr);
}

duplicate([1, 2, 3, 4, 5]); // [1,2,3,4,5,1,2,3,4,5]


  • Create a for loop that iterates up to 100 while outputting “fizz” at multiples of 3, “buzz” at multiples of 5 and “fizzbuzz” at multiples of 3 and 5

  • 답:

for (let i = 1; i <= 100; i++) {
  let f = i % 3 == 0,
    b = i % 5 == 0;
  console.log(f ? (b ? 'FizzBuzz' : 'Fizz') : b ? 'Buzz' : i);
}


  • What is the value of foo?
var foo = 10 + '20';
  • 답: "1020", 자바스크립트는 weak typed language이기 때문에 암시적 형변환이 일어나며 서로 다른 데이터 타입이 연산될 경우 표현범위가 좁은 데이터 타입에서 넓은 쪽으로 형변환이 일어나며 이 경우에는 String으로 변합니다.


  • What will be the output of the code below?
console.log(0.1 + 0.2);
console.log(0.1 + 0.2 === 0.3);
  • 답:
0.30000000000000004
false

decimal(십진수)을 binary(이진수)로 표현하는 경우 무한히 반복되는 수가 될 수 있어 근사값 표현이 되기 때문입니다. 예를 들어 십진수 0.1은 이진수로 표현하게 되면 0.00011001100110011… 이 되어 뒷부분의 0011이 무한히 반복되는 수가 됩니다. 이를 가수부영역에 표현하기 위해서는 반올림 처리를 해서 실제값과 가장 가까운 수로 표현할 수밖에 없게 됩니다.

이런 결과는 IEEE 754표준 중 double precision floating point(배정도 부동소수점)를 사용하여 계산된 결과를 정밀도를 맞추기 위해 나머지 수를 반올림하여 표현되었기 때문입니다.


  • How would you make this work?
add(2, 5); // 7
add(2)(5); // 7
  • 답:
var add = function(x, y) {
    return x + y;
}

var add = function(x) {
    return function(y) { return x + y; };
}


  • What value is returned from the following statement?
"i'm a lasagna hog".split("").reverse().join("");
  • 답:
"goh angasal a m'i"


  • What is the value of window.foo?
( window.foo || ( window.foo = "bar" ) );
  • 답: 만약 window에 foo 함수가 존재할 경우 그대로 넘어가며, 없을 경우 "bar"로 설정됩니다.


  • What is the outcome of the two alerts below?
var foo = "Hello";
(function() {
  var bar = " World";
  alert(foo + bar);
})();
alert(foo + bar);
  • 답:
first alert: "Hello World"
second alert: ReferenceError, bar not defined

var는 함수 스코프내에 정의되기 때문입니다.


  • What is the value of foo.length?
var foo = [];
foo.push(1);
foo.push(2);
  • 답:
2


  • What is the value of foo.x?
var foo = {n: 1};
var bar = foo;
foo.x = foo = {n: 2};
  • 답:

foo: {n: 2}

bar: {n: 1, x: {n: 2}}

위 코드는 아래와 같이 실행됩니다.

foo.x = (foo = {n: 2})

먼저 왼쪽의 foo.x를 참조하고 오른쪽 foo = {n: 2}를 실행한 후 {n: 2}를 반환하는데, foo는 재할당되었으므로 새로운 메모리의 객체가 되어있습니다. 그러므로 재할당 이전에 참조했던 foo.x는 bar만이 가지고 있는 프로퍼티인 상태가 됩니다.


  • What does the following code print?
console.log('one');
setTimeout(function() {
  console.log('two');
}, 0);
Promise.resolve().then(function() {
  console.log('three');
})
console.log('four');
  • 답:
"one"
"four"
"three"
"two"

setTimeout의 경우 Task Queue로 들어가고 프로미스 객체는 Micro Queue로 들어가는데, 이벤트 루프는 Micro Queue를 먼저 확인한다고 하네요.

Frontend

JSX

JSX는 React를 위해 태어난 새로운 자바스크립트 문법으로 과거 페이스북이 만들었던 PHP의 개량판 XHP에 그 기원을 두고 있습니다. React는 컴포넌트라는 개별적인 뷰 단위를 사용하는데, JSX는 컴포넌트를 HTML에 근접한 형태로 직관적인 조작이 가능하여 공식 웹사이트에서도 JSX의 사용을 권장하고 있습니다.


Virtual DOM

Virtual DOM은 리액트의 큰 특징 중 하나로, DOM의 성능 개선을 위해 등장하였습니다.

기존의 DOM은 변경이 일어날 경우, DOM 트리를 재구축하고, 렌더 트리 구축, 렌더 트리 배치, 렌더 트리 그리기, 표시의 과정을 통해 변경사항을 화면에 나타내었습니다. 문제는 렌더링 과정이 cost가 비싸고 DOM의 변경은 잦은 업데이트를 겪는 경우가 많기 때문에 브라우저의 속도에 타격을 준다는 것이었습니다.

Virtual DOM은 DOM의 복사본을 메모리 내에 저장하여 사용하며, 변경 사항을 가상의 위치에서 처리하고, 실제 DOM의 조작을 최소화하였습니다. 즉, DOM트리를 모방한 가벼운 자바스크립트 객체를 통해 직접 DOM을 핸들링 하지 않고 퍼포먼스를 향상시킵니다.

DOM 내 객체의 업데이트가 일어날 시, 직접 push와 같은 함수를 이용해 DOM에 변경내용을 적용할 수도 있지만, 저는 React의 Lifecycle의 규칙에 맞추어 유기적으로 해결되도록 하였었습니다.


Ajax

Ajax는 서버로부터 데이터를 가져와 전체 페이지를 새로 고치지 않고 일부만 로드할 수 있게 하는 기법입니다. 본래 Ajax는 비동기 요청을 보내는 데 필요한 기술, 즉 Asynchoronous Javascript And XML의 약자였으나 이후 브라우저 내에서 비동기 기능을 제공하는 모든 기법을 통칭하게 되었습니다.

페이지의 일부분에만 새로운 콘텐츠를 로드하는 기능은 사용자의 전체적인 사용 경험을 향상시킬 수 있습니다. 이는 페이지의 일부만 수정하게 되면 사용자가 전체 페이지가 로드될 때까지 기다릴 필요가 없기 때문이며, 이 기법은 소위 단일 페이지 웹 애플리케이션(SPA:Sinlge Page Application, 브라우저에서 실행되기는 하지만 마치 소프트웅어 애필리케이션 같은 느낌을 주는 웹 기반 도구)이 등장하는 계기가 되었습니다.

단 레이아웃이 너무 복잡한 사이트는 웹 브라우저가 렌더링하는 데 힘겨워할 수도 있습니다. 또는 아주 신속하게 첫 화면을 보여 줄 필요가 있는 경우에도 Ajax는 최소 두 번의 데이터 요청(일반적으로 4회 이상. HTML, CSS, JS 로딩 후 Ajax call 1회)을 해야 한다는 문제가 있습니다.


MVC Pattern

MVC 는 Model, View, Controller의 약자입니다. 하나의 애플리케이션, 프로젝트를 구성할 때 그 구성요소를 세가지의 역할로 구분한 패턴입니다. 비지니스 처리 로직과 사용자 인터페이스 요소를 분리시켜 서로 영향없이 개발 하기 수월하다는 장점이 있습니다.

  • Model은 무엇을 할지 정의합니다. 비지니스 로직에서의 알고리즘, 데이터 등의 기능을 처합니다.
  • Controller는 어떻게 할지를 정의합니다. 화면의 처리기능과 Model과 View를 연결시켜주는 연활을 하지요.
  • View는 화면을 보여주는 역활을 하지요. 웹이라면 웹페이지, 모바일이라면 어플의 화면의 보여지는 부분입니다.


How browsers work?

브라우저의 주요 기능은 사용자가 선택한 자원을 서버에 요청하고 브라우저에 표시하는 것입니다. 자원은 보통 HTML 문서지만 PDF나 이미지, 또는 다른 형태일 수도 있습니다. 자원의 주소는 URI(Uniform Resource Identifier)에 의해 정해집니다.

브라우저가 요청을 통해 얻은 리소스를 사용자에게 보여주는 작업은 아래와 같은 과정을 갖습니다.

먼저 HTML의 파싱과 DOM 트리 구축이 진행됩니다.

그와중 <link rel="stylesheet" type="text/css" media="screen" href="main.css" />와 같이 CSS 파일의 링크를 만나면 main.css를 향한 요청을 보내고 CSSOM (CSS Object Model) 트리를 구축합니다. 이후 둘을 결합하여 렌더 트리를 구축합니다.

HTML과 CSS 모두 클라이언트로 보내지고 트리가 완성이 되어야 렌더링이 되므로 둘 모두 render-blocking resource라 할 수 있지만, Javascript 또한 그렇습니다. HTML 파서가 script 태그를 마주칠 때마다 DOM 구축 프로세스는 멈추게 되죠. 그러므로 script는 </body> 직전에 위치시켜 DOM tree의 구축을 방해하지 않도록 합니다.


Cross Browsing

Croos Browsing이란 적어도 표준 웹기술을 채용하여 다른 기종 혹은 플랫폼에 따라 달리 구현되는 기술을 비슷하게 만듦과 동시에 어느 한쪽에 최적화되어 치우지지 않도록 공통 요소를 사용하여 웹 페이지를 제작하는 기법을 말하는 것입니다.

필요한 방법으로는 reset.css, vendor prefix, Babel 등이 있습니다.


Webpack

웹팩은 모듈 번들러(Module Bundler)입니다.

웹팩은 프로젝트의 구조를 분석하고 자바스크립트 모듈을 비롯한 관련 리소스들을 찾은 다음 이를 브라우저에서 이용할 수 있는 번들로 묶고 패킹합니다.


Babel

Babel은 ES6+ 코드를 ES5 이하의 버전으로 트랜스파일링합니다.


RxJs

RxJS는 Observable를 사용하여 비동기 및 이벤트 기반 프로그램을 작성하기 위한 라이브러리입니다. 앵귤러를 사용하였을 때 잠시 써봤는데 잘 기억은 나지 않습니다.


React vs Vue.js

분명하게 어느 쪽이 더 낫다고 판단할 순 없으며 서로의 매니아층이 확실하지만, 저는 리액트와 JSX의 컴포턴트 작성 방식이 더 직관적으로 다가왔기 때문에 리액트를 택하였습니다.


Code splitting

우리가 자바스크립트로 애플리케이션을 개발하게 되면, 기본적으로는 하나의 파일에 모든 로직들이 들어가게 됩니다. 그럼, 프로젝트의 규모가 커질수록 자바스크립트 파일 용량도 커집니다. 용량이 커지면, 인터넷이 느린 환경에서는 페이지 로딩속도도 느려질 것입니다.

코드 스플리팅을 하게 되면, 지금 당장 필요한 코드가 아니라면 따로 분리시켜서, 나중에 필요할때 불러와서 사용 할 수 있습니다. 이를 통하여, 페이지의 로딩 속도를 개선 할 수 있죠.


참고

© 김형록 2018 RSS

찾기