Seok_In

그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미한다. 이번 장에서는 다른 그래프 알고리즘들에 대해서 공부해 볼 것이다. 🔷 Tree 자료구조 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델이며, 방향성이 있고 순환성이 있으며 루트 노드가 존재한다. 🔷 서로소 집합(Disjoint Sets) 수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미하는데 자료구조에서의 서로소 집합이란 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조라고 할 수 있다. 서로소 집합 자료구조는 union과 find 2개의 연산으로 조작할수 있다. 서로소 집합 자료구조를 구현할 때에는 트리 자료구조를 이용하여 집합을 표현하는데 아래와 같은 알고리즘으로 표현한다. 1...

저번 글에서는 다익스트라 알고리즘에 대해서 공부하였고, 이번 글에서는 이어서 플로이드 워셜에 대해 공부해보려고 한다. 🔷 플로이드 워셜 알고리즘 (Floyd=Warshall Algorithm) 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우에 사용 할 수 있는 다익스트라 알고리즘과 달리 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다. 플로이드 워셜은 2차원 리스트에 최단거리 정보를저장하는 특징으로 N번의 단계를 수행하는데 단게마다 O(N^2)의 연산을 수행해서 총 시간 복잡도는 O(N^3)이다. 알고리즘은 노드의 개수가 N개 일 때 1번을 거쳐가는 경우 부터 N번째까지 거쳐가는 경우를 고려해서 그 중에서 사이사이..

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘인데 보통 그래프, 간선, 노드로 표현된다. 우리는 보통 문제를 해결할 때 다익스트라 알고리즘, 플로이드 워셜, 벨만포드 알고리즘 이렇게 3가지를 이용하게 되는데 이 책에서는 2가지만 다루고 있다. 🔷 그래프, 노드, 간선 ◼ 그래프(Graph) 그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료 구조를 의미한다. ◼노드(Node) 정점(Vertex)이라고도 부르며 단순하게 하나의 지점이라고 생각하면 편하고 다른 연결된 노드와 간선에 대한 정보를 가지고 있다. ◼간선(Edge) 노드와 노드 사이에 연결된 통로라고 생각하면 된다. ◼그래프의 표현 그래프의 표현은 크게 2가지 방식으로 표현할 수 있다. 0과 1 사이의 거리가 7이고, 0과 2..

🔷 다이나믹 프로그래밍 우리는 현실에서 컴퓨터를 활용할 때 공간적 제약과 시간적 제약을 받는다. 따라서 우리는 이러한 제약을 해결하기 위환 효율적인 알고리즘을 작성해야하는데 대표적인 방법이 다이나믹 프로그래밍 기법이다. 동적계획법이라고도 표현하기도 한다. 다이나믹 프로그래밍에는 두가지 방식이 있다. 바로 탑다운과 보텀업이다. 위 단순 피보나치 함수를 보자. x 값이 작다면 상관없지만 x값이 커지게 되면 밑에있는 하위의 연산들이 계속 진행되어야 한다. 이는 쓸데없는 연산이며 이 경우 를 해결하기 위해 우리는 아래와 같은 탑다운, 보텀업 방식을 이용할 수 있다. ◼탑다운 방식(Top Down) 재귀함수를 이용하며 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식으로 하향식이라고도 한다. 메모이제이션 기법을..

🔷 탐색(Search) : 탐색이란 많은양의 데이터 중에서 원하는 데이터를 찾는 과정 ◼ 순차 탐색 (Sequential Search) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법으로 보통 정렬되지 않은 리스트에서 활용된다. ◼ 이진 탐색(Binary Search) 배열 내부의 데이터가 정렬되어 있을 때 사용할 수 있는 알고리즘으로, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 과정이다. 이진탐색은 재귀와 반복문을 통해서 구현을 할 수 있다. - 반복문으로 구현 - 재귀함수를 이용하여 구현 ◼ 참고 이것이 취업을 위한 코딩테스트다 with 파이썬