그래프 이해 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])을 이용해서 세 개로 짤라서 각 리스트 변수에 넣고 출력해보기..

동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) 1. 정의 - 동적계획법 (DP 라고 많이 부름) - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 - 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 - Memoization 기법을 사용함 - Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 - 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 - 예: 피보나치 수열 ..