개발26 트리의 구현과 순회는 뭘까? 21.1 도입 계층적 구조의 자료 구조 연결된 두 노드 중 상위에 있는 것이 부모 노드 , 하위는 자식 노드 부모 노드가 같은 두 노드는 형제 노드 부모 노드와 그의 부모들을 통틀어 선조 노드 자식 노드와 그의 자식들을 통틀어 자손 노드 모든 노드의 선조이고, 부모이면 뿌리 노드 , 루트(root) 자식이 하나도 없는 노드는 잎 노드 , 리프(leaf) 트리와 노드 속성 깊이 : 루트에서 어떤 노드까지 도달하기 위해 거쳐야하는 간선의 수 높이 : 트리에서 가장 깊숙히 있는 노드의 깊이 트리의 재귀적 속성 가장 유용하게 쓰이는 이유는 재귀적 속성때문이다. [상위-하위 개념으로 연결된 트리 구조] 에서 ‘탐색형 자료구조(=t)’에서 그 자손들로 구성된 트리를 ‘t’를 루트로 하는 서브트리 라고 한다. 모든 .. 2024. 4. 17. 큐와 스택, 데크는 뭘까? 큐와 스택, 데크 일렬로 늘어선 같은 형태의 자료들을 저장한다. 셋의 차이는 어느 쪽 끝에서 자료를 넣고 뺄 수 있는가 이다. 셋 다 O(1)에 이루어진다. push : 자료를 넣는 것 pop : 자료를 빼는 것 큐 선입선출 가장 먼저 들어간 자료 순으로 빠진다. 줄서기 스택 후입선출 가장 늦게 들어간 것 순으로 빠진다. 컨텍스트 관리 데크 양쪽 끝에서 자료들을 넣고 뺄 수 있다. 스택과 큐를 모두 구현 가능하다. 19.2 큐와 스택, 데크의 구현 연결 리스트 양쪽 끝에서 추가와 삭제를 모두 상수 시간에 할 수 있다. 노드의 할당과 삭제, 포인터를 따라가는데 드는 시간이 걸리기 때문에 가장 효율적이진 않다. 동적 배열 스택은 쉽게 가능하다. 하지만 앞에서 추가와 삭제가 일어나는 것은 동적 배열에서 쉽지 .. 2024. 4. 17. 선형 자료 구조는 뭘까? 18.2 동적 배열 배열을 이용해 만들어낸 별도의 자료 구조이기 때문에 배열의 특징을 그대로 받는다. 원소들은 메모리의 연속된 위치에 저장된다. 캐시의 효율성과 직결되어 중요한 포인트 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. O(1)? 시간복잡도 개념에서 상수를 의미한다. 입력에 관계없이 복잡도가 동일하게 유지된다. 동적 배열만의 특징은 아래와 같다. 배열의 크기를 변경하는 resize() 연산이 가능하다. 이 동작을 수행하는 데는 배열의 크기 N에 비례하는 시간이 걸린다. 주어진 원소의 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append() 연산을 지원한다. 이 동작을 수행하는 데는 상수 시간이 걸린다. 동적 배열의 크기가 바뀌는 과정은 아래와 같다. 새 배열을 .. 2024. 4. 17. ESM (ES Module) feat. Vite JS 파일은 브라우저에서 해석될 수 없다. 모듈은 모듈 스코프를, 변수/함수 스코프를 통해 서로의 파일이 오염되지 않도록 하는 장점이 있다. import, export 를 활용한다. ES6부터 모듈 기능을 제공하기 시작했다. 하지면 IE는 여전히 지원하지 않는다. entry 파일을 기준으로 import한 파일들을 찾아가며 의존성 그래프를 그린다. ES module이 동작하려면 브라우저에서 사용가능하도록 module record라는 데이터 구조로 변환해야한다. 이 변환 과정은 ES6 명세가 아닌 HTML 명세를 따라 구문 분석을 한다. (브라우저 한정) 이런 모듈화 작업은 구성 → 인스턴스화 → 평가 단계로 진행된다. 구성단계에서는 로더가 파일을 불러온다. 파일을 모듈 레코드로 구문 분석한다. 로더는 모듈.. 2024. 4. 15. 브라우저 캐시 캐시는 브라우저에서 서버에 최초 요청 이후 로딩을 더 빠르게 하기 위한 장점이 있다. 그러나 요청에 의해 캐시가 저장되면 이후 변경 내용이 있어도, 사용자 브러우저의 캐시에 의해 캐시를 지우기 전까지 변경 내용의 수정이 일어나지 않을 수 있다. 우리는 header의 cache-control 태그를 이용해 max-age 속성으로 캐시의 수명을 지정할 수 있다. 말만 들으면 max-age=60 으로 설정해놓으면 60초 동안 캐싱된 데이터를 사용하고, 그 이후는 캐싱된 데이터를 사용하지 않고 새 응답을 받는 것 같다. (200을 받을 것같으나) 하지만 이것은 명확한 캐시 수명이 아니다. 60초 이후에도 브라우저는 캐싱된 데이터를 확인하며 캐싱된 데이터가 있다면 304 Not Modified 응답을 준다. 결국.. 2024. 4. 15. 브라우저 대기 시간 Latency 정의 하나의 데이터 패킷이 출발지에서 도착지까지 가는 데 걸리는 시간 대기 시간은 첫 번째 패킷을 받아올 때는 긴 편이다. 첫 번째 패킷의 크기가 14kb로 정해져 있다하더라도 DNS 조회, TLS handshake, TCP negotiation 과정을 거친 후 요청한 패킷을 받아오기 때문이다. 이후에는 이미 네트워크가 연결 되었으니 이러한 과정은 생략된다. 대기시간 측정 방법 브라우저가 자원 요청을 보내는 시간 또는 브라우저가 요청을 보내고, 다시 응답오는 왕복 시간을 측정한다. Network latency 브라우저 요청→ 서버 응답 → 브라우저 해당 자원의 흐름 대기시간 Disk latency 서버 응답 → 브라우저 해당 자원의 흐름 대기시간 브라우저를 이용해서 다양한 네트워크 상태에서 테스트를 할 .. 2024. 4. 15. 이전 1 2 3 4 5 다음 728x90 반응형
