Developer Cafe

그래프는 데이터가 어떻게 연결되는지 쉽게 이해시키므로 관계에 특화된 자료구조다. 원 하나를 노드로 그 노드는 정점이라 부르고, 정점간 관계인 선은 간선이라 부른다. 또한 그래프는 트위터 팔로우 기능처럼 화살표로 표현된 것을 방향 그래프, 페이스북처럼 상호작용하는 그래프는 무방향 그래프라한다. 위 그림에서 앨리스는 밥과 직접 커넥션이 있으나 신시아와 직접 커넥션이 없다. 비직접적인 커넥션을 포함해 앨리스 전체 네트워크를 찾으려면 두가지 방법이 있다. 1. 너비 우선 탐색 2. 깊이 우선 탐색 여기선 너비 우선 탐색만 포스팅하고 깊이 우선 탐색은 차후 업데이트하거나 따로 비교포스팅하겠다. 너비 우선 탐색 1. 현재 정점과 인접한 각 정점을 방문한다. 이전에 방문한 적 없는 정점이면 방문했다 표시하고 큐에 추..

- 마이크로소프트 사에서 만든 언어로 자바스크립트가 동작하는 어디서나 사용가능하다. - 신규 언어가 아니라 JS를 한단계 감싸는 언어이다. - 2012년 0.8 버전을 시작으로 현(2021-03-08) 4.1 버전까지 출시되었다. - JS는 dynamically typed라는 큰 특징으로 프로그램이 동작할때 실시간으로 타입이 결정이 되어서 runtime 환경때 에러가 발생하는 큰 문제가 있고, TS는 Statically Typed라고 컴파일 시간때(코딩할때) 에러를 잡을 수 있다. dynamically typed let age = 10; age = 'hello'; Statically Typed let age:number = 10; age = 'hello'; // 에러발생 - 객체지향 언어로 JS가 Pro..

트리 - 트리에는 가장 상위 노드를 루트라 부른다. 여기선 2가 루트다 - 90은 50, 150의 부모고 반대로 50, 150은 90의 자식이다. - 트리는 레벨이 있다. 여기선 4 레벨이다 (맨위가 1 레벨) 이진 트리(+트리 특징) - 각 노드의 작식은 0개나 1개, 2개다. - 한 노드에 자식이 둘이면 한자식은 부모보다 작은 값을, 다른 자식은 부모보다 큰 값을 가져야한다. 검색 - 111을 찾는다고 가정하고 두 자식중 부모가 111보다 큰지 작은지 비교 후 조건에 맞는 자식에게 타고 들어가면서 찾고자하는 값을 찾는다. (여기선 111이 부모 90보다 크다 고로 우측 150으로 타고옴) - 이진 트리 검색은 O(log N) 단계이다. 삽입 - 100을 삽입한다고 가정하면 먼저 루트90부터 큰지 작은..

노드 연결 리스트는 서로 인접 하지 않은 메모리 셀 묶음으로 이뤄진다.. 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 서로 인접하지 않은 이러한 셀을 노드라 부른다. "a" 1652 "b" 1983 "c" null 1000 1001 1652 1653 1983 1984 배열 vs 연결 리스트 차이 - 연결 리스트를 다루는 코드는 항상 첫 번째 노드가 메모리 어디에서 시작하는지 알고 두번째 세번째 링크를 따라 나머지 리스트를 검색할 수 있다. - 연결 리스트가 배열보다 나은 점 중 하나는 프로그램이 데이터를 저장하기 위해 메모리 내에 나란히 이어진 빈 셀 묶음을 찾을 필요가 없다는 점이다. 연산 배열 연결 리스트 읽기 O(1) O(N) 검색 O(N) O(N) 삽입 O(N)(끝에서 하면 O(1)..

컴퓨터 정렬에서 실제로 가장 많이 쓰이는게 바로 내장 정렬 함수 퀵 정렬이다. 퀵 정렬은 매우 빠른 알고리즘으로 특히 평균 시나리오 에서 효율적이다. 분할 분할은 배열로부터 임의의 수를 가져와(이 수를 피벗이라 부름) 피벗보다 작은 모든 수는 왼쪽, 큰 수는 오른쪽에 둔다. 1 4 2 3 임의의 수 를 선택(2선택 피벗지정) 후 왼쪽 포인터(1)과 오른쪽 포인터(3)을 고른다. 1. 왼쪽 포인터를 한 셀씩 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다. 2. 오른쪽 포인터를 한 셀씩 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다. 3. 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한다. 4. 두 포인터가 가리키는 값이 같거나 왼쪽 포인터가 오른쪽 포인터 바로 오른쪽..