Developer Cafe

1959년 에드거 데이크스트라가 최단 경로 문제를 푸는 굉장히 흥미로운 알고리즘을 만들었다. 1. 시작 정점을 현재 정점으로 한다. 2. 현재 정점에 인접한 모든 정점을 확인해서 시작 정점으로부터 알려진 모든 위치까지의 가중치를 계산하고 기록한다. 3. 다음 현재 정점을 결정하려면 시작 정점으로부터 도달할 수 있는 방문하지 않은 가장 저렴한 알려진 정점을 찾는다. 4. 그래프 내 모든 정점을 방문할 때까지 1~3단계를 반복한다. 0에 갈 수 있는 정점은 4, 1, 5 이다. 이들의 최단 거리를 저장한다. 이어 가장 가까운 최단거리인 4를 다음 정점으로 한다. 4에서 갈 수 있는 6, 1, 3의 최단 거리를 0에서 시작하는 거리값으로 저장한다. 예를 들어 6인 경우는 3+5이니 8이다. 그러므로 8을 저장..

그래프는 데이터가 어떻게 연결되는지 쉽게 이해시키므로 관계에 특화된 자료구조다. 원 하나를 노드로 그 노드는 정점이라 부르고, 정점간 관계인 선은 간선이라 부른다. 또한 그래프는 트위터 팔로우 기능처럼 화살표로 표현된 것을 방향 그래프, 페이스북처럼 상호작용하는 그래프는 무방향 그래프라한다. 위 그림에서 앨리스는 밥과 직접 커넥션이 있으나 신시아와 직접 커넥션이 없다. 비직접적인 커넥션을 포함해 앨리스 전체 네트워크를 찾으려면 두가지 방법이 있다. 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)..