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. 현재 정점과 인접한 각 정점을 방문한다. 이전에 방문한 적 없는 정점이면 방문했다 표시하고 큐에 추..

트리 - 트리에는 가장 상위 노드를 루트라 부른다. 여기선 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. 두 포인터가 가리키는 값이 같거나 왼쪽 포인터가 오른쪽 포인터 바로 오른쪽..

컴퓨터 과학에 있어서 재귀는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. function ex() { ex(); } 재귀에서 메서드가 반복되지 않는 경우를 기저 조건(중단 조건) 이라 부른다. 재귀를 다루는 컴퓨팅 사고 function factorial(number) { if (number === 1) { return 1; } else { return number * factorial(number - 1); } } factorial(3); 위의 코드를 실행시키면 일어나는 컴퓨팅 사고 1. factorial(3)이 먼저 호출된다. 2. factorial(2)가 두 번째로 호출된다. 3. factorial(1)이 세 번째로 호출된다. 4. factorial(1)이 먼저 완료된다. 5. facto..

스택과 큐는 제약을 갖는 배열로 이 제약으로 인해 자료 구조가 매우 간결해진다. 두 자료 구조는 임시 데이터를 처리할때 사용하고 오래 데이터를 사용할 때는 사용하지 않는다. 마치... 음식 주문서같이(식사준비부터 배달까지만 필요하니깐) 스택 스택에는 3가지 제약이 존재한다. ● 데이터는 스택의 끝에만 삽입할 수 있다. ● 데이터는 스택의 끝에서만 읽을 수 있다. ● 데이터는 스택의 끝에서만 삭제할 수 있다. 스택에 삽입하는걸 푸시, 제거하는걸 팝 이라한다. 예를 들어 (var x = {y: [1, 2, 3]})이라는 코드에 괄호 를 빼먹었는지 검사하고싶다면 스택을 사용한다. 1. 괄호((),{},[]) 외엔 전부 무시한다. 2. 처음 ( 이 나왔으니 ( 을 푸시한다. ( 3. 다음 { 이 나왔으니 { 을..

해시테이블은 키값이 있는 테이블이다. [ ["사과", 1000] ["바나나",1500] ["포도",2000] ] 그럼 컴퓨터는 어떻게 값을 저장하고 읽어들일까.. 먼저 문자를 숫자로 변환하는 해싱작업을 한다. 이때 각 문자는 지정되어 있는데 예를 들어 ABC라는 값은 A = 1, B = 2, C = 3 으로 되어있을경우 1*2*3 = 6 으로 해싱한다 ABC에 값으로 apple를 넣으면 아래 그림과 같이 표현된다. "apple" 문제는 BAC에 pop이라는 값을 저장할때이다. 마찬가지로 2*1*3 = 6 이니 셀이 중복된다. 이때 해시는 배열처럼 자리를 나누어 저장한다. ["ABC","apple"]["BAC","pop"] 해시값을 찾을때는 선행검색으로 하나하나 차례대로 찾게 된다. 만약 중복된셀이 없으면..

기준 인덱스 다음 원소값을 임시 변수에 저장해 그 값을 왼쪽 원소들과 차례로 비교해 임시 변수의 값이 왼쪽 원소값보다 작다면 앞으로 시프트시키며 정렬한다. 패스스루1 인덱스 1의 값 2는 임시변수에 저장 4 2 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 2 4 7 1 3 패스스루2 인덱스 2의 값 7은 임시변수에 저장 2 4 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 (임시변수값이 더 크다 고로 그대로 저장) 2 4 7 1 3 패스스루3 인덱스 3의 값 1은 임시변수에 저장 2 4 7 1 3 앞의 원소값들과 비교 후 시프트한 후 저장 1 2 4 7 3 패스스루4 인덱스 4의 값 3은 임시변수에 저장 1 2 4 7 3 앞의 원소값들과 비교 후 시프트한 후 저장 1 2 3 4 7 삽입정..

인덱스 0부터 패스스루하는데 각 시점의 최솟값을 구해 그 최소값과 같은 원소값고 시작 인덱스 원소값만 바꾼다. 최솟값(2) 최솟값(2) 최솟값(1) 최솟값(1) 2 6 1 4 1 6 2 4 이후 인덱스 0은 값이 정해졌으니 인덱스 1부터 다시 반복한다. 선택 정렬일때는 (N-1) + (N-2)... + 1 = 번의 비교가 나타난다. 비교단계는 버블정렬과 같다. 하지만, 교환은 패스스루 한번당 한번만 나타난다. 즉, N - 1 의 교환단계가 발생한다. N개의 원소 버블 정렬에서 최대 단계 수 선택 정렬에서 최대 단계 수 5 20 14(10 + 4) 10 90 54(45 + 9) 20 380 199(180 + 19) 40 1560 819(780 + 39) 80 6320 3239(3160 + 79) 선택정렬은..