네트워크 형태로 서로 연결된 노드

정점: 노드

가장자리: 가장자리, 한 쌍의 노드

무게/비용

유향 그래프

무방향 그래프

인접 행렬

인접 목록

너비 우선 검색 DFS

깊이 우선 검색 TFS

폭과 깊이 우선 검색 구현

그래프가 트리인지 확인

그래프의 간선 수 계산

두 꼭지점 사이의 최단 거리 찾기

라고도 함: 접두사 트리, 특별한 트리형 데이터 구조

문자열 관련 문제를 해결하는 데 매우 효과적입니다.

빠른 검색 제공

사전에서 단어 검색

검색 엔진의 자동 제안

IP 라우팅

사전 트리의 총 단어 수를 계산합니다.

사전 트리에 저장된 모든 단어를 인쇄합니다.

사전 트리를 사용하여 배열의 요소 정렬

사전 트리를 사용하여 사전에서 단어 만들기

T9 사전 구축: 사전 트리 DFS

키-값 쌍의 형태로 고유하게 식별된 객체를 저장합니다.

사전: 키-값 쌍의 모음

키키를 이용하여 객체값 검색

Java의 HashSet/HashMap, C의 unordered_map, Python의 dict

<br>작동 원리: 세트용. 키는 해시 함수를 통해 인덱스를 얻은 다음 그 값을 배열에 저장합니다. <br>Get의 경우 키와 해시 함수를 통해 인덱스를 찾아 값을 가져옵니다.

키는 문자열, 정수 또는 알 수 없는 길이의 것일 수 있습니다. 따라서 엄격한 의미에서 O(L)을 사용하는 것이 적절합니다. 모든 작업의 ​​시간 복잡도는 O(1)이 아닌 O(keySize)입니다.

128 해시 함수

충돌이란 해시 함수로 계산한 후 두 개의 서로 다른 키가 두 개의 동일한 값을 얻는 것을 의미합니다. 충돌을 해결하는 두 가지 주요 방법은 다음과 같습니다.<br>오픈 해싱. 이는 해시 테이블의 기반이 되는 배열에서 각 위치가 연결 목록의 헤드 노드임을 의미합니다. 이러한 방식으로 충돌하는 <key, value> 튜플은 동일한 연결 목록에 배치됩니다. <br>폐쇄형 해싱. 충돌이 발생하면 후속 요소가 빈 공간을 찾기 위해 다음 위치로 이동한다는 의미입니다.<br>

129 재해시

해시 함수

해시 테이블 크기

충돌 처리 방법

배열에서 대칭 키-값 쌍 찾기

문제 해결을 위해 해시 테이블을 유연하게 사용할 것인가?

해시 테이블의 기본 원리에 능숙합니까?

편의를 위해 전체 경로를 추적하세요.

배열이 다른 배열의 하위 집합인지 확인

주어진 배열이 분리되어 있는지 확인합니다.

526. 로드 밸런서<br>

134. LRU 캐시 전략<br>657. 삽입 삭제 GetRandom O(1)<br>954. 삽입 삭제 GetRandom O(1) - 중복 허용<br>209.

데이터 스트림 클래스 문제<br>960. 스트림 II의 첫 번째 고유 번호<br>105. 순서가 잘못된 문자열을 사용하여 연결 목록 복사<br> 124. 가장 긴 연속 시퀀스

삽입 정렬

빠른 정렬

선택 정렬

병합 정렬

기수 정렬

힙 정렬

정적 조회 테이블

동적 조회 테이블

해시 테이블

알고리즘 1:O(n) lowerBound O(1) 추가

알고리즘 2:O(logn) lowerBound O(logn) add

1차원 배열

2차원 배열

다차원 배열

하위 배열

배열 간격 문제

외부 정렬 문제

비트 연산

트리 배열은 거의 고려되지 않습니다.

증가하다

삭제 삭제

삽입 삽입,

크기크기

배열에서 두 번째로 작은 요소 찾기

반복되지 않는 첫 번째 정수 찾기

배열의 양수 및 음수 값 재정렬

65. 두 개의 정렬된 배열의 중앙값, 어려운 문제<br>

6. 정렬된 배열 병합<br>64. 두 개의 정렬된 간격 목록 병합<br>486. K 정렬된 간격 목록 병합<br>547. 두 배열<br>548. 두 배열의 교차점<br>793. 다중 배열의 교차점<br>654. K 정렬 배열의 중앙값<br>149. 시간<br>405. 합계가 0인 하위 행렬<br>943. 범위 합계 쿼리 - 불변<br>665. 변수 범위 합계

LIFO. 예를 들어, 물류 적재에서는 나중에 적재된 물품이 먼저 하역됩니다.

이진 트리의 비재귀 순회, 역 폴란드식 계산 등에 사용됩니다.

DFS의 비재귀적 구현의 주요 데이터 구조

너비우선탐색(BFS)에서는 확장할 노드를 기록합니다.

대기열은 비동기 작업을 완료하기 위해 메시지 대기열을 구현하는 데 사용될 수 있습니다.

메시지 생성 및 소비 속도가 일관되지 않은 경우 전송되었지만 수신되지 않은 메시지를 임시로 저장하기 위해 메시지 큐가 필요합니다.

저장 구조(일반적으로 사용되는 배열, 때때로 연결 목록)를 사용하여 요소를 저장합니다.

하나의 배열을 사용하여 세 개의 스택을 구현하시겠습니까?

두 개의 대기열을 사용하여 스택을 구현하시겠습니까? <br>

차이점

연습<br>

푸시, 상단에 요소 삽입

pop은 스택의 최상위 요소를 반환하고 제거합니다.

isEmpty스택이 비어 있고 true를 반환합니다.

top은 최상위 요소를 제거하지 않고 반환합니다.

Java는 Vector 클래스에서 확장되고 push(), pop(), peek(),empty() 및 search()와 같은 작업을 지원하는 java.util.Stack을 사용합니다.

C에서는 <stack>의 스택을 사용하면 됩니다. C의 peek()가 top()으로 호출된다는 점과 pop()의 경우 반환 값이 비어 있다는 점을 제외하면 메소드는 Java와 유사합니다.

Python, 목록을 직접 사용하고, [-1]과 같은 슬라이싱 작업을 사용하여 스택 상단을 보고, 스택 상단을 팝할 때 list.pop()을 사용하고, 스택 상단을 푸시할 때 list.append()를 사용합니다. . <br>

스택을 사용하여 후위 표현식 평가

스택의 요소 정렬

식이 괄호 균형을 이루고 있는지 확인

FIFO 선입선출 순차 저장 선형 데이터 구조, 슈퍼마켓 체크아웃

BFS 알고리즘의 주요 데이터 구조로 사용됩니다.

대기열에 넣기 대기열 끝에 요소 삽입

dequeue는 큐의 헤드 요소를 제거합니다.

isEmpty 열이 비어 있고 true를 반환합니다.

top은 대기열의 첫 번째 요소를 반환합니다.

연결리스트를 사용하여 큐를 구현하시겠습니까?

두 개의 스택으로 큐를 구현하시겠습니까? <br>

원형 배열을 사용하여 대기열을 구현하시겠습니까?

큐를 사용하여 스택을 표현

대기열의 처음 k개 요소를 반전합니다.

큐를 사용하여 1부터 n까지 이진수 생성

642. 데이터 스트림의 이동 평균<br>

955. 원형 배열로 큐 구현<br>

노드 체인: 각 노드에는 후속 노드에 대한 데이터와 포인터가 포함됩니다.

파일 시스템, 해시 테이블, 인접 목록 구현

단방향 연결리스트

이중 연결 리스트

insertAtEnd

insertAtHead

삭제

머리에서 삭제

찾다

isEmpty, 비어 있음, true를 반환합니다.

역방향 연결리스트

연결리스트의 순환 감지

연결된 목록의 마지막 노드에서 n번째 노드를 반환합니다.

연결리스트에서 중복된 항목 제거

계층적 데이터 구조

정점과 모서리로 구성

그래프에 표시된 것처럼 트리에는 사이클이 없습니다.

루트 루트 노드

상위 상위 노드

자식 자식 노드

리프 노드

형제 노드

N-ary 트리

선분 트리는 기본적으로 테스트되지 않았으며 보편적입니다.

자주 테스트되는 이진 트리

이진 트리의 높이 찾기

이진 검색 트리에서 k번째 최대값 찾기

루트 노드로부터 거리 k인 노드 찾기

이진 트리에서 주어진 노드의 조상 노드 찾기

104. K 정렬 목록 병합<br>