크래프톤 정글 2주차 TWIL..

this week i learned..

2주차 학습 내용

• 컴퓨터 시스템 책(Compouter Systems - A Programmer's Perspective / CSAPP) 1.5 - 1.7
• 백준 문제 풀이 + 관련 이론 학습
  • 스택
  • 큐
  • 우선순위 큐

---

CSAPP 1.5 - 1.7

캐시가 중요하다

• 시스템이 정보를 한 곳에서 다른 곳으로 이동시키는 데 많은 시간이 든다.
  • 하드디스크에서 메인 메모리로, 그리고 메인 메모리에서 프로세서로..
• 이러한 복사 과정들은 프로그램의 "실제 작업"을 느리게 하는 오버헤드(overhead)가 된다.
  • 오버헤드: 어떤 처리를 함에 있어서, 간접적인 원인으로 인해 추가되는 처리 시간 및 메모리
• 큰 저장장치들은 작은 저장장치들보다 느린 속도를 갖는다. 그리고 빠른 장치들은 느린 장치들보다 만드는 데 더 많은 비용이 든다. (trade-off)
• 캐시 메모리: 프로세서가 단기간에 필요로 할 가능성이 높은 정보를 임시 저장할 목적으로 사용

저장장치들은 계층구조를 이룬다

• 메모리 계층 구조
  • 저장장치들은 아래 그림과 같은 메모리 계층구조를 이루는데, 계층구조의 위에서 아래로 갈수록 저장장치들은 더 느리고/더 크고/더 저렴해진다.
  • 한 레벨의 저장장치가 다음 하위레벨 저장장치의 캐시 역할을 한다.

출처: 위키백과 - 메모리 계층 구조

운영체제는 하드웨어를 관리한다

• 운영체제: 하드웨어/소프트웨어 사이에 위치한 소프트웨어 계층
• 프로그램은 메모리에 직접 접근하지 않는다. 대신 운영체제가 제공하는 서비스를 활용한다.
  
  • 응용프로그램이 하드웨어를 제어하려면 운영체제를 통해서 해야 한다.
• 운영체제의 두 가지 목적
  • 첫 번째, 응용프로그램들이 하드웨어를 잘못 사용하는 것을 막기 위함.
  • 두 번째, 응용프로그램들이 하드웨어 장치들을 비교적 단순한 메커니즘을 사용하여 조작할 수 있도록 하기 위함.
• 운영체제는 이를 위해 추상화를 사용한다.
  • 입출력장치의 추상화 → 파일
  • 메인 메모리, 디스크 입출력 장치의 추상화 → 가상메모리
  • 프로세서, 메인 메모리, 입출력장치 모두의 추상화 → 프로세스

자료구조, 알고리즘

스택, 큐

• 스택(stack)
  • 후입선출(LIFO)의 특징을 가진다. → 데이터가 입력 순서의 역순으로 처리되어야 할 때 사용
  • 함수의 콜 스택(function call stack)이 대표적인 사례
    • 예를 들어 DFS를 구현할 때, 배열로 스택을 구현하는 방식으로 코드를 짤 수도 있지만 재귀 함수를 사용하여 아예 함수 콜 스택 자체를 이용하는 방식도 가능하다.
  • 스택의 연산: push, pop, peek, empty
    • push: 데이터를 스택에 넣는 것을 의미하는데, 이때 스택의 크기 이상으로 데이터를 push하게 되면 stack overflow가 발생
    • pop: 데이터를 삭제하는 연산과 해당 데이터를 반환 받는 연산으로 이루어져 있음. 스택에 있던 데이터보다 더 많이 pop을 하게 될 경우 underflow가 발생
    • peek: 데이터를 삭제하지 않고 확인만 하는 연산
    • empty: 스택이 비어있는지 확인
• 큐(queue)
  • 선입선출(FIFO)의 특징을 가진다. → 입력된 데이터가 순서대로 처리되어야 할 때 사용
  • 예를 들어 네트워크 요청은 요청 큐에 들어온 순서대로 처리가 된다.
  • 큐에서 다음에 값이 들어올 인덱스를 리어(rear)라고 하고, 이제 반환될 값의 인덱스를 프론트(front)라고 한다.
  • 큐의 연산: enqueue, dequeue, peek
    • enqueue: 데이터를 리어로 삽입함. enqueue가 되는 순간 리어는 다음 인덱스로 이동
    • dequeue: 데이터를 프론트에서 꺼냄. dequeue가 되는 순간 프론트는 다음 인덱스로 이동
    • peek: 프론트에 있는 자료를 반환하되 dequeue와 달리 삭제는 하지 않음.

힙 정렬

• 힙 정렬은 힙(max heap)에서 최댓값은 루트에 위치한다는 힙의 특징을 이용하여 정렬하는 알고리즘이다.
• 힙 정렬을 할 때 다음의 작업을 반복:
  • 힙에서 루트(최댓값)을 꺼낸다.
  • 루트 이외의 부분을 힙으로 만든다. → heapify
• 이러한 반복 작업을 거치면서 꺼냈던 값들을 나열하면 정렬이 끝난 배열이 완성된다.
• 힙 정렬은 선택 정렬(selection sort)을 응용한 알고리즘이다.

선택 정렬

• 0번째 원소부터 주목한다.
• 배열을 순회하며, 최소값을 갖는 원소를 찾는다.
• 최소값 원소와, 주목 중인 원소를 swap 한다.
• 이제 1번째 원소에 주목하여 같은 작업을 반복한다. n번째 원소까지 동일하게 진행된다.

힙(heap)

• 힙: 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전 이진 트리
  • 부모 값은 자식 값보다 항상 작아도 됨.
  • 항상 크든 작든, 부모 값과 자식 값의 대소 관계가 일정하기만 하면 됨.
  • 완전 이진 트리
    • 우선 트리🌲란, 각 원소를 의미하는 노드(node)들이 연결된 계층 구조다.
    • 트리의 가장 윗부분에 위치한 루트(root)는 부모가 없는 노드다.
    • 노드 간의 관계
      • 노드 간 상하 관계: 부모 노드(parent node)-자식 노드(child node)
      • 부모가 같은 자식 노드 간의 관계: 형제 노드(sibling node)
    • 완전 이진 트리는 트리의 한 종류인데, 이름에서 알 수 있듯이 완전 이진 상태라는 특징이 있다.
      • 완전: 부모는 왼쪽 자식부터 추가하여 모양을 유지한다.
      • 이진: 부모가 가질 수 있는 자식의 최대 개수는 2개 뿐이다.
• 힙에선 부모의 값이 자식의 값보다 항상 큰 관계가 성립하기 때문에, 힙의 가장 위쪽에 위치한 루트가 힙에서 가장 큰 값이 된다.
• 힙에 대해 알기 전에 ADT인 우선순위 큐에 대해 알아야 한다.
  • ADT(Abstract Data Type, 추상 자료형)
    • 자료 구조의 기반으로, 값과 연산의 집합으로 정의되는 논리적 행동을 가지는 object class
    • 추상 ↔️ 구상(concrete)
    • ADT vs 자료 구조: 가장 큰 차이점은 바로 구현 여부
      • 구현 명세가 있으면 자료 구조, 없으면 추상 자료형
      • 이미 구현이 되어있는 것은 자료 구조
  • 우선순위 큐(priority queue)
    • 일반적인 큐와 같이 FIFO에 따라 동작하는 것이 아니라, 일정한 규칙에 맞춰 동작하는 큐
    • 인큐할 때 데이터에 우선순위를 부여하여 추가하며, 디큐할 때 우선순위가 높은 데이터를 꺼낸다.
• 힙은 일반적으로 이진 트리(binary tree)로 구현된다.
• max heap(부모 값 > 자식 값)은 가장 큰 숫자를 먼저 빼주는 반면, min heap(부모 값 < 자식 값)은 가장 작은 값을 먼저 빼준다.
• 시간복잡도
  • 최대값(최소값) 접근: O(1)
    • 최대값(최소값)은 이진 트리의 루트에 위치해있기 때문
  • 새로운 노드를 추가하게 될 경우: O(logN)
    • 기존 노드들과 크기를 비교하면서 swap 작업을 진행
  • 루트 삭제하며 힙 재구성: O(logN)
• 완전 이진 트리의 성질을 이용해서 트리가 아닌 배열로도 힙을 표현할 수 있다.
  • 힙의 원소를 어떤 배열(a)에 저장하는 방법은 다음과 같다. :
    
    1. 루트를 a[0]에 저장한다.
    2. 한 단계 아래로 내려가되, 왼쪽 노드부터 본다. 왼쪽 노드의 값을 a[1]에 저장한다. 그 다음에 같은 단계의 오른쪽 노드를 본다. 인덱스를 1 증가시킨 a[2]에 오른쪽 노드의 값을 저장한다.
    3. 인덱스 값을 1씩 증가시키며, 왼쪽부터 오른쪽으로, 한 단계 완료되면 그 다음 단계의 왼쪽 노드로 가면서 해당 노드의 값을 배열에 저장하는 작업을 반복한다.
  • 이러한 순서에 따라 힙을 배열로 나타나게 되면 어떤 원소 a[i]의 인덱스 i와 그 부모 인덱스 및 자식 인덱스 간에는 다음과 같은 관계가 성립하게 된다. :
    • 부모 인덱스: (i - 1) // 2
    • 왼쪽 자식 인덱스: (i * 2) + 1
    • 오른쪽 자식 인덱스: (i * 2) + 2 → 즉, 왼쪽 자식 인덱스 + 1
• 힙에서 부모 자식 관계는 일정하지만, 형제 사이의 대소 관계는 일정하지 않다.
  • 이처럼 힙은 형제 대소 관계가 정해져 있지 않으므로, 부분 순서 트리(partial ordered tree)라고도 한다.

문제 접근 방식

• 2805. 나무 자르기 🌳 - 0부터 가장 높은 나무 높이까지 1씩 증가하며 적절한 높이를 찾아가는 방법도 있지만 이러한 방법은 O(n^2)의 시간 복잡도를 갖기 때문에 이진 탐색을 사용하는 편이 좋다.
• 2470. 두 용액 🧑‍🔬 - 정렬되어 있는 수열에서 특정 합을 구하는 문제를 보면 투 포인터를 떠올리자.
• 11053. 가장 긴 증가하는 부분 수열 - LIS(Longest Increasing Subsequence) 유형은 흔한 유형이다. DP로 해결하는 게 좋다.
  • dp[i]는 A[i]까지의 부분 수열 길이

---

2주차 소회

코로나 이슈로 인해 공부도 거의 못하고 문제도 문제꾸러미 중에서 절반 정도 밖에 못 풀었다. (심지어 twil도 이제야 올림;;)

이틀은 정말 앉아있는 것도 힘들 정도로 아파서 어쩔 수 없었다해도, 격리 3일차부터는 그 정도는 아니었지만서도 어쩐지 뇌가 고장난 것처럼 도저히 집중이 되지 않았다. 그 상태로 기숙사 방에서 혼자 공부하려고 하니까 자꾸 쉬거나 딴 짓을 하게 됐다.. (다나카 영상 진짜 많이 봤다..;) 그리고 팀원분과 비대면으로 협업을 진행하기가 마땅치 않아서 거의 혼자 학습을 했던 것도 상당히 아쉽고 팀원분께 죄송했다 ㅠ

그렇지만..! 한편으론 5개월 중 그나마 제일 덜 바쁜 1~4주차 중에 미리 걸려서 오히려 다행인 것 같기도 하고..!? 🤭