일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- ESlint
- 호이스팅
- 리터럴 타입
- 공변성
- CORS
- 투포인터
- async/await
- app router
- SSR
- Promise
- tailwind
- 결정 알고리즘
- 태그된 유니온
- RTK Query
- React
- map
- 이분 검색
- recoil
- TS
- 반공변성
- useAppDispatch
- 인터섹션
- 무한 스크롤
- CI/CD
- dfs
- Cypress
- autosize
- Jest
- webpack
- 타입 좁히기
- Today
- Total
목록학교/알고리즘 (8)
짧은코딩
해싱 해싱: 산술적인 연산을 이용하여 키가 있는 위치를 계산하여 찾아가는 검색 방식 해시 함수: 키 값을 원소의 위치로 변환하는 함수 해시 테이블: 해시 함수에 의해 계산된 주소의 위치에 항목을 저장한 표 동일한 해시 주소를 가지면 충돌이 일어난다. 해시 함수 -해시 함수의 조건 해시 함수는 계산이 쉬워야하고 충돌이 적어야한다. 헤시 테이블에 고르게 분포할 수 있어야한다. -중간 제곱 함수 예를 들면 제곱하여 중간 자리 수에 있는 값을 해시 주소로 사용한다. -제산 함수 나머지 연산이다. 10, 7, 77, 9를 각각 8로 나누고 그 나머지를 해시 주소로 사용한다. -승산 함수 키 값 k와 정해진 실수 α를 곱한 결과에서 소수점 이하 부분만을 테이블의 크기 M과 곱하여 그 정수 값을 주소로 사용한다. -..
레드 블랙 트리 1. 루트는 블랙이다. 2. 모든 리프는 블랙이다. => 레드 블랙 트리에서 리프는 맨 밑에 노드가 아닌 맨 밑에 숨겨진 자식 노드, 즉 존재하지 않는 NIL을 의미한다. 3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. => 노드가 블랙이면 색은 상관없다. 4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. 오른쪽 그림처럼 NIL에 갈 때 만나는 블랙 노드 개수가 모두 3개로 통일이다. 레드 블랙 트리 삽입 이진검색트리에서의 삽입과 같지만 삽입된 노드는 반드시 레드로 칠한다. -부모가 블랙 문제 없다. -부모가 레드 문제가 발생한다. => 삽입된 노드의 부모의 형제를 확인한다. case1: 부모의 형제가 빨간색인 경우(recoloring)..
최단 경로 탐색 목적지가 분명하다. -과정 O: open 앞으로 갈 지점 C: close 현재 지점 F score: G + H, F가 짧은거 선택 G score: 처음 노드부터 자기 노드까지 거리 H score: 앞으로 갈 목적지까지 예상 거리, 1->6은 직접 못간다. 그래서 직선 거리를 구한다, 대충 눈대중으로 구함 parent node로 추적해서 경로 찾는다. 가장 짧은 3을 선택 이렇게 하다 보면 최종적으로 이렇게 나온다. 그러면 C의 마지막부터 parent node를 따라가서 출발지가 나오면 그게 최종 경로이다.
원시적인 매칭 이렇게 하나씩 맞춰보는 것 -원시적인 매칭이 비효율적인 예 오토마타를 이용한 매칭 -ababaca를 체크하는 오토마타 순서 대로 맞게 들어오면 단계가 올라간다. 이것을 만드는 것이 어렵다. 위 그림을 S/W 구현 라빈-카프 알고리즘 문자열 패턴을 수치로 바꾸어 문자열의 비교를 수치 비교로 대신한다. -수치화 여기서는 문자가 5개라 5진수를 사용한다. 그리고 문자를 인덱스 번호처럼 대응 시킨다. 그리고 5진수라 5^n이렇게 해준다. n은 1씩 감소한다. -수치화를 이용한 매칭의 예 eeaab를 찾는데 eeaab를 수치화하면 3001이다. 따라서 앞부터 수치화해서 3001가 나오는 것을 찾는다. a2부터는 a1의 값에서 a1의 맨 앞 수를 빼고 추가되는 것을 더해주면 된다. 그리고 차수가 높아..
이진 검색 트리 이진 검색 트리의 각 노드는 키값을 하나씩 갖고 키값은 모두 달라야 한다. 루트 노드가 있고 각 노드는 최대 두 개의 자식을 갖는다. 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식의 키값보다 작다. -서브 트리 -이진 검색 트리 검색 1. 여기서 25을 찾으면 맨 처음 30보다 작아서 왼쪽, 20보단 커서 오른쪽으로 가면 25가 나온다. 2. 27을 찾으면 맨 처음 30보다 작아서 왼쪽, 20보다 커서 오른쪽 하지만 25보다 큰데 25의 자식이 없어서 27은 저 트리에 없다. 이러면 NIL이라고 한다. -이진 검색 트리 삽입 -이진 탐색 트리 삭제 r이 리프 노드인 경우 r의 자식 노드가 하나인 경우 r의 자식 노드가 두 개인 경우 1. r이 리프 노드인 경우 그냥 삭제한다. 2. r의 ..
최단 경로 신장 트리가 아닌 가중치 그래프, 즉 네트워크에서 정점 u와 정점 v를 연결하는 경로 중에서 가중치 합이 최소인 경로 다익스트라 최단 경로 알고리즘 그래프가 이렇게 있으면 A B C D E A 0 10 5 INF INF C 0 8 5 14 7 E 0 8 5 13 7 B 0 8 5 9 7 A C E B D 순서대로 방문하게된다. -최단 경로 트리 최단 경로 트리이다. 플로이드 최단 경로 알고리즘
이진 트리 -모든 노드의 차수를 2 이하로 제한하여 전체 트리 차수가 2 이하 -이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가짐(공백 노드도 자식으로 취급) -0
완전 그래프 각 정점에서 다른 모든 정점을 연결해 최대로 많은 간선 수를 가진 그래프 무방향 그래프 최대 간선 수: n(n-1)/2개 방향 그래프 최대 간선 수: n(n-1)개 그래프 구현 -인접 행렬 무방향 그래프 방향 그래프 -인접 리스트 무방향 그래프 방향 그래프 그래프 순회 -깊이 우선 탐색, DFS 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이를 탐색해 가는 법 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 1. A를 시작으로 깊이 우선 탐색 시작 스택: Null 2. A에서 방문하지 않은 정점 B, C가 있어서 A를 스택에 push, 이 중에서 오름차순에 따라 B를 선택 스택: A 3. B에 ..