자료구조 스터디10 자료구조 스터디 6주차 섹션 6) 다익스트라에서 최소 신장 트리까지1.다익스트라 알고리즘시작 노드와 그 외 노드들 간의 최단 거리를 구하는 알고리즘. 엣지는 항상 양수여야 한다. 1. 인접리스트로 그래프 구현하기 (각 노드에서 갈 수 있는 노드와 가중치를 리스트 원소로)(인접행렬로도 구현 가능하지만 시간복잡도 측면에서 인접리스트로 구현해주도록 한다.)2. 최단거리 배열을 초기화한다. (시작노드는 0 나머지는 무한대)3. 값이 가장 작은 노드 고르기(처음은 시작노드가 된다)4. 최단거리 배열 업데이트하기5.모든 노드가 처리될때까지 3, 4 반복. 방문 배열을 만들어 재방문이 일어나지 않도록 한다. 2.벨만포드그래프에서 최단거리를 구하는 알고리즘.출발 노드에서 다른 노든까지의 최단 경로 탐색.엣지는 음수여도 된다.(음수 사이클 .. 2024. 5. 25. 자료구조 스터디 5주차 5-1) 그래프노드와 엣지의 집합 유니온 파인드그래프의 사이클이 생성되는지 판별하는 알고리즘위상 정렬사이클이 없는 방향 그래프에서 사용가능.그래프의 노드들을 선형으로 정렬. 정렬 결과가 꼭 한개는 아님 ex)수강신청다익스트라시작점이 존재하고 그 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘.단 음수 간선은 있으면 안됨 =>최단거리 알고리즘 벨만-포드다익스트라 알고리즘인데 음수 간선이 가능함. 음수 사이클이 존재하는가=>최단거리 알고리즘 플로이드-워셜벨만 -포드 알고리즘 인데 시작 노드가 없음. 즉 모든 노드 사이의 최단거리 측정. (시간복잡도가 안좋음)=>최단거리 알고리즘 최소 신장 트리 mst. 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘. 사이클이 없.. 2024. 5. 18. 자료구조 스터디 4주차 4-1)소수 구하기 핵심 이론소수: 1과 자기 자신 외 약수가 존재하지 않는 수 기본 원리에라토스테네스의 체:1. 구하고자 하는 범위만큼 1차원 배열 생성2. 2부터 시작하고 현재 숫자가 지워지지 않을 때 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움.이때 처음 선택한 숫자는 지우지 않는다.3. 배열의 끝까지 반복해준 후 배열에남아 있는 모든 수 출력이중 for문을 사용하므로 시간 복잡도는 N^2최적화 정도에 따라서 실제 속도는 n(log(logn))임.배수 삭제 과정에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문에라토스테네스의 체는 소수를 구하는 일반적 방법으로 이용된다. 4-2)오일러 피자주 등장하지는 않음오일러 피 함수 p(n)의 정의는1부터 n까지의 숫자중.. 2024. 5. 15. 자료구조 스터디 3주차 3-1)깊이 우선 탐색 DFS가장 많이 사용되는 탐색 방법.깊이우선 탐색: 그래프 완전 탐색 기법중 하나. 시작 노드에서 출발하여 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다음 분기로 너머가 탐색을 수행.재귀 함수, 스택 자료구조를 이용한다. 시간 복잡도: O(노드 수+엣지 수)깊이 우선 탐색에서 재귀함수를 이용하므로 스택 오버플로우에 유의해야 함. 한번 방문한 노드를 다시 방문하지 않으므로 노드 방문 여부를 페크할 배열이 필요하다. 대부분 인접리스트로 표현.후입선출의 특성을 가진다. 실제로는 스택 자료구조보다 스택의 성질을 갖는 재귀함수로 구현하는 경우가 더 많다. [수행과정] 1. dfs를 시작할 노드를 정한 후 사용할 자료구조(인접리스트)를 초기화한다. 2. 스택에서 노드를 꺼내고.. 2024. 5. 4. 이전 1 2 3 다음
