Ryan의 Devlog

Memory 관련 용어

• 논리적 주소(Logical Address):
  • 프로세스가 메모리에 적재되기 위한 독자적인 주소 공간인 논리적 주소가 생성 됩니다.
  • 논리적 주소는 각 프로세스마다 독립적으로 할당 되며 0번지 부터 시작됩니다.
• 물리적 주소(Pysical address)
  • 물리적으로 프로세스가 실제 메모리에 적재되는 위치를 말합니다.
• 주소 바인딩(address binding)
  • CPU가 기계어 명령을 수행하기 위해 프로세스의 논리적 주소가 실제 물리적 메모리의 어느 위치에 매핑되는지 확인하는 과정
• 메모리 단편화
  • 내부 단편화 : 프로세스가 필요한 공간 보다 더 많은 메모리가 할당되어 메모리가 낭비되는 상황
  • 외부 단편화 : 메모리 중간중간에 사용하지 않는 공간이 생겨서 더이상 사용할 수 없는 상황

Q1. Paging이란 무엇인가요?

paging 기법은 process의 메모리 공간을 동일한 크기의 page 단위로 나누어 물리적 메모리의 서로 다른 위치에 page들을 저장하는 메모리 관리 기법입니다. paging 기법에서는 물리적 메모리를 page와 같은 크기의 frame으로 미리 나누어둡니다.

• Paging 기법에서는 주소 바인딩을 위해 모든 프로세스가 각각의 주소 변환을 위한 page table을 갖습니다.

꼬리 질문 1 : Paging 기법 사용시 발생할 수 있는 메모리 단편화 문제에 대해 설명하시오.

paging기법에서는 process의 논리적 주소 공간과 물리적 메모리가 같은 크기의 page 단위로 나누어지기 때문에 외부 단편화 문제는 발생하지 않습니다.
하지만 process 주소 공간의 크기가 page 크기의 배수라는 보장이 없기 때문에 프로세스의 주소 공간 중 마지막에 위치한 page에서는 내부 단편화 문제가 발생할 가능성이 있습니다.

Q2. Segmentation에 대해서 설명해주세요.

Segmentation 기법은 process가 할당받은 메모리 공간을 논리적 의미 단위(segment)로 나누어 연속되지 않는 물리 메모리 공간에 할당될 수 있도록 하는 메모리 관리 기법입니다.
일반적으로 메모리 영역을 Code, Data, Heap, Stack 등의 기능 단위로 segment를 정의하는 경우가 많습니다.
Segmentation 기법에서는 주소 바인딩을 위해 모든 프로세스가 각각의 주소 변환을 위한 segmentation table을 갖습니다.

꼬리 질문 1 : Segmentation의 메모리 단편화 문제에 대해 설명하시오.

Segmentation 기법에서는 Segment의 크기만큼 메모리를 할당하므로 내부 단편화 문제는 발생하지 않습니다.
하지만 서로 다른 크기의 segment들이 메모리에 적재되고 제거되는 일이 반복되면 외부 단편화 문제가 발생할 가능성이 있습니다.

꼬리 질문 2 : Segmentation과 paging의 차이는 뭔가요?

Paging은 일정한 크기의 단위로 나누어 할당을 하는데 반해
Segmentation 기법에서는 code, data, heap, stack등의 기능단위로 물리 메모리를 할당하는 기법입니다.
paging의 경우 내부 단편화의 문제가 발생할 수 있는데, 이에 반해
segmentation은 외부 단편화의 문제가 발생할 수 있습니다.

꼬리 질문 3 : Paged segmentation 기법에 대해 설명하시오.

paged sementation이란 segmentation을 기본으로 하되 이를 다시 동일한 크기의 page로 나누어 물리 메모리에 할당하는 메모리 관리 기법입니다. 즉, 프로그램을 의미하는 단위의 segment로 나누고 개별 segment의 크기를 page의 배수가 되도록 하는 방법입니다.

이를 통해 segmentation 기법에서 발생하는 외부 단편화 문제를 해결함과 동시에 segment 단위로 processrksdml rhddbsk process내의 접근 권한 보호가 이루어지도록 하여 paging 기법의 단점을 해결 합니다.

Q3. 가상 메모리에 대해서 설명해주세요

가상메모리(virtual memory)는 실제의 물리 메모리 개념과 개발자 입장의 논리 메모리 개념을 분리한 것입니다. 이렇게 함으로써 개발자가 메모리 크기에 관련한 문제를 염려할 필요 없이 쉽게 프로그램을 작성할 수 있게 해줍니다.
운영체제는 가상 메모리 기법을 통해 프로그램의 논리적 주소 영역에서 필요한 부분만 물리적 메모리에 적재하고 직접적으로 필요하지 않은 메모리 공간은 디스크(Swap 영역)에 저장하게 됩니다.

요구 페이징(demend paging)

당장 사용될 주소 공간을 page단위로 메모리에 적재하는 방법을 요구 페이징(demend paging)이라고 합니다. 요구 페이징 기법에서는 특정 page에 대해 cpu의 요청이 들어온 후에 해당 page를 메모리에 적재합니다. 당장 실행에 필요한 page만을 메모리에 적재하기 때문에 메모리 사용량이 감소하고 프로세스 전체를 메모리에 적재하는 입출력 오버헤드도 감소하는 장점이 있습니다.

요구 페이징 기법에서는 유효/무효 비트(valid/invalid bit)를 두어 page가 메모리에 존재하는지 표시하게 됩니다.

Page Fault

CPU가 무효 비트로 표시된 page에 엑세스하는 상황을 page fault라고 합니다.

CPU가 무효 page에 접근하면 주소 변환을 담당하는 하드웨어인 MMU가 page fault trap을 발생시키게 되고 다음과 같은 순서로 page fault를 처리하게 됩니다.

1. CPU가 페이지 N을 참조

2. Page table에서 페이지 N이 무효 상태임을 확인

3. MMU에서 Page fault trap이 발생

4. 디스크에서 페이지 N을 빈프레임에 적재하고 page table을 업데이트합니다. (invalid -> valid)

Page 교체 알고리즘

page fault가 발생하면 요청된 page를 디스크에서 메모리로 가져옵니다. 이때 물리적 메모리에 공간이 부족할 수 있습니다. 그럴 경우에는 메모리에 올라와있는 page를 디스크로 옮겨서 메모리 공간을 확보해야 합니다. 이것을 페이지 교체(page replacement)라고 하고 어떤 page를 교체할 것이냐를 결정하는 알고리즘이 page교체 알고리즘입니다.

Session/Cookie 방식

HTTP는 비연결성 및 무상태성이라는 특징을 가지고 있기 때문에 요청에 대한 응답을 처리하게 되면 연결을 끊어 버린다. 따라서 클라이언트에 대한 이전의 상태 정보 및 현재 통신의 상태가 남아있지 않는다.
이를 보완하기 위해 Cookie와 Session을 사용한다.

Cookie

쿠키는 일종의 서버와 클라이언트가 대화하기 위한 수단.

• 브라우저가 서버와 연결이 되었을 때 브라우저에서 자동적으로 쿠키를 생성하고, response 할 때 쿠키를 담아서 보낸다.
• 서버는 요청 해더의 set-cookie 속성에 클라이언트 측에 저장하고 싶은 정보를 담아 보낸다.
• 특정 호스트에서 생성된 쿠키는 이후 모든 요청마다 서버로 전송됨
• 쿠키에 담긴 데이터는 브라우저에서 관리됨.
• 쿠키는 Key-Value 형식의 문자열 덩어리
• 이름, 값, 만료 날짜, 경로 정보 등 다양한 정보를 가짐

단점

1. 서버에 계속적으로 요청을 보낼 시, 쿠키의 값을 그대로 보내기 때문에 조작 및 유출의 위험성이 높음.

2. 용량 제한이 있어 , 많은 데이터 정보를 담을 수 없다.

3. 쿠키의 사이즈가 커질 수록, 네트워크 성능 부하가 심해진다.

Session

서버는 요청을 처리한 후에는 클라이언트의 연결 상태를 확인하지 못하기 때문에

서버와 클라이언트의 연결이 활성화된 상태인지 확인하기 위해 사용

Cookie 인증의 보안적인 이슈를 보완하기 위해, Session 인증 방식은 사용자의 민감 인증 정보를 브라우저가 아닌 서버에 저장 및 관리한다. (서버 메모리 혹은 로컬 파일 및 데이터베이스에 저장함.)

세션 객체의 구성

• 세션 id
• Value(Map)
  • 세션 생성시간
  • 접근 시간
  • user가 저장한 속성
  • etc.

단점

1. 세션 id 자체는 유의미한 개인정보를 담고 있지 않으나,해커가 세션 id 자체를 탈취하여 사용자인척 위장할수 있다. (서버에서 ip 특정을 통해 해결가능함.)

2. 세션 저장소를 따로 이용하기에 요청이 많아지면 많아질수록 서버 부하가 심해진다.

Cookie/Session 인증 (Stateful)

• 클라이언트가 서버와 통신을 시작하면 서버는 해당 클라이언트에 대해 유일한 값인 세션 id를 부여, 세션 스토리지에 세션 정보를 저장함.
• 클라이언트는 이 세션id를 쿠키를 통해 기억함.
• 이후 클라이언트가 어떤 요청을 보낼 때마다 헤더의 cookie에 세션 id를 담아서 전송함.
• 서버는 클라이언트가 보낸 요청의 쿠키에 담긴 세션 id와 세션 스토리지에 담긴 세션 id를 대조해 인증 상태를 판단함.
• (즉, 세션과 쿠키는 완전히 분리된 개념이 아니며 세션은 쿠키를 기반으로 함)
• 각 클라이언트 마다 유니크한 세션 객체가 주어지고, 이 세션 객체에 데이터를 담아 관리할 수 도 있음.
• (세션 객체가 자물쇠로 잠긴 상자라면 세션 id 가 열쇠인 셈)
• 세션을 사용하지 않고 쿠키만으로 어떤 데이터를 주고받는다면, 클라이언트는 이미 모든 데이터를 알고 있다는 것.

단점

• 세션
  • 사용자가 인증을 할 때, 서버는 이러한 정보를 저장해야 하고 이를 세션(Session)이라고 부른다. 대부분의 경우에는 메모리에 저장하는데, 로그인 중인 사용자가 늘어날 경우에는 서버의 RAM에 부하가 걸리게 된다. 이를 피하기 위해 데이터베이스에 저장을 하기도 하는데, 이러한 방식 역시 데이터베이스에 무리를 줄 수 있다.
• 확장성
  • 사용자가 늘어나게 되면 더 많은 트래픽을 처리하기 위해 여러 프로세스를 돌리거나 컴퓨터를 추가하는 등 서버를 확장해야 한다. 세션을 사용한다면 세션을 분산시키는 시스템을 설계해야 하지만 이러한 과정은 매우 어렵고 복잡하다
• CORS(Cross-Origin Resource Sharing)
  • 웹 어플리케이션에서 세션을 관리할 때 자주 사용되는 쿠키는 단일 도메인 및 서브 도메인에서만 작동하도록 설계되어 있다. 따라서 쿠키를 여러 도메인에서 관리하는 것은 번거롭다.

Token 인증(Stateless)

토큰 기반의 인증 시스템은 인증받은 사용자들에게 토큰을 발급하고, 서버에 요청을 할 때 헤더에 토큰을 함께 보내도록 하여 유효성 검사를 한다. 이러한 시스템에서는 더이상 사용자의 인증 정보를 서버나 세션에 유지하지 않고 클라이언트 측에서 들어오는 요청만으로 작업을 처리한다.

• 인증이 완료된 클라이언트에게 인증되었다는 의미의 "토큰"을 부여
• 이 토큰은 유일하며 서버에 다른 요청을 보낼 때 헤더에 토큰을 심어서 보낸다.
• 토큰은 세션과 달리 서버가 아닌 클라이언트에 저장하기 때문에 메모리 및 스토리지의 부담을 덜 수 있다.
• 다양한 도메인과 플랫폼에서 활용할 수 있다.(주로 앱과 서버 간 통신 및 인증시에 가장 많이 사용됨)

단점

1. 쿠키/세션과 다르게 토큰 자체의 데이터 길이가 길어, 인증 요청이 많아질수록 네트워크 부하가 심해질수 있다.
2. Payload 자체는 암호화되지 않기 때문에 유저의 중요한 정보는 담을 수 없다.
3. 토큰을 탈취당하면 대처하기 어렵다. (따라서 사용 기간 제한을 설정하는 식으로 극복한다)

JWT(JSON Web Token) 인증 방식

JWT(JSON Web Token)란 인증에 필요한 정보들을 암호화시킨 Json 토큰을 말하고 이를 HTTP헤더에 실어 서버가 클라이언트를 식별하는 방식이다. JWT는 JSON 데이터를 Base64 url-safe Encode를 통해 인코딩하여 직렬화 한 것 이며 토큰 내부에는 위변조 방지를 위해 개인키를 통한 전자서명도 들어있다.

JWT의 구조

• Header
  • JWT에서 사용할 타입(항상 JWT)
  • 해시 알고리즘의 종류
• Payload
  • Registered claims(등록 클레임) : 
    • iss(issuer) : 토큰 발급자
    • exp(expiration time) : 토큰 만료 시간
    • sub(subject) : 토큰 제목
    • aud(audience) : 토큰 수신자/대상자
    • nbf(Not Before) : 토큰의 활성 날짜
    • iat(issued at): 토큰이 발급된 시간, 토큰의 age가 얼마나 되었는지 판단 가능
    • jti : JWT의 고유 식별자, 주로 중복 처리 방지를 위해 사용, 일회용 토큰에 사용하면 유용
  • Public claims(공개 클레임)
  • Private Claims(개인 클레임)
• Signature
  • Header와 Payload를 Base64 URL-safe Encode를 한 이후 Header에 명시한 해시함수를 적용하고 개인키(Private Key)로 서명한 전자서명
  • 비대칭 암호화 알고리즘을 하용하여 암호화를 위한 키와 복호화를 위한 키가 다르다. 암호화(전자서명)에는 user id, 복호화(검증)에는 공개키를 사용한다.
  • 서버의 비밀키와 헤더에 적힌 해싱 알고리즘으로 payload를 암호화한 값이 signature와 같은지 비교함으로써 토큰의 변조 유무 확인

JWT 인증 프로세스

 JWT의 단점

• 매우 복잡한 표준이어서 개발자의 실수로 인한 오류가 발생되기 쉽다.
• 토큰을 임의로 삭제하는 것이 불가능함으로 토큰 만료 시간이 필요하다
  • 보통 만료시간이 짧은 access 토큰과 만료시간이 긴 refresh 토큰 두가지를 발급한다
  • refresh 토큰은 데이터베이스에도 저장
  • 클라이언트는 access 토큰을 계속 사용하다가 만료되면 refresh 토큰을 보낸다.
  • 로그아웃할 경우 refresh토큰을 삭제하여 access 토큰 갱신을 못하게 함
• 토큰이 유출되면 만료시킬 방법이 없다

JWT 주요 보안 취약점

• none 공격
  • JWT 헤더의 해싱 알고리즘을 none으로 넣고 서버에 보내는 공격
• decoding이 쉽다
  • 민감한 정보를 payload에 넣어놓으면 안된다
• 시크릿 키 문제
  • 시크릿키를 너무 단순하게 만들면 안된다
  • 생성키/검증키 2개를 사용
• JWT 탈취
  • 훔치기 어렵게 만들기
  • blacklist 활용
  • access토큰, refresh토큰 활용(refresh 토큰은 1회용으로)

HTTP Request/Response 헤더

Request/Response header 구성

• Host : 요청하려는 서버 호스트 이름과 포트번호
• User-agent : 클라이언트 프로그램 정보 ex) Mozilla/4.0, Windows NT5.1
• 이 정보를 통해서 서버는 클라이언트 프로그램(브라우저)에 맞는 최적의 데이터를 보내줄 수 있다.
• Referer : 바로 직전에 머물렀던 웹 링크 주소(해당 요청을 할 수 있게된 페이지)
• Accept : 클라이언트가 처리 가능한 미디어 타입 종류 나열 ex) */* - 모든 타입 처리 가능, application/json - json데이터 처리 가능.
• Accept-charset : 클라이언트가 지원가능한 문자열 인코딩 방식
• Accept-language : 클라이언트가 지원가능한 언어 나열
• Accept-encoding : 클라이언트가 해석가능한 압축 방식 지정 ex) gzip, deflate
• 압축이 되어있다면 content-length와 content-encoding으로 압축을 해제한다.
• Content-location : 해당 개체의 실제 위치
• Content-disposition : 응답 메세지를 브라우저가 어떻게 처리할지 알려줌. ex) inline, attachment; filename='jeong-pro.xlsx'
• Content-Security-Policy : 다른 외부 파일을 불러오는 경우 차단할 리소스와 불러올 리소스 명시ex) default-src 'self' -> 자기 도메인에서만 가져옴
• ex) default-src 'none' -> 외부파일은 가져올 수 없음
• ex) default-src https -> https로만 파일을 가져옴
• If-Modified-Since : 여기에 쓰여진 시간 이후로 변경된 리소스 취득. 페이지가 수정되었으면 최신 페이지로 교체하기 위해 사용된다.
• Authorization : 인증 토큰을 서버로 보낼 때 쓰이는 헤더
• Origin : 서버로 Post 요청을 보낼 때 요청이 어느 주소에서 시작되었는지 나타내는 값
• 이 값으로 요청을 보낸 주소와 받는 주소가 다르면 CORS 에러가 난다.
• Cookie : 쿠기 값 key-value로 표현된다. ex) attr1=value1; attr2=value2

Q. Queue는 어떤 자료구조 인가요?

Queue는 선입선출 FIFO(First In First Out)의 자료구조입니다.
Enqueue의 시간복잡도는 O(1), dequeue의 시간복잡도는 O(1)입니다.
활용예시는 Cache의 구현, 프로세스 관리, 너비우선 탐색이 있습니다.

Queue 관련 특징 정리

• 선입선출 FIFO
• 데이터 추가 -> Enqueue
• 데이터 추출 -> Dequeue
• 구현 방식
  
  • Array based queue -> enqueue, dequeue 과정에서 남는 메모리가 생김. 메모리 낭비를 줄이기 위해 circular queue 사용
  • List based queue -> 재할당이나 메모리 낭비를 걱정을 할 필요가 없어집니다.
• 원형 큐(Circular Queue)
  
  • front, rear를 가리키는 포인터를 통해 메모리 낭비를 줄임
• 확장 & 활용
  • 양쪽에 enqueue, dequeue가 가능한 double-ended queue와 시간 순서가 아닌 우선순위가 높은 순서로 dequeue할 수 있는 우선순위 queue가 있습니다
  • 활용 예시로는 프린터, CPU task scheduling, Cache구현, 너비우선탐색 등이 있습니다.

Queue 꼬리 질문

Q) Array-Base 와 List-Base의 경우 어떤 차이가 있나요?

Array-Base의 경우 queue는 circular queue로 구현하는 것이 일반적입니다. 이는 메모리를 효율적으로 사용하기 위함입니다. 또한, enqueue가 계속 발생하면 fixed size를 넘어서게 되기 때문에, dynamic array와 같은 방법으로 Array의 size를 확장시켜야 합니다. 그럼에도 enqueue의 시간복잡도는 (amortized)O(1)를 유지할 수 있습니다.

List-Bases의 경우 보통 singly-lilnked list로 구현을 합니다. enqueue는 단순히 singly-lilnked list에서 append를 하는 것으로 구현되고, 이 때 시간복잡도는 O(1)입니다. dequeue는 맨 앞의 원소를 삭제하고 first head를 변경하면 되기 때문에 이 연산도 O(1)의 시간이 걸립니다.

요약하자면, 두 가지 종류의 자료구조로 queue를 구현을 하더라도 enqueue와 dequeue는 모두 O(1)의 시간복잡도를 갖습니다. Array-Base의 경우 전반적으로 performance가 더 좋지만, worst case의 경우에는 훨씬 더 느릴 수 있습니다(resize). List-Base의 경우에는 enqueue를 할 때마다 memory allocation을 해야 하기 때문에 전반적인 runtime이 느릴 수 있습니다.

Q. Stack은 어떤 자료구조 인가요?

Stack은 후입선출 LIFO(Last In First Out)의 자료구조입니다.
시간복잡도는 push O(1), pop O(1)입니다.
활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있습니다.

Stack 관련 특징 정리

LIFO

stack은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out)형식으로 데이터를 저장하는 자료구조입니다.

push & pop

stack에서 데이터를 추가하는 것을 push라고 하고 데이터를 추출 하는 것은 pop이라고 합니다.

push의 경우 stack의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)입니다.

이와 동일하게 pop의 경우도 맨 뒤의 데이터를 삭제하면 완료 되기 때문에 O(1)의 시간복잡도를 갖습니다.

push와 pop은 모두 stack의 top에 원소를 추가하거나 삭제하는 형식으로 구현됩니다.

활용

stack은 재귀적인 특징이 있어서 프로그램을 개발할 때 자주 쓰이는 자료구조입니다. 활용 예시로는 call stack, 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있습니다.

Q. Stack 두 개를 이용하여 Queue를 구현해 보세요.

Queue의 enqueue를 구현하기 위한 스택(instack)을 하나 선언하고, dequeue를 위한 스택(outstack) 하나를 선언한다.
Enqueue()시에는 instack에 데이터를 push하고,
Dequeue()시에는 instack의 데이터를 pop하여 outstack에 push하면 가장 먼저 들어온 데이터가 outstack의 top에 위치하여 FIFO를 구현할 수 있다.

이때 시간복잡도는
enqueue가 O(1)이고
dequeue는 outstack이 비어있는경우 O(n), 차있는 경우 O(1)이게 되어 amortized O(1)입니다.

class Queue(object):
    def __init__(self):
        self.instack=[]
        self.outstack=[]

    def enqueue(self,element):
        self.instack.append(element)

    def dequeue(self):
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

Q. Queue 두개를 이용하여 Stack을 구현해 보세요.

push에 사용할 queue를 q1, pop에 사용할 queue를 q2라고 하면,
push의 경우엔 q1에 데이터를 모두 enqueue하면 되고,
pop할때는 q1의 데이터가 1이하가 될 때 까지 dequeue하여 q2에 enqueue하고
q1에 남은 데이터를 dequeue하여 가장 최근에 저장된 데이터를 반환한다.
그후 다음 pop을 위해여 q1과 q2의 이름을  swap한다.

import queue

class Stack(object):
    def __init__(self):
        self.q1 = queue.Queue()
        self.q2 = queue.Queue()

    def push(self, element):
        self.q1.put(element)

    def pop(self):
        while self.q1.qsize() > 1:
            self.q2.put(self.q1.get())

        temp = self.q1
        self.q1 = self.q2
        self.q2 = temp

        return self.q2.get()

Q. Queue vs priority queue를 비교하여 설명해 주세요

Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장하는 형식입니다. 이와 다르게 우선순위큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다.

Queue의 operation 시간복잡도는 enqueue O(1), dequeue O(1)이고,

Priority queue는 push O(logn) , pop O(logn) 입니다.

Q. Array는 어떤 자료구조 인가요?

Array는 연관된 데이터를 메모리상에 연속적이며 순차적으로 미리 할당된 크기만큼 저장하는 자료 구조 입니다.

Array 관련 특징 정리

• 고정된 공간
• 순차적인 데이터 저장
• Array의 장점
  • Lookup과 Append가 빠름
  • 조회가 많이 발생할 때 사용하면 좋음
• Array의 단점
  • 크기가 고정되어 있기 때문에 메모리의 낭비나 overhead가 발생할 수 있습니다.

Array 꼬리 질문

Q) 미리 예상한 것보다 더 많은 수의 data를 저장하느라 Array의 size를 넘어서게 됐습니다. 이 때, 어떻게 해결할 수 있을 까요?

답변 사항
- 기존 size보다 큰 Array를 선언하여 데이터를 옮겨 할당
- 옮긴 후에는 기존 array를 삭제한다
- 이렇게 동적으로 배열의 크기를 조절하는 자료구조를 Dynamic array라고 합니다.
- 다른 방법으로 size 예측이 힘들다면 Array 대신 Linked list를 사용해서 추가할 때마다 메모리 공간을 할당 받는 방식을 사용하면 됩니다.

Q. Dynamic Array는 어떤 자료구조 인가요?

Dynamic Array는 크기가 고정되어 있지 않아 저장공간이 가득차게 되었을 때 resize하여 유동적으로 크기를 조절하여 데이터를 저장하는 자료구조 입니다.

Dynamic Array관련 특징 정리

• Append의 시간 복잡도
  • 미리 선언된 size를 넘기 전에는 O(1)
  • size를 넘는 순간 resize 과정(2배 크기의 Array선언, 데이터 옮기기) 후에 마지막 자리에 추가하기 때문에 O(n)
  • 하지만 전체적으로 봤을 때 resize는 아주 가끔 발생함
  • 그렇기 때문에 전체적으로는 O(1) 더 정확하게는 Amortized O(1)

Dynamic Array 꼬리 문제

Q)Dynamic Array와 Linked list를 비교하여 장단점을 설명해 주세요

Linked List와 비교 했을 때 Dynamic Array의 장점
- 데이터의 접근과 할당이 O(1)로 굉장히 빠르다
- index로 접근하는 방법이 산술적인 연산으로 이루어져있기 때문입니다.
- Dynamic Array 맨 뒤에 데이터를 추가하거나 삭제하는 것이 상대적으로 빠릅니다. O(1)

Linked List와 비교 했을 때 Dynamic Array의 단점
- 맨 끝이 아닌 데이터를 삭제하거나 추가할때 느리다. O(n)
- 데이터가 연속적으로 저장되어있기 때문에 데이터 추가 및 삭제 후 한칸식 shift해야하기 때문입니다.
- resize 해야할 때 마다 예상치 못한 낮은 퍼포먼스가 발생합니다
- resize에 시간이 많이 걸리므로 필요 이상의 메모리 공간을 할당 받아서 메모리 공간의 낭비가 발생합니다

Q. Linked List에 대해서 설명해 주세요.

Linked List는 Node라는 구조체로 되어있는데, Node는 데이터 값과 다음 Node의 address를 저장합니다.
Linked List는 물리적인 메모리상에서는 비연속적으로 저장이 되지만,
Linked list를 구성하는 각각의 Node가 next Node의 address를 가리킴으로써 논리적인 연속성을 가진 자료구조입니다

Linked List 관련 특징 정리

• 물리적으로 비연속적으로 저장
• 논리적으로 연속성을 가짐
• 메모리 내에서 연속성을 유지하지 않아도 되서 메모리 사용이 자유로움
• 데이터 하나에 값과 다음 노드의 주소값을 저장하기 때문에 데이터 하나당 차지하는 메모리는 더 큼

Q. Array와 Linked list를 비교해서 설명해주세요.

Array는 메모리 상에서 연속적으로 데이터를 저장하고
Linked list는 메모리상에서는 비연속적으로 데이터를 저장하는 대신 각 원소가 다음 원소의 주소값을 가짐으로써 논리적인 연속성을 유지합니다.

그렇기에 operation의 시간 복잡도에서 차이가 있습니다
조회의 경우, Array는 O(1)의 시간복잡도를 갖는 반면 Linked List는 O(n)의 시간복잡도를 갖습니다.
삽입/삭제의 경우 Array는 O(n)의 시간복잡도를 갖지만 Linked list는 O(1)의 시간복잡도를 갖습니다.

그러므로 얼마만큼의 데이터가 저장될지 미리 알고 있고, 조회가 자주 필요한 경우에는 Array를 사용하는 것이 유리하고,
얼마만큼의 데이터가 저장될지 예측하기 힘들거나, 삽입/삭제가 많이 일어나는 경우에는 Linked List를 사용하는 것이 유리합니다.

또한 메모리 활용도에서도 차이가 있습니다.
Array는 선언시 고정된 크기를 갖기 때문에 메모리의 낭비가 발생할 수 있지만
Linked list는 데이터를 추가할 때마다 메모리를 할당하기 때문에 메모리 낭비가 발생하지 않습니다.
또한 Linked list의 각 원소는 value와 다음 원소의 address값을 저장하기 때문에
Array보다 Linked list의 데이터 하나의 크기가 더 큽니다.

Array vs Linked List 주요 비교점

1. 조회(Lookup)

• Array는 연속적으로 데이터를 저장해서 저장된 데이터에 즉시 접근(random access O(1))할 수 있다
• Linked List는 메모리상에 불연속적으로 저장되있기 때문에 순차적으로만 접근 할 수 있다. O(n)

2. 삽입/삭제

• Array는 연속적으로 데이터를 저장해서 데이터를 삽입/삭제할 때 나머지 데이터들의 shift과정이 필요하여 O(n)
• Linked List는 데이터 삽입/삭제 시에 다음 주소를 가리키는 부분만 변경하면 되기 때문에 O(1)

3. Memory

• Array는 append는 빠르지만 고정된 크기의 메모리를 사용하기 때문에 데이터가 저장되어있지 않더라도 메모리를 차지하여 메모리 낭비가 발생합니다.
• Linked List는 runtime중에도 size를 늘리고 줄일 수 있기 때문에 초기 사이즈를 고민할 필요가 없고 필요한만큼 메모리를 할당하기 때문에 메모리 낭비가 없다.

Dynamic Array 꼬리 문제

Q. 어느 상황에 Linked list를 쓰는게 Array보다 더 나을까요?

• $O(1)$으로 삽입/삭제를 자주 해야 될 때
• 얼마만큼의 데이터가 들어올지 예측을 할 수 없을 때
• 조회 작업을 별로 하지 않을 때

Q. 어느 상황에 Array를 쓰는게 Linked list보다 더 나을까요?

• 조회 작업을 자주 해야될 때
• Array를 선언할 당시에 데이터의 갯수를 미리 알고 있을때
• 데이터를 반복문을 통해서 빠르게 순회할 때.
• 메모리를 적게 쓰는게 중요한 상황일 때. Linked list보단 Array가 메모리를 적게 차지 하기 때문에 미리 들어올 데이터의 양을 알고만 있다면 Array가 메모리를 더 효율적으로 사용합니다.

Q. Array와 Linked List의 memory allocation은 언제 일어나며, 메모리의 어느 영역을 할당 받나요?

Array의 경우 compile단계에서 메모리를 할당 받는다.
이를 Static Memory Allocation이라고 하며 이 경우에는 Stack 메모리 영역에 할당됩니다.

Linked List의 경우 runtime 단계에서 새로운 node가 추가될 때마다 메모리를 할당 받는다.
이를 Dynamic Memory Allocation이라고 부르며 Heap 메모리 영역에 할당됩니다.