🐍Algorithm

파이썬 코테 공부를 하다보면 collections와 itertools 모듈을 정말 자주 사용하게 된다.오늘부터는 이 컨테이너들 중 코테에 많이 사용하는 자료형 몇가지를 살펴보도록한다. 먼저 이번 포스팅에서는 collection모듈의 Counter에 대해서 알아보자.Counterhttps://docs.python.org/3.11/library/collections.html#collections.Counter collections — Container datatypesSource code: Lib/collections/__init__.py This module implements specialized container datatypes providing alternatives to Python’s gener..

오늘은 코테에서 유용하게 사용할 수 있는 set에 대해서 알아보자Setset은 이름처럼 집합에 관련한 작업을 쉽게 처리할 수 있는 자료형이다.두가지의 큰 특징을 가진다.중복을 허용하지 않는다. 중복값을 제거해준다! 순서가 없다. 따라서 인덱스를 사용할 수 없으므로, 리스트형으로 다시 바꿔 사용하자중복제거는 다음처럼 그냥 list를 set으로 바꾸면 제거된다.list_ = [1,2,3,4,5,5]print(set(list_)) # {1, 2, 3, 4, 5} 중복을 제거한다  다만, 위의 특성으로 인해 set으로 중복 제거를 한 결과는 순서가 유지되지 않는다. 그럼, 순서를 유지하면서 set을 이용하여 중복을 제거하려면 어떻게 해야 할까? 이 때는 sorted함수를 이용해서 인덱스를 기준으로 정렬해주면 된..

가장 간단하게 시작할 수 있는 정렬문제에 대해서 다뤄보도록 한다. 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함수도 있지만 리스트에서만 사..

최단거리 알고리즘최단거리 알고리즘은 그래프에서 정점간의 최단 경로를 찾는 알고리즘입니다.  필수적으로 알고 있어야 하는 알고리즘은 크게 3가지 정도로 꼽아볼 수 있습니다.다익스트라 알고리즘: 가중치가 있는 그래프에서 출발 노드로부터 모든 노드까지의 최단 경로를 찾음. (음수 가중치는 불가능)벨만-포드 알고리즘: 다익스트라와 유사하지만 음수 가중치도 허용. (음수 사이클이 없다는 가정 필요)플로이드-워셜 알고리즘: 모든 정점에서 모든 정점까지의 최단 경로를 찾는 알고리즘.A 알고리즘*: 휴리스틱을 활용하여 특정 목표 정점까지의 최단 경로를 찾음. 다익스트라 알고리즘다익스트라 알고리즘은 하나의 출발 정점(source)에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다.알고리즘출발 노드를 선택하고, 해..

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는 한국어로 최소 신장 트리라 한다. ..

오늘은 파이썬을 통해 완전 탐색을 하는 방법에 대해 알아본다.완전 탐색의 방법으로 단순한 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..

파이썬에서는 iterpools라이브러리에서 순열과 조합, 중복 순열과 중복 조합에 대한 메서드를 제공하고 있다.라이브러리의 코드가 직접 구현실행하는 것 보다 몇배는 빠르기 때문에 숙지하고, 탐색 알고리즘 등에 활용하도록 하자. 순열 permutationfrom itertools import permutationsmy_List = [1,2,3,4,5]for _,elements in enumerate(permutations(my_List,2)): print(elements) #(1, 2)#(1, 3)# ...#(5, 3)#(5, 4) 활용 문제https://school.programmers.co.kr/tryouts/85920/challenges?language=python3중복 순열 produc..

오늘은 파이썬 알고리즘 풀이에 자주 사용되는 딕셔너리 자료형에 대한 이야기를 해본다. 파이썬 기초 문법 공부를 할 때 분명히 배우고 넘어가는 영역이지만, 딕셔너리를 자유롭게 사용하기 위해서는 한번 정리를 해두고 문제풀이에 활용해보는것이 좋다. 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'] ..