오늘은 파이썬을 통해 완전 탐색을 하는 방법에 대해 알아본다. 완전 탐색의 방법으로 단순한 brute force와, 순열의 활용, BFS/DFSk에 대해서 알아본다. Brute Force for문과 if문을 활용하여 모든 가능한 경우를 검사하는 방법이다. 코테에서 brute force는 사실 많이 나오는 풀이방법은 아니지만, 풀이 과정에서 간단하게 활용할 수 있다. 순열의 활용 파이썬으로 순열을 사용하는 방법은 아래의 포스팅에 소개되어있다. https://he-kate1130.tistory.com/70 [python] "코테"를 위한 기초 파이썬 (5) - 순열, 조합, 중복 순열, 중복 조합 파이썬에서는 iterpools라이브러리에서 순열과 조합, 중복 순열과 중복 조합에 대한 메서드를 제공하고 있다...
[Algorithm] Daira i Noor
이분탐색 문제에 대해 알아보자. Binary Search 이분탐색은 기본적으로 탐색하려는 대상이 정렬되어있다는것이 가정된다. 즉, 정렬된 상태의 데이터를 효율적으로 탐색하기 위한 방법이다. 탐색 대상 리스트의 가장 중간지점을 확인하고, 타겟이되는 값이 오른쪽, 왼쪽에 있을지 판단하여 점차 탐색대상을 절반으로 줄여나간다. 이분탐색의 시간 복잡도는 O(logN)이다. 기존의 순차탐색이 O(N)임 기억한다면 정렬된 상태에서는 이분탐색을 활용하는것으로 상당히 빠르게 문제를 해결할 수 있다는 것을 알 수 있다. 만약 이분탐색을 사용하고자 한다면, 먼저 정렬된 데이터인지 꼭 확인 후에 탐색해야 한다. 정렬되어있지 않다면 경우에 따라 순차탐색과 같은 다른 방법이 더 효율적일 수 있다. def binarySearch(..
파이썬에서는 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]*10 for i in range(10): arr[i] = i 즉 우리는 선언과, 값 할당을 분리해서 사용한다. List Comprehension은 이 과정을 한번에, 한 줄로 가능하게 한다. 기본적인 문법은 다음과 같다 [ (변수를 활용하여 만들 값) for (변수 명) in (순회가능한 값)] 사용예시 #가장 기본적인 형태 one_list = [i for i in range(10)] # if else문을 사용해볼 수 있다...
최근 알고리즘 문제풀이를 Python으로 푸는 비율이 높아지고 있어서 코딩테스트에 주로 사용하는 기본적인 파이썬 코드에 대해서 기록한다. 입력 먼저 기본적인 input reading과 unpacking에 대해서 알아본다. 파이썬 기초 문법을 공부할때 많이 사용하는 input() 그런데 사실 파이썬으로 코테준비를 하다보면 이 함수는 점점 사용하지 않게 될 것이다. input()을 사용할 경우에 파이썬에서는 입력받은 것을 문자열로 변환하고, 추가 처리(strip...)을 수행하기 때문에 입력이 많아지는 경우에는 시간초과가 매우 빈번히 나타나는 코드이기 때문이다. sys.stdin.readline 오잉 그러면 입력을 어떻게 받나요 ?? 우리는 sys의 스탠다드 인풋- stdin을 사용한다. 이를 사용하려면 s..
