Graph 알고리즘가장 기본이 되는 그래프 알고리즘인 DFS와 BFS에 대한 이야기는 아래의 링크를 통해 확인할 수 있다.https://he-kate1130.tistory.com/73 [Daira i Noor] Python Algorithm (2) - Brute Force Search오늘은 파이썬을 통해 완전 탐색을 하는 방법에 대해 알아본다.완전 탐색의 방법으로 단순한 brute force와, 순열의 활용, BFS/DFSk에 대해서 알아본다. Brute Forcefor문과 if문을 활용하여 모든 가능한he-kate1130.tistory.com 오늘은 Minimum spanning tree에 대한 이야기를 한다. Minimum spanning tree (MST)MST는 한국어로 최소 신장 트리라 한다. ..
[Algorithm] Python Algorithm
오늘은 파이썬을 통해 완전 탐색을 하는 방법에 대해 알아본다.완전 탐색의 방법으로 단순한 brute force와, 순열의 활용, BFS/DFSk에 대해서 알아본다. Brute Forcefor문과 if문을 활용하여 모든 가능한 경우를 검사하는 방법이다. 코테에서 brute force는 사실 많이 나오는 풀이방법은 아니지만, 풀이 과정에서 간단하게 활용할 수 있다. 순열의 활용파이썬으로 순열을 사용하는 방법은 아래의 포스팅에 소개되어있다.https://he-kate1130.tistory.com/70 [python] "코테"를 위한 기초 파이썬 (5) - 순열, 조합, 중복 순열, 중복 조합파이썬에서는 iterpools라이브러리에서 순열과 조합, 중복 순열과 중복 조합에 대한 메서드를 제공하고 있다. 라이브..
이분탐색 문제에 대해 알아보자.Binary Search이분탐색은 기본적으로 탐색하려는 대상이 정렬되어있다는것이 가정된다.즉, 정렬된 상태의 데이터를 효율적으로 탐색하기 위한 방법이다. 탐색 대상 리스트의 가장 중간지점을 확인하고, 타겟이되는 값이 오른쪽, 왼쪽에 있을지 판단하여 점차 탐색대상을 절반으로 줄여나간다. 이분탐색의 시간 복잡도는 O(logN)이다.기존의 순차탐색이 O(N)임 기억한다면 정렬된 상태에서는 이분탐색을 활용하는것으로 상당히 빠르게 문제를 해결할 수 있다는 것을 알 수 있다. 만약 이분탐색을 사용하고자 한다면, 먼저 정렬된 데이터인지 꼭 확인 후에 탐색해야 한다.정렬되어있지 않다면 경우에 따라 순차탐색과 같은 다른 방법이 더 효율적일 수 있다. def binarySearch(a..
가장 간단하게 시작할 수 있는 정렬문제에 대해서 다뤄보도록 한다. sortinghttps://docs.python.org/ko/3/howto/sorting.html Sorting TechniquesAuthor, Andrew Dalke and Raymond Hettinger,. Python lists have a built-in list.sort() method that modifies the list in-place. There is also a sorted() built-in function that builds a new sorted lis...docs.python.org파이썬에서는 내장 함수 sorted() 를 이용해 손쉽게 정렬을 수행할 수 있다. (list의 sort함수도 있지만 리스트에서만 사..
파이썬에서는 iterpools라이브러리에서 순열과 조합, 중복 순열과 중복 조합에 대한 메서드를 제공하고 있다. 라이브러리의 코드가 직접 구현실행하는 것 보다 몇배는 빠르기 때문에 숙지하고, 탐색 알고리즘 등에 활용하도록 하자. 순열 permutation from itertools import permutations my_List = [1,2,3,4,5] for _,elements in enumerate(permutations(my_List,2)): print(elements) #(1, 2) #(1, 3) # ... #(5, 3) #(5, 4) 중복 순열 product from itertools import product list_1 = [1,2,3] list_2 = '45' # list_1과 list_..
오늘은 파이썬 알고리즘 풀이에 자주 사용되는 딕셔너리 자료형에 대한 이야기를 해본다. 파이썬 기초 문법 공부를 할 때 분명히 배우고 넘어가는 영역이지만, 딕셔너리를 자유롭게 사용하기 위해서는 한번 정리를 해두고 문제풀이에 활용해보는것이 좋다. Dictionaty 딕셔너리에 대해서 한번 되짚어보자. 딕셔너리는 순차적으로 element를 얻지 않고, key-value쌍으로 이루어져 있는 자료형이다. # 딕셔너리 생성 dic_1 = {} #빈 딕셔너리 dic_2 = dict() # 선언 -> key:value dic_3 = {'name': 'mingyung', 'age':4000, 'pet':{'type':'beta','name':'pearl','age':2}} keys=['name','age','pet'] ..
이번 포스팅에서는 반복문에서 유용하게 사용하게 될 Enumerate에 대해서 알아보도록 한다. enumerate() 보통 for문은 다음처럼 사용한다. num_list = [1,2,3,4,5] for i in range(len(num_list)): print(i,num_List[i]) 그런데 range대신에 enumerate를 사용하면 인덱스와 element를 튜플형태로 얻어 손쉽게 표현이 가능하다. for i,element in enumnerate(num_list): print(i,element) 예시 코드는 기존 for문 또한 간단한 코드라 큰 유용성을 느끼지 못하지만, 실제 문제 풀이 과정에서 코드가 복잡해질 수록 유용하게 사용할 수 있다. enumerate는 파이썬 알고리즘에서 빠지지 않을 코드이..
이번 포스팅에서는 List Compeohension에 대해서 알아본다. List Comprehension잘쓰면 좋지만 길어지면 머리가 아픈 List Comprehension에 대해서 알아보자. 일반적으로 list를 사용할 때 우리는 다음과 같은 문법을 사용하게 된다.arr=[0]*10for i in range(10): arr[i] = i즉 우리는 선언과, 값 할당을 분리해서 사용한다. List Comprehension은 이 과정을 한번에, 한 줄로 가능하게 한다. 기본적인 문법은 다음과 같다[ (변수를 활용하여 만들 값) for (변수 명) in (순회가능한 값)] 사용예시#가장 기본적인 형태one_list = [i for i in range(10)]# if else문을 사용해볼 수 있다.one_lis..
