10일차 - binary search tree, 정렬 알고리즘

in Study-siotz on TIL


추후에 정리가 필요한 문서입니다!!!

10일차

  1. binary search tree(이진 탐색 트리)
  2. 정렬 알고리즘 1. 1.

1. binary search tree(이진 탐색 트리)

1. 이진트리

트리 구조에서 밑으로 가지가 최대 2개까지 있는 트리구조 (0개,1개,2개) 트리 구조 상에서만 부모 자식으로 나누고 데이터 자체는 관계성이 없다.

2. binary search tree

지금 있는 데이터와 비교해서 작으면 왼쪽가지, 크면 오른쪽 가지로 가서 빈 곳에 자리를 잡는다.

3. 기능

1. 삽입 insert

루트 노드의 데이터와 비교해서 작으면 왼쪽으로 내려가고 크면 오른쪽으로 내려가서 자리에 배치!

2. delete

  • 위와 같이 내려가면서 찾다가 찾으면 해당 노드 삭제!

  • 만약 삭제하려는 노드에 자식이 하나 있으면 그 자식을 삭제하려던 노드 자리에 위치시킨다.

  • 만약 삭제하려는 노드에 자식이 둘 이상 손자도 있다면

    1. 오른쪽 subtree의 가장 왼쪽 node
    2. 왼쪽 subtree의 가장 오른쪽 node

4. 순회 3가지

바이너리서치트리예제 이름만 화려하고 별거 없당ㅋ 기준은 root

비용이 적고 효율이 아주 좋아서 개발자들이 매우 좋아함!

1. pre-order

왼쪽을 먼저 보고 오른쪽을 본다

5-3-2-1-4-8-7-6-9

2. in-order

왼쪽-root-오른쪽 정렬할때 많이 쓴다. 루트를 기준으로 가장 subtree까지 들어가서 밑에서부터 확인하며 올라온다

1-2-3-4-5-6-7-8-9

3. post-order

왼쪽-오른쪽-root 순으로 확인한다.

4. 어디에 사용하는가…

이건 모르겠음!ㅎㅎ

2. 정렬 sorting 알고리즘

1. big-O (빅오) 표기법

시간복잡도와 공간복잡도를 표기한다.

코드가 실행되는 시간 표기 메모리를 차지하는 공간 표기

for문 안에 for문이 있을 때 가장 안에 있는 코드는 n*n번 실행된다.

이 떄 시간복잡도는 O(n^2) 라고 표기할 수 있다.

O(log n) > O(n log n) > O(n) > O(n^2)

첫번째가 제일 효율이 좋다! => 이진탐색트리에서 serch의 시간복잡도는 O(log n) 이다! 짱좋음.

2. bubble sort

나열 된 데이터 2개를 비교해서 오른쪽이 더 크면 둘의 자리를 바꾼다(2개를 비교했을 떄 더 작은게 왼쪽에 있게)

무조건 (n-1)번 반복한다 => 정렬이 된다.

한번에 (n-1)번 비교하는데, 이 비교를 (n-1)번 한다

(n-1)^2번 반복하는데 (n^2 + 2n + 1)?? 이기 때문에 뒤에 애들은 그닥 영향이 크지 않으므로 줄여서 n^2번 반복한다고 할 수 있다.

그래서 bubble sort의 시간복잡도는 O(n^2) 이다 (아주 후짐)

3. SPA(Single Page Application), SSR, CSR

SPA의 대표적인 라이브러리. 프론트프레임워크 React, Vue, Angular가 있습니다.

1. SPA란?

  • SPA는 기본적으로 단일 페이지로 구성
  • 기존의 서버 사이드 렌더링과 비교할 때, 배포가 간단하다.
  • 네이티브 앱과 유사한 사용자 경험을 제공하는 장점이 있습니다.
  • 웹 애플리케이션에 필요한 모든 정적 리소스를 최초에 한번 다운로드 한다. 이후 새로운 페이지 요청시, 페이지 갱신에 필요한 데이터만을 전달받아 페이지를 갱신 전체적인 트래픽이 감소하며, 전체 페이지를 다시 렌더링 하지 않고 변경되는 부분만을 갱신하므로 새로고침이 발생하지 않아 네이티브 앱과 유사한 사용자 경험을 제공할 수 있다.

전통적인 페이지 : 사이드 렌더링

매번 서버에서 데이터를 부르므로 비용이 많이든다.

SPA : 클라이언트 렌더링을 사용함.

데이터를 다 가지고 와서 필요한게 있으면 클라이언트쪽에서 빼서 쓴다.

2. 서버 사이드 렌더링 ? (SSR)

전통적인 웹 페이지 방식 = SSR

서버에서 다 처리해서 클라이언트에 넘겨준다.

필요한게 있을 때 마다 서버에 요청한다.

  • SSR의 경우에는 View를 서버에서 렌더링 하여 가져오기 때문에 첫로딩이 매우 짧습니다.
  • View를 보기까지 물론 JS파일을 모두 다운로드하고 적용하기 전까지는 그 어떤 인터렉션에도 반응하지 않습니다.(사용자의 움직임?클릭?에 반응하지 않지만 화면만 그려준다.)
  • 사용자 입장에서는 로딩이 매우 빠르다고 생각할 수 있습니다.

3. 클라이언트 사이드 렌더링 (CSR)

최초에 1번 서버에서 전체 페이지를 로딩하여 보여주고 이후에는 사용자의 요청이 올 때마다, 리소스를 서버에서 제공한 후 클라이언트가 해석하고 렌더링을 하는 방식입니다.

즉,서버는 단지 JSON 파일만 보내주는 역할을 하며 html을 그리는 역할은 클라이언트 측에서 자바스크립트가 수행합니다.

view만 관리하고자 해서 React가 등장했다. (리액트는 CSR SSR 둘 다 쓰는것 같음!)

**SPA 방식이 모두 CSR은 아니다!!!**

  • CSR의 경우 서버에서 View를 렌더하지 않고 HTML을 다운받은 다음
  • JS파일이나 각종 리소스를 다운받은후 브라우저에서 렌더링하여 보여주기 때문에
  • SSR보다 초기 View를 볼수 있기까지 시간이 오래 걸립니다. 즉, 로딩이 길어집니다.
  • 하지만 View가 보여진 시점에서 바로 인터렉션이 가능해집니다.

4. SSR과 CSR의 차이점

크게 렌더링 속도, SEO(검색엔진), 보안으로 볼 수 있습니다.

1. 렌더링 속도

2. SEO

SEO검색 검색엔진 최적화 문제가 존재합니다.

3. 보안 문제

CSR은 쿠키 말고는 사용자에 대한 정보를 저장할 공간이 마땅치 않다. 그래서 보안에 취약하다고 할 수 있다.

면접문제

  1. SPA(Single Page Application)로 구성된 페이지에서 SEO(Search Engine Optimization)를 할 수 있는 방법은 무엇일까?
SEO 대응기술이 존재하고 있는 SPA 프레임워크를 이용하거나, 리액트와 리액트 전용 라이브러리인 nextJS와 같은 프레임워크를 이용해 서버사이드 렌더링을 구현한다.
  1. SSR(Server Side Rendering)은 무엇이고 사용 목적은 무엇인가?
서버에서 렌더링이 일어나는 경우이다. 데이터를 서버에 요청하여 받아온다. 필요할 때마다 요청하기 때문에 첫 로딩이 짧다. 검색엔진을 이용하려면 서버사이드렌더링을 이용해야한다.

4. CORS

1. 동일 출처 정책(Same-Origin Policy)

웹 애플리케이션 보안 모델에서 중요한 개념 중 하나. 자바스크립트로 다른 웹페이지에 접근할 때는 같은 출처의 페이지에만 접근이 가능하다.

같은 출처라는 것은 프로토콜, 호스트명, 포트가 같다는 것을 의미한다.

SPA(Single Page Application)로 구성된 페이지에서 SEO(Search Engine Optimization)를 할 수 있는 방법은 무엇일까?

웹페이지의 스크립트는 그 페이지와 같은 서버에 있는 주소로만 ajax 요청을 할 수 있다.

이 정책이 초기에는 웹 사이트의 보안을 위해 좋은 방법으로 생각되었으나 요즘에는 여러 도메인에 걸쳐서 구성되는 대규모 웹 프로젝트가 늘어나고, REST API 등을 이용한 외부 호출이 많아지는 상황에서는 거추장스러운 기술이 되기도 하고 있다.

그래서 만들어진 추가 정책이 CORS(Cross-Origin Resource Sharing)이다.

동일출처정책을 피하는 방법 CORS 외 3가지

2. Content-Security-Policy

3. CORS(Cross-Origin Resource Sharing)

웹 브라우저에서 외부 도메인 서버와 통신하기 위한 방식을 표준화한 스펙입니다.

1. CORS 작동 방식

Preflight request (사전 요청) 요청하려는 URL이 외부 도메인일 경우 웹 브라우저는 preflight요청을 먼저 날리게 된다. preflight요청은 실제로 요청하려는 경로와 같은 URL에 대해서 옵션 메서드로 요청을 미리 날려보고 요청을 할 수 있는 권한이 있는지 확인합니다. 이 방식으로 CORS요청을 편법 없이 하기 위해서는 클라이언트의 처리만으로 안되고 해당 서버 측에서의 추가 처리사항이 필요합니다.

2. Cross-origin 요청의 위험성

3. 서버에서 CORS 요청 핸들링하기

4. CORS에 관여하는 응답 헤더 정리

5. HTTP / HTTPS

Web browser와 Web server 통신 규칙인 HTTP/ HTTPS

NOTE ! 웹구성 4가지 페이지를 만드는 언어 HTML 원하는 웹페이지에 방문할수 있도록 도와주는 주소 체계 URL, URI 웹페이지를 주고 받는 소프트웨어인 웹브라우저, 웹서버 Web browser와 Web server 통신을 규칙인 HTTP,HTTPS

1. HTTP

Hypertext Transfer Protocol

클라이언트가 요청하면 서버가 응답해주는 것이 HTTP이다

HTML, CSS, JS, 이미지 등… 콘텐츠들을 클라이언트와 서버가 주고 받기 위해서 서로 알아 듣기위해서 공통의 약속이 메시지가 http입니다.

HTTP로 통신을 한다면 암호화가 되어있지 않기 때문에 서버와 클라이언트가 서로 주고받은 메세지를 알아내기가 쉬움(보안에 취약하다.)

2. HTTPS

Hypertext Transfer Protocol Secure

클라이언트가 서버에 HTML 등을 요청하는데 요청할 때 암호화 된 말로 요청하는 것이 HTTPS

  • HTTP의 보안버전이다.

3. HTTPS는 어떻게 작동하는가 ?

4. SSL 인증서

클라이언트와 서버간의 통신을 공인된 제 3자 업체 (CA)가 보증해주는 전자화 된 문서

CA(Cetificate Authority) 디지털 인증을 제공하는 공인 기업

1. SSL 인증서의 장점 및 역할

2. SSL 동작방법

  • 공개키 암포 방식은 알고리즘 계산 방식이 느린 경향이 있다 => SSL을 사용하는 HTTPS가 HTTP보다 느리다는 인식이 있다.?

3. SSL 통신방법

5. HTTPS가 HTTP보다 좋은 점

  1. HTTPS는 HTTP보다 빠르다.(개빠름;;)

  2. 구글 랭킹 노출에 도움이 된다. (HTTPS를 쓰면 순위가 올라간다.)

  3. ATS(IOS App Transport Security)는 HTTP를 차단

  4. PWA(Progressive Web Apps)에는 https 만 가능

  5. 지리정보, 자동기입 등의 모든 API는 https가 필요함

  6. https는 도입 비용이 비싸지않음

  7. 안전하다.

6. HTTP Cache

1. cache가 만들어진 배경

면접문제

  1. CORS에 대해 설명할 수 있나?
동일 출처 정책으로 인해 다른 도메인에 요청을 할 수 없는 경우를 위한 정책이고 외부 도메인 서버와 통신하기 위한 방식이다. 요청을 받은 웹서버가 허용할 경우에는 다른 도메인의 웹페이지 스크립트에서도 자원을 주고받을 수 있게 해준다.