파이썬
-
[배열] 하 - 2920 음계 문제백준 Online Judge 2021. 8. 23. 18:31
2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 문제 요약 난이도 : 하 문제 유형 : 배열, 구현 추천 풀이 시간 : 15분 [문제 링크](https://www.acmicpc.net/problem/2920) 문제 해설 숫자 1~8까지 여러 개를 입력 받았을 때, ascending/descending/mixed로 분류하는 문제 입력 예시 : 1 2 3 4 5 6 7 8 출력 예시 : ascending 문제 풀이 코드 # 데이터를 입력 받는다. data_list = li..
-
[알고리즘] 탐욕 알고리즘 (Greedy Algorithm)Algorithms & Data Structure 2021. 8. 22. 14:41
탐욕 알고리즘 최적의 값에 가장 가까운 값을 구하는 알고리즘이다. 알고리즘 예시: 동전 문제 4720원을 1원, 50원, 100원, 500원 동전으로 지불 할때, 가장 적은 동전의 개수로 지불하라. coin_list = [500, 100, 50, 1] def min_coin_count(value, coin_list): total_coin_count = 0 details = list() coin_list.sort(reverse = True) for coin in coin_list: coin_num = value // coin total_coin_count += coin_num value -= coin_num * coin details.append([coin, coin_num]) return total_co..
-
깊이 우선 탐색 (Depth-First Search)Algorithms & Data Structure 2021. 8. 20. 21:56
깊이 우선 탐색이란 그래프 탐색 알고리즘 노드의 자식들을 먼저 탐색하는 알고리즘 오른쪽 노드 먼저, 왼쪽 노드 먼저는 상관 없다. 구현하기 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'] def dfs(graph, start_node): visited, need_visit = list(), list() need_visit..
-
[알고리즘] 너비 우선 탐색 (BFS)Algorithms & Data Structure 2021. 8. 20. 18:23
너비 우선 탐색 (Breadth-First Search) 노드와 같은 레벨에 있는 형제 노드들부터 먼저 탐색하는 방식 그래프를 표현 할 때 딕셔너리와 리스트 자료 구조 활용 시간 복잡도 : O(V+E), (V: 노드 갯수, E: 간선 갯수) 알고리즘 구현 방법 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'] def bfs..
-
[알고리즘] 순차 탐색 (Sequential Search)Algorithms & Data Structure 2021. 8. 18. 19:48
순차 탐색 (Sequential Search) 리스트를 앞에서부터 순서대로 비교하는 탐색 방법. 순차 탐색 구현 방법 from random import * rand_data_list = list() for num in range(10): rand_data_list.append(randint(1, 100)) rand_data_list Out[2]: [65, 21, 75, 43, 86, 98, 32, 51, 58, 13] def sequential(data_list, search_data): for index in range(len(data_list)): if data_list[index] == search_data: return index return False sequential(rand_data_lis..
-
[알고리즘] 이진 탐색(Binary Search)Algorithms & Data Structure 2021. 8. 18. 19:25
이진 탐색 (Binary Search) 탐색: 순차 탐색, 이진 탐색, 해쉬 리스트를 두 개로 나뉜뒤, 가운데 중간값과 검색 대상값을 비교한다. 가운데 중간값 > 검색 대상값, 앞 부분 리스트에서 반복해서 검색한다. 가운데 중간값 < 검색 대상값, 뒷 부분 리스트에서 반복해서 검색한다. 시간 복잡도 : O(logn) 이진 탐색 구현하기 def binary_search(data, search): if len(data) == 1 and search == data[0]: return True if len(data) == 1 and search != data[0]: return False if len(data) == 0: return False medium = len(data) // 2 if search == ..
-
[알고리즘] 병합 정렬 Merge SortAlgorithms & Data Structure 2021. 8. 18. 15:31
병합 정렬이란 분할 정복 알고리즘의 기법을 사용한다. 합병 정렬이라고도 불린다. 재귀 용법을 이용해서 리스트를 잘게 자른다. 그 안에서 다시 또 자른다. 그 뒤에 두 개씩 묶어서 정렬한다. 분리하는 단계, 합병하는 단계로 크게 나뉜다. 병합 정렬 실행 모습 알고리즘 구현하기 def mergesplit(data): if len(data) left_point and len(right) > right_point: if left[left_point] > right[right_point]: merged.append(right[right_point]) right_point += 1 else: merged.append(left[left_point]) left_point += 1 # case2: left만 남아있는 경..
-
[알고리즘] 퀵 정렬 Quick SortAlgorithms & Data Structure 2021. 8. 18. 15:10
퀵 정렬이란 굉장히 효과적인 정렬 알고리즘 Pivot을 정한 뒤, 다른 데이터를 pivot과 비교해서 작으면 왼쪽, 크면 오른쪽으로 정렬 이 과정을 재귀적으로 반복한다 시간 복잡도 : O(n logn) 알고리즘 구현하기 def qsort(data): if len(data) data[index]: left.append(data[index]) else: right.append(data[index]) return qsort(left) + [pivot] + qsort(right) import random data_list = random.sample(range(100), 10) qsort(data_list) Out[6]: [3, 11, 21, 26, 41, 57, 64, 66, 75, 96] 파이썬 compre..