오늘 그래프에 대해 배웠는데 그래프론 시간에 배운 개념들이 꽤 도움이 됐던 것 같다. 직접적으로 언급이된다거나 같은 개념이 나온건 아니었지만 그래프론의 개념이 밑바탕되어서 나오는 개념들이 꽤 있었다.
특히 중국인 집배원 문제가 생각나는 부분이 있었는데, 생각해보니 중국인이 붙어있는 문제들이 많다고 느꼈다. 중국인 집배원 문제, 중국인 나머지 정리, 중국어방 문제... 중국어방은 중국인이 관련된건 아니지만 나머지는 찾아보니 중국인과 관련이 있었다. 배울땐 어디 써먹지 싶었던 것들이 배워두니까 도움이 되긴 되는구나 싶은 날이었다.
인접리스트 공간 복잡도
V+E
인접행렬 공간 복잡도
V^2
인접행렬 간섬 추가, 삭제 편함
인접리스트 정점 추가, 삭제 편함
인접행렬 삭제가 힘든 이유는 모조리 0으로 바꿔두면 자리를 차지하기때문에 뒤에 있는 정보들의 index를 모두 한 칸씩 당겨줘야함
그래서
알고리즘 문제에서는 인접리스트를 주로 쓴다
이진 탐색 트리의 시간 복잡도
보통은 logN에 근사(log의 밑은 2)(만약 이진 트리가 아니라 자식 노드가 n개 있는 트리라면 log의 밑은 n)
최악은 N
================
이진트리종류
전위순회 중위순회 후위순회
인접행렬과 인접리스트 장단점 정리
================
||연산자
||가 OR 인거 아시죠~.
A || B => 이 표현(expression)은 결국 참 또는 거짓이죠?
OR의 특성상 하나만 참이어도 참입니다. 그래서 많은 자바스크립트를 포함해 프로그래밍 언어에 일종의 지름길(shortcut circuit)이 있습니다.
A가 참이면 B의 값을 확인할 필요도 없다는 겁니다.
자바스크립트에서 참이 될 수 있는 값이 뭔지 아시죠?? 그런것들이 A 에 위치하게 된다면, B가 무슨 값인지는 중요하지 않습니다.
반면 A가 거짓이라면 (undefined, null, false, 빈배열 등), 이제 B의 값에 의해 전체값(참/거짓) 여부가 결정됩니다.
B가 핵심인 것이지요. 그래서 B의 값이 곧 전체값이 되는 겁니다
A || B
1. A가 참일 경우 => A의 값과 전체값이 동일 => A 를 그대로 쓴다
2. A가 거짓일 경우 => B의 값과 전체값이 동일 => B 를 그대로 쓴다
그래서 보통 디폴트(default) 값을 설정할 때 활용합니다.
사용자 입력 || 디폴트 값
1. 사용자 입력이 존재하면(빈 문자가 아니라고 가정) => 사용자 입력을 그대로 사용한다
2. 사용자 입력이 존재하지 않으면 => 디폴트 값을 그대로 쓴다.
짜장 짬뽕 중에 골라~
말 없으면 짜장으로 알고 있을게~
&&는 지름길(shortcut circuit)에 의해서 어떻게 활용될 수 있을지를, 위에 제가 작성한 대로 한번 작성해보시죠
