차쟁이파이썬

#1. 탐욕 알고리즘* 최적의 해에 가까운 값을 구하기 위해 사용* 그사치 추정에 활용* 반드시 최적의 해를 구할 수 있는 것은 아님* 여러 경우 중 하나를 결정해야 할때 마다 매 순간 최적이라고 생각되는 경우를 선택하는 방식#2. 탐욕 알고리즘의 예지불해야 할 값이 4720원일 때 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 작게 지불하는 방법* 가장 큰 동전부터 최대한 지불해야하는 값을 채우는 방식으로 구현* 매 순간 최적이라고 생각되는 경우를 선택하면 됨coin_list = [1, 100, 50, 500]print(coin_list)coin_list.sort(reverse=True)print(coin_list)-->[1, 100, 50, 500][500, 100, 50, 1]#모범..

#1. 너비우선 탐색(Breadth-First Search)* BFS : 대표적인 그래프 탐색 알고리즘* 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 우선 탐색하는 방식* 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들(형제 노드들)을 먼저 순회함graph = dict()graph['A'] = ['B', 'C']graph['B'] = ['A', 'D']graph['C'] = ['A', 'G', 'H', 'I']graph['D'] = ['B', 'E', 'F']graph['E'] = ['D']graph['F'] = ['D']graph['G'] = ['C']graph['H'] = ['C']graph['I'] = ['C', 'J']graph['J'] = ['I']graph-->{'A': ..

#1.그래프(graph)*** 실제 세계의 현상이나 사물을 정점(Vertext) 또는 노드(Node)의 간선(Edge)으로 표현하기 위해 사용* 노드(node) : 위치, 정점이라고 함* 간선(Edge) : 위치간의 관계를 표시한 선으로 노드를 연결한 선(link 또는 Branch라고도 함)#1-1. 그래프의 종류1. 무방향 그래프 * 방향이 없는 그패프 * 간선을 통해, 노드는 양방향으로 갈 수 있음2. 방향 그래프 * 간선에 방향이 있는 그래프 * 보통 노드 A, B가 A -> B 로 가는 간선으로 연결괴어 있는 경우 로 표기 * 단, 와 는 다름3. 가중치 그래프 * 간선에 비용 또는 가중치가 할당된 그래프4. 연결 그래프와 비연결 그래프 * 연결 그래프: 무방향 그래프에 있는 모든 노..

#1. 순차탐색(Sequential Search)*** 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미* 순차 탐색 : 데이터가 담겨 있는 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법* 최악의 경우 리스트 길이가 n일떄 n번 비교해야함from random import randintdata_list = list()for num in range(10): data_list.append(randint(1, 100))data_list-->[92, 66, 32, 49, 50, 12, 58, 58, 88, 87]def sequencial(data_list, search_data): for index in range(len(data_list)): if data_list[index] ..

#1. 순차탐색(Sequential Search)* 탐색은 여러 데이터 중에서 원하는 데이터를 찾아내는 것을 의미* 순차 탐색 : 데이터가 담겨 있는 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법* 최악의 경우 리스트 길이가 n일떄 n번 비교해야함

# 1. 병합정렬(merge sort)* 재귀 용법을 활용한 정렬 알고리즘* 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔* 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬* 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병#2. 알고리즘 이해하기'''data_list = [1, 9, 3, 2]'''1. [1,9] 로 나눔2. 앞부분은 [1], [9]로 나누고 뒷부분은 [3],[2]로 나눔3. 정렬해서 합침 [1,9] , [2, 3]4. [1,9] , [2, 3] 을 합침(단, 아래와 같은 조건으로) * 1 2 이므로 리스트에 2를 추가 [1,2] * 9 > 3 이므로 리스트에 3을 추가 [1,2,3] * 9 밖에 없으니 리스트에 9를 추가 [1,2,3,9] #3. 알고리즘..

1. 분할 정복(Divide and Conquer)* 문제를 여러 개의 독립적인 하위 문제로 나눠서 각각 해결한 후, 그 결과를 합쳐서 원래 문제를 해결하는 방식* 재귀적으로 하위 문제를 풀고, 합병 과정을 거치는 게 특징2. 분할 정복을 사용하는 대표적인 정렬: 퀵 정렬* 정렬 알고리즘의 꽃* 기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성* 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함2-1. 퀵 정렬 알고리즘 구현하기* 만약 리스트 갯수가 한 개이면 해당 리스트를 반환* 그렇지 않으면, 리스트 맨 앞의 데이터를 기준점(pivot)으로 설정* left, right 리스트 변수를 만듦* 맨 앞의 데이터를 뺀 나머지..

1. 동적 프로그래밍(Dynamic Programming)* 복잡한 문제를 작은 하위 문제들로 나누고 그 결과를 재사용하여 효율적으로 문제를 해결하는 알고리즘 기법* 주어진 문제를 풀 때,같은 하위 문제를 여러 번 푸는 대신,그 결과를 저장해 두고 필요할 때 다시 사용하는 방식1-1. 동적 프로그래밍의 접근 방식* 메모이제이션(Bottom-Down): 큰 문제를 풀기 위해 재귀적으로 하위 문제들을 풀면서, 이미 계산된 하위 문제는 저장된 값을 재사용하는 방식* 테이블 방식(Bottom-Up): 작은 하위 문제부터 시작해 차례대로 계산해가며, 최종적으로 큰 문제를 해결하는 방식1-2. 동적 프로그래밍 알고리즘* 피보나치 수열 n을 입력받아서 계산* [피보나치](https://namu.wiki/w/%ED%9..

1-1. 알고리즘 복잡도 계산이 필요한 이유* 정수의 절대값을 구하는 방법 * 방법1: 정수값을 제곱한 값에 루트 씌우기 * 방법2: 값이 음수인지 확인하고 음수일때 -1을 구하기> 다양한 알고리즘이 더 좋은지 분석하기 위해 복잡도를 정의하고 계산함1-2. 알고리즘 복잡도 계산 항목* 시간 복잡도: 알고리즘 실행 속도* 공간 복잡도: 알고리즘이 사용하는 메모리 사이즈### 1-3. 알고리즘 오메가 성능 표기법* 오메가 표기법: 알고리즘 최상의 결과를 표기* 세타 표기법 : 알고리즘 평균 결과를 표기* 빅오 표기법 : 최악의 실행 결과를 표기(가장 많이 사용함, 아무리 최악의 상황이라도 이 정도의 성능은 보장함을 의미)# **2.시간 복잡도*** 알고리즘이 수행되는 시간이 입력 크기에 따라 어떻게 변하..

#1.재귀함수(recursive call)* 함수 안에서 동일한 함수를 호출하는 형태* 여러 알고리즘, 고급 정렬 알고리즘 작성시 자주 사용됨### 1-1. 재귀 함수 호출 분석* 2! = 1 * 2* 3! = 1 * 2 * 3### 1-2. 규칙'''n! = n (n-1)!'''* 함수로 만들기 = def factorial(num)* factorial(num)은 num > 1 이라면 return n * factorial(n-1)* factorial(num)은 num = 1 이라면 return n### 1-3. 검증* 2! * factorial(2)이면 2 > 1 이므로 2 * factoral(1) * factorial(1)은 1이므로 return 2 * 1 * 결과는 2 * 3! * factor..