목록분류 전체보기 (327)

오늘도 더 나은 코드를 작성하였습니까?

그래프 탐색 - 너비우선 탐색 (BFS Breadth-First Search) feat.kotlin

정의 그래프를 방문 또는 탐색하는 방법중 하나이다. 시작 노드를 기준으로, "동일한 레벨"를 기준으로 탐색을 진행한다. 즉, 1개의 간선으로 연결된 모든 노드 탐색 후, 2개의 간선으로 연결된 모든 노드 탐색.. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 탐색을 적용한다 한번 방문한 노드는 다시 방문하지 않는다. V - 정점(노드)의 개수 E - 간선의 개수 인접리스트로 표현된 자료구조로 탐색 했다면 시간복잡도 - O(V + E) 인접행렬로 표현된 자료구조로 탐색 했다면 (시간 복잡도가 크기 때문에 인접리스트로 바꾸어 탐색) 시간복잡도 O(V^2) 동일한 level 순으로 탐색을 해야될때 사용한다. 간선에 특별한 가중치가 있지 않고 모든 간선의 가중치가 동..
Algorithm/개념 2023. 10. 13. 17:37
그래프 탐색 - 깊이우선 탐색 (DFS Depth-First Search) feat.kotlin

정의 그래프를 탐색 하는 방법중 하나이다. 그래프에서는 탐색을 시작하는 노드를 시작으로 인접한 노드로 지속적으로 이동한다. 더 이상 탐색을 하지 않은 인접한 노드가 없을 때 까지 탐색을 진행후, 부모노드로 돌아와서 탐색하지 않은 인접한 노드를 탐색한다. 인접한 모든 노드가 탐색이 완료되면 종료한다. * 탐색은 한번 방문한 노드는 다시 방문하지 않습니다. (부모노드로 돌아오는것 이외에) * 현재 노드에서 다음 노드로 이동시 인접한 노드중에 선택하는 기준은 위 그림에선 왼쪽 --> 오른쪽이다. V - 정점(노드)의 개수 E - 간선의 개수 인접리스트로 표현된 자료구조로 탐색 했다면 시간복잡도 - O(V + E) 인접행렬로 표현된 자료구조로 탐색 했다면 (시간 복잡도가 크기 때문에 인접리스트로 바꾸어 탐색) ..
Algorithm/개념 2023. 10. 12. 20:00
그래프(graph)의 기본 개념(feat.kotlin)

그래프의 정의 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선 기본적으로 알아야 될 용어 및 정의 path 경로 : 한 정점에서 다른 정점 까지의 경로 degree 차수: 하나의 정점에 연결된 간선의 개수 cycle 순환, 회로: 경로의 시작과 끝이 동일한 것 weight, cost, 가중치: 한 정점에서 다른 정점을 연결하는 간선에 부여된 비용. * 방향성 유무 무방향 즉, 양방향 이동이 가능하다. 방향성 있다 u --> v 는 되지만, u
Algorithm/개념 2023. 10. 12. 01:57
B Tree 데이터 삭제

* 나무위키의 내용 및 *아래 링크의 유튜브 영상을 보고 본 글은 제 학습의 결과를 정리한 내용입니다. https://www.youtube.com/watch?v=H_u28u0usjA 데이터 삭제 1. 모든 데이터는 leaf-node에서 삭제를 진행한다. - internal node를 삭제해야 된다면, lower_bound (삭제 해야되는 노드 보다 작은 값 중 가장 큰것) upper_bound (삭제 해야되는 노드 보다 큰 값 중 가장 작은 것) * 항상 lower_bound / upper_bound는 B tree 특성상 항상 leaf 노드에 존재한다. 둘 중에 1개를 골라 internal node와 위치를 바꾼뒤 삭제를 진행한다면, B tree의 key 정렬 조건을 위배하지 않는다. 15를 삭제 하려고..
자료구조 2023. 10. 11. 19:27
이전 Prev 1 ··· 11 12 13 14 15 16 17 ··· 82 Next 다음