[TIL] 정렬 알고리즘과 시간복잡도

오늘의 나는 무엇을 잘했을까?

1. 가고싶은 기업이 무엇인가?에 대해 고민했다.

   라인으로 결정! 내일 멘토링 시간에 분석해볼 공고문을 정리했다😊

2. 정렬 정리

   기본 정렬을 구분 짓고 개념 정리를 할 뿐만 아니라 python 코드로 작성 했다.

오늘의 나는 무엇을 배웠을까?

[1] 알고리즘의 기본, 정렬과 시간복잡도

재귀함수

base case와 recursive case(재귀적으로 부분문제 풀기)를 모두 생각해내야한다.

• 재귀함수 호출이 너무 많으면 call stack이 과부화된다.
  • 파이썬은 1000개 까지만 허용한다.

하노이 의 탑

1. 원반이 1개면 그냥 옮기면 된다. (종료조건)
2. 1번 기둥에 남아있는 n개 원반 중 n-1 개를 2번 기둥으로 옮긴다
3. 1번 기둥에 남아있는 가장 큰 기둥 (n번째 기둥)을 3번 기둥으로 옮긴다.
4. 2번 기둥에 남아있는 n-1개 원반을 다시 3번으로 옮긴다.

삽입 정렬과 선택 정렬 O(n^2)

삽입 정렬은 자료 배열의 모든 요소를 (보통은)앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 즉 각 값이 어떤 자리에 들어가야할 지 찾는 것이다.

• 앞에서 사용한 배열로 오름차순 삽입 정렬을 할 경우

  • 인덱스 1번에서 시작을 하고 왼쪽에(0) 1번 인덱스의 값보다 큰 숫자가 있으면 자리를 이동시키고 더이상 없으면 그자리에 둔다.

  • 1칸 이동해서 2번 인덱스의 값보다 왼쪽에(0~1) 큰 숫자가 있으면 두 수의 자리를 이동시키고 더이상 없으면 그자리에 둔

  • 1칸 이동해서 3번 인덱스의 값보다 왼쪽에(0~2) 큰 숫자가 있으면 두 수의 자리를 이동시키고 더이상 없으면 그자리에 둔다.
    - 만약 0 1 2 인덱스의 모든 값이 3 인덱스 값보다 크면 [arr[3], arr[0], arr[1], arr[2]] 의 순서대로 이동하겠죠?

    ~ 를 무한 반복하다 끝 인덱스에 다달으면 정렬이 완성되어있다.

• 1,4,2,6,7 오름 차순의 예
  • 1,4,2,6,7 → 1, 2, 4, 6, 7 → 1, 2, 4, 6, 7 → 1, 2, 4, 6, 7 → 1, 2, 4, 6, 7

선택 정렬은 타겟을 이동시키면서 타겟보다 오른쪽에 더 크거나 작은 수가 있다면 위치를 교환하는 것! 이때 더 크거나 작은 수가 여러개라면 그 중 가장 작은 수를 선택한다.

예를 들어 1,4,2,6,7 이라는 배열을 오름차순으로 정렬하고 싶다면 타켓을 0번 인덱스의 값부터 지정하며 오른쪽에 더 작은 수가 있다면 교환한다.

1회전을 했을 경우

• 1, 4, 2, 6, 7 → 1, 4, 2, 6, 7 → 1, 2, 4, 6, 7 → 1, 2, 4, 6, 7 → 1, 2, 4, 6, 7 → 1, 2, 4, 6, 7

정렬 알고리즘 비교

1. 거의 정렬된 리스트를 정렬할 때는 삽입 정렬이 가장 빠르다
2. 무작위 순서의 리스트를 정렬할 때는 힙 정렬이 가장 빠르다
3. 아예 정반대로 정렬된 리스트의 경우 다시 원래대로 정렬하려면 삽입 정렬이 매우 오래 걸린다.
4. 선택 정렬과 합병 정렬은 상황에 영향을 받지 않고 일정한 시간이 소요된다

정렬 알고리즘 최악의 시간 복잡도

• 선형탐색 O(n)
• 이진탐색 O(logn)

파이썬 내장 함수들의 시간 복잡도

O(1) 들

• 인덱싱 my_list[index]
• append(el)
• len(my_list)
• 값 찾기my_dict[key
• 값 넣어주기/덮어쓰기my_dict[key] = value
• 값 삭제del my_dict[key]
• type

O(n)들

• 뒤집기 reverse()
• 탐색 el in my_list - O(n)
• .insert(idx, ele) - O(n)
• del mylist[idx] - O(n)
• min() or max()

기타

• my_list[a:b] : O(b-a)
• 정렬 my_list.sort()or sorted(my_list) : O(nlogn)
• str() - O(logn)

[2] 브라우저 동작 원리

프론트엔드 개발자라면 알고 있어야하는 브라우저의 동작 과정
관련 테크톡 영상

브라우저 렌더링 동작 과정은 다음과 같은 순서로 진행 됩니다.

• 서버로부터 자원을 요청한 뒤 응답받기브라우저는 URL을 입력받으면, DNS(도매인 서버)를 통해 IP주소로 변환받아 해당 IP 주소를 갖는 서버에 요청을 전달합니다.

• HTML 파일(with JS)과 CSS 파일을 파싱해서 각각 Tree를 만듭니다. (Parsing)

  • HTML & CSS 파일을 해석하여 DOM Tree / CSSOM Tree를 구성하는 단계입니다

    • JavaScript는 렌더링 엔진 레이어가 아니기 때문에 JavaScript 인터프리터 (= js 엔진)라는 별도의 레이어에서 언어를 해석합니다.

    • JS 파싱 후 AST 생성하는데, 추상 구문 트리이고(각각 의미를 갖는 토큰으로 분해 된 후 결합하여 형성된 트리), 이후 바이트코드로 변환되어 인터프리터가 실행합니다.

    • HTML 파싱은 script 태그를 만나면 블로킹되어 렌더링 엔진에서 JS엔진에게 제어권을 넘겨주게 됩니다. 스크립트는 동기적 파싱(위에서 아래로 파싱)이 이루어지기 때문에, HTML 파싱이 script 태그의 위치에 따라 지연될 수 있습니다.만약 JS 코드가 HTML 노드를 생성할 경우, HTML 파싱이 완료되어있어야 합니다.

    • 따라서 script 태그는 되도록이면 body 태그 맨 아래에 위치하는 편이 좋습니다.

    • 두 Tree를 결합하여 Rendering Tree를 만듭니다. (Style)

• DOM Tree와 CSSOM Tree를 매칭시켜서 Render Tree를 구성합니다.

• Rendering Tree에서 각 노드의 위치와 크기를 계산합니다. (Layout)

• Render Tree를 화면에 어떻게 배치해야 할 것인지 노드의 정확한 위치와 크기를 계산합니다.

  • 만약 크기 값을 %로 지정하였다면, Layout 단계에서 % 값을 계산해서 픽셀 단위로 변환합니다.

• 계산된 값을 이용해 각 노드를 화면상의 실제 픽셀로 변환하고, 레이어를 만듭니다. (Paint)

  • Layout 단계에서 계산된 값을 이용해 Render Tree의 각 노드를 화면상의 실제 픽셀로 변환합니다.

• 레이어를 합성하여 실제 화면에 나타낸다. (Composite)

  • Paint 단계에서 생성된 레이어를 합성하여 실제 화면에 나타냅니다.

오늘의 나는 어떤 어려움이 있었을까?

1. 하노이의 탑 풀이

학부생 때 수없이 풀고 넘어간 개념인데 고새 까먹었다. 점화식을 세우는 것이 생각보다 어려웠다 😂

1. 정렬 구분

선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬의 방식이 헷갈린다. 각 정렬의 동작 원리는 잘 설명할 수 있는데, 그래서 이게 어떤 정렬인데? 라고 질문이 들어오면 헷갈린다.ㅠㅠ 잘 구분 지을 수 있도록 공부가 필요하다.

내일의 나는 무엇을 해야할까?

• 알고리즘 1문제 풀이
• 알고리즘 패러다임 완강
• 기본 자료구조들 1/2