✔ 트라이 트라이란? 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행 문자 종류의 개수인 N에 따라 N진 트리가 결정됨 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지 트라이 과정 루트 노드는 공백을 유지하고 첫 번째 단어의 각 알파벳에 해당하는 노드를 생성 두 번째 단어를 삽입할 때는 루트 노드에서부터 검색을 수행 검색 노드가 공백 상태이면 신규 노드를 생성하고, 아니면 이동
✔ 트리 트리란? 노드와 엣지로 연결된 그래프의 특수한 형태 그래프의 형태이므로 그래프의 표현으로도 트리를 표현할 수 있음 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재함 루트 노드를 제외한 노드는 단 1개의 부모 노드를 가짐 트리에서 임의의 두 개의 노드를 연결하는 경로는 유일 트리의 부분 트리 역시 트리의 모든 특징을 따름 트리의 구성 요소 노드 : 데이터의 index와 value를 표현하는 요소 엣지 : 노드와 노드의 연결 관계를 나타내는 선 루트 노드 : 트리에서 가장 상위에 존재하는 노드 부모 노드 : 두 노드 사이의 관계에서 상위 노드에 해당하는 노드 자식 노드 : 두 노드 사이의 관계에서 하위 노드에 해당하는 노드 리프 노드 : 트리에서 가장 하위에 존재하는 노드 (자식 노드가 없..
✔ 최소 신장 트리 최소 신장 트리란? 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음 N개의 노드가 있으면 최소 신장 트리를 구성하는 엣지의 개수는 항상 N - 1개 크루스칼 알고리즘 또는 프림 알고리즘을 통해 구현됨 최소 신장 트리 과정 엣지를 중심으로 저장하므로 엣지 리스트로 그래프를 표현 노드 변수 2개와 가중치 변수로 구성됨 사이클 처리를 위한 유니온 파인드 배열도 함께 초기화 엣지 리스트의 데이터를 가중치 기준으로 오름차순 정렬 가중치가 낮은 엣지부터 순서대로 선택해 연결을 시도 바로 연결하지 않고 엣지를 연결했을 때 그래프에 사이클 형성 유무를 find 연산을 이용해 확인 두 노드..
✔ 플로이드-워셜 플로이드-워셜란? 그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘 음수 가중치 엣지가 있어도 수행할 수 있음 동적 계획법의 원리를 이용해 알고리즘에 접근 A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분도 최단 경로라는 원리를 이용 V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V³) 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 빠르지 않으므로 노드의 개수의 범위가 다른 그래프보다 적음 플로이드-워셜 과정 최단 거리 배열을 인접 행렬로 표현 s와 e 값이 같은 칸은 0, 다른 칸은 ∞로 초기화 출발 노드는 s, 도착 노드는 e, 이 엣지의 가중치는 w라고 했을 때 D[s][e] = w로 엣..
✔ 벨만-포드 벨만-포드란? 그래프에서 특정 출발 노드에서 다른 모든 노드까지의 최단 거리를 구하는 알고리즘 음수 가중치 엣지가 있어도 수행할 수 있음 최단 거리를 구하는 문제보다 음수 사이클을 판단하는 문제에 더 빈번하게 사용 V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(VE) 벨만-포드 과정 엣지를 중심으로 동작하므로 엣지 리스트로 그래프를 표현 최단 거리 배열을 만들고, 출발 노드는 0, 이 외의 노드는 무한으로 초기화 출발 노드를 1로 선택 선택된 노드에서 연결된 엣지의 값을 바탕으로 다른 노드의 값을 업데이트 D[s] != ∞이며 D[e] > D[s] + w일 때 D[e] = D[s] + w 노드 개수가 N이고, 음수 사이클이 없을 때 특정 두 노드의 최단 거리를 구성할 수 있는 엣지의..
✔ 다익스트라 다익스트라란? 엣지가 모두 양수인 그래프에서 출발 노드와 모든 노드 간의 최단 거리를 구하는 알고리즘 V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(ElogV) 다익스트라 과정 인접 리스트로 그래프를 표현 최단 거리 배열을 만들고, 출발 노드는 0, 이외의 노드는 무한으로 초기화 최단 거리 배열에서 현재 값이 가장 작은 노드를 고름 선택된 노드에 연결된 엣지의 값을 바탕으로 다른 노드의 값을 업데이트 Min(선택 노드의 최단 거리 배열의 값 + 엣지 가중치, 연결 노드의 최단 거리 배열의 값) 이때 한 번 선택된 노드가 다시 선택되지 않도록 방문 배열을 만들어 처리 모든 노드가 선택될 때까지 과정을 반복 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf...
✔ 줄 세우기 [백준 2252] 문제 분석하기 학생들을 노드로 생각하고, 키 순서 비교 데이터로 엣지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제 특히 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일 손으로 풀어보기 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트 진입 차수가 0인 노드를 큐에 저장 큐에서 데이터를 poll해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer 큐가 빌 때까지 반복 슈도코드 작성하기 N(학생 수) M(비교 횟수) A(데이터 저장 인접 리스트) 학생 수만큼 인접 리스트 ..
✔ 위상 정렬 위상 정렬이란? 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 항상 유일한 값으로 정렬되지 않음 V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V + E) 위상 정렬 과정 ArrayList(인접 리스트)로 그래프를 표현 자기 자신을 가리키는 엣지의 개수를 뜻하는 진입 차수에 대한 진입 차수 배열을 업데이트 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀 후, 진입 차수 배열 업데이트 이 과정을 모든 노드가 정렬될 때까지 반복 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
