그래프 이해 1. 그래프 (Graph) 란? * 그래프는 실제 세계의 현상이나 사물을 정점(Vertex) 또는 노드(Node) 와 간선(Edge)로 표현하기 위해 사용 예제 집에서 회사로 가는 경로를 그래프로 표현한 예 2. 그래프 (Graph) 관련 용어 - 노드 (Node): 위치를 말함, 정점(Vertex)라고도 함 - 간선 (Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면 됨 (link 또는 branch 라고도 함) - 인접 정점 (Adjacent Vertex) : 간선으로 직접 연결된 정점(또는 노드) - 참고 용어 - 정점의 차수 (Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 - 진입 차수 (In-Degree): 방향 그래프에서 외부에서 오는 간선..

탐색 알고리즘2: 이진 탐색 (Binary Search) 1. 이진 탐색 (Binary Search) 이란? * 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 다음 문제를 먼저 생각하자 이진 탐색의 이해 (순차 탐색과 비교하며 이해하기) 2. 분할 정복 알고리즘과 이진 탐색 - 분할 정복 알고리즘 (Divide and Conquer) - Divide: 문제를 하나 또는 둘 이상으로 나눈다. - Conquer: 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않다면 다시 나눈다. - 이진 탐색 - Divide: 리스트를 두 개의 서브 리스트로 나눈다. - Comquer - 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다...

merge 함수 만들기 * 목표: left 와 right 의 리스트 데이터를 정렬해서 sorted_list 라는 이름으로 return 하기 * left와 right는 이미 정렬된 상태 또는 데이터가 하나임 프로그래밍 연습 1. left 부터 하나씩 right과 비교 2. left > right 이면, left 를 sorted_list에 넣고, 다음 left 리스트와 right 비교 - 그렇지않으면 반대로 하기 다음 경우만 프로그래밍으로 작성해보기 left = [0] right = [3] 결과는 별도의 리스트 변수를 만들어 적은 숫자 순으로 순서대로 저장해서 리턴 프로그래밍 연습 다음 경우만 프로그래밍으로 작성해보기 left = [0, 2] right = [1] 결과는 별도의 리스트 변수를 만들어 적은 숫..

대표적인 정렬4: 병합 정렬 (merge sort) 1. 병합 정렬 (merge sort) - 재귀용법을 활용한 정렬 알고리즘 1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 2. 알고리즘 이해 데이터가 네 개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자.) - 예: data_list = [1, 9, 3, 2] - 먼저 [1, 9], [3, 2] 로 나누고 - 다시 앞 부분은 [1], [9] 로 나누고 - 다시 정렬해서 합친다. [1, 9] - 다음 [3, 2] 는 [3], [2] 로 나누고 - 다시 정렬해서 ..

대표적인 정렬5: 퀵 정렬 (quick sort) 1. 퀵 정렬 (quick sort) 이란? 정렬 알고리즘의 꽃 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함 2. 어떻게 코드로 만들까? 퀵소트 알고리즘에 대해서는 위에서 언급이 되었으므로, 이를 구현하기 위한 세부 코드에 대해 연습을 통해 이해합니다. 프로그래밍 연습 다음 리스트를 리스트 슬라이싱(예 [:2])을 이용해서 세 개로 짤라서 각 리스트 변수에 넣고 출력해보기..

대표적인 정렬2: 삽입 정렬 (insertion sort) 1. 삽입 정렬 (insertion sort) 란? -삽입 정렬은 두 번째 인덱스부터 시작 - 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 -이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 직접 눈으로 보면 더 이해가 쉽다 for index in range(10, 1, -1): print (index) - 출력:10 9 8 7 6 5 4 3 2 2. 어떻게 코드로 만들까? (결국 프로그래밍으로 일반화할 수 있도록 만드는 것) - 알고리즘 연습 방법에 기반해서 단계별로 생각해봅니다. - 데이터가 두개 일 때 동작하는 삽입..