선형 탐색 vs 이진 탐색 뭔가를 찾아야 할 때, '처음부터 하나하나 다 찾아보기 vs 필요 없는 거 반씩 거르면서 찾기' 둘 중에 뭘 고르겠냐고 하면 닥 두 번째다. 전자는 선형 탐색, 후자는 이진 탐색으로 시간 복잡도가 각각 O(N), O(logN)이다. 이진 탐색은 중간 지점의 값이 찾아야 할 값보다 작다면 오른쪽 반절을, 크다면 왼쪽 반절을 보면서 반씩 줄여나가며 원하는 값을 찾아내는 알고리즘이다. * 탐색에 대한 이해가 조금 부족하시다면 아래의 글을 참고해주세요! 2022.12.05 - [Algorithm/Algorithm] - [알고리즘] 파이썬으로 이진 탐색(Binary Search) 구현하기 [알고리즘] 파이썬으로 이진 탐색(Binary Search) 구현하기 서론 주어진 리스트에서 어떤 ..
Language/Python
for - else 구문 프로그래밍을 할 때 else는 if와 함께 오는 것이 국룰이다. 하지만 파이썬에서는 for문과도 함께 사용할 수 있는데, 이 포스팅에서는 문제를 풀면서 그 방법에 대해 알아보고자 한다. 아래의 문제는 프로그래머스의 파이썬을 파이썬답게 > flag OR for-else 문제이다. 위의 문제에서 핵심은 수를 곱해나가다가 제곱 수가 되는 게 하나라도 있다면 "found"를 출력하는 것이다. import math mul = 1 flag = False for _ in range(5): num = int(input()) mul *= num if int(math.sqrt(mul)) == math.sqrt(mul): flag = True break if flag: print("found") e..
우선순위 큐(Priority Queue)란? 스택은 가장 최근에 들어온 데이터를 꺼내고 큐는 가장 먼저 들어온 데이터를 꺼낸다. 그에 비해 우선순위 큐는 가장 우선순위가 높은 데이터를 먼저 꺼낸다. 이 말은 곧 내부적으로 데이터를 정렬된 상태로 갖고 있는다는 것인데, 이것을 보통 힙으로 구현해 삽입 O(logN), 삭제 O(logN)의 복잡도를 가진다. 사용법 - 임포트 queue 내장 모듈에서 PriorityQueue 클래스를 제공하므로 import 해서 사용하면 된다. from queue import PriorityQueue - 우선순위 큐 생성 PriorityQueue() 생성자를 이용해 우선순위 큐를 초기화할 수 있다. que = PriorityQueue() 이때, 디폴트 사이즈가 무한대로 생성되..
fractions fractions는 분수를 계산할 때 사용할 수 있는 모듈이다. 프로그래머스 코딩테스트 입문 > 분수의 덧셈 문제 1,2,3,4가 입력 되었을 때 1/2 + 3/4 = 5/4이므로 [5, 4] return (풀이) print(1/2 + 3/4) # 1.25 파이썬에서 유리수를 그냥 더하면 실수 형태로 결과값이 나온다. 우리가 원하는 정확한 유리수 연산을 위해서는 fractions.Fraction을 사용하면 된다. from fractions import Fraction Fraction을 사용하면 우리가 원하던 그 형태가 나온다. a = Fraction(1, 2) print(a) # 1/2 분자의 값은 numerator를 사용해 알 수 있다. print(a.numerator) # 1 분모의..
*의 역할 곱셈/거듭제곱 연산에 이용 반복 자료형을 확장하는 데에 이용 컨테이너 타입의 데이터 Unpacking 할 때 사용 가변인자 사용 시 Unpacking *는 우리가 흔히 아는 곱셈 외에 unpacking 역할을 하기도 한다. 컨테이너 타입의 데이터에서, 컨테이너를 풀어 각각의 값들로 만들어주는 것이다. 리스트 data = [1, 2, 3, 4, 5] print(data) # [1, 2, 3, 4, 5] print(*data) # 1 2 3 4 5 튜플 data = (1, 2, 3, 4, 5) print(data) # (1, 2, 3, 4, 5) print(*data) # 1 2 3 4 5 딕셔너리 data = {1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e'} print(d..
파이썬 math 모듈의 gcd, lcm gcd 함수 (최대공약수) 사용법 : math.gcd(숫자들) 매개변수로 0개부터 N개까지의 숫자들을 입력할 수 있다. 이전 버전에서는 두개의 숫자까지만 구할 수 있고, 최신 버전에서는 여러개의 최대공약수를 한 번에 구할 수 있다. from math import gcd print(gcd(20, 35))# 결과 : 5 lcm 함수 (최소공배수) 사용법 : math.lcm(숫자들) 매개변수로 0개부터 N개까지의 숫자들을 입력할 수 있다. * python 3.9 버전부터 사용 가능 from math import lcm print(lcm(20, 35))
덱(deque)이란? 큐를 양방향으로 쓸 수 있게 만든 자료구조다. 쉽게 말해, 큐와 스택의 연산이 모두 들어있는 자료구조라고 생각하면 된다. 양 끝 엘리먼트 모두에 대해 append와 pop이 가능하다. 파이썬에서는 collections라는 모듈에서 deque라는 클래스를 제공한다. 파이썬에서 큐를 사용할 때는 웬만하면 deque을 사용하는 것이 시간복잡도 상에서 훨씬 이득이다. 메서드 append(item) : item을 덱의 오른쪽 끝에 삽입 appendleft(item) : item을 덱의 왼쪽 끝에 삽입(== 스택의 push) pop() : 덱의 오른쪽 끝 요소를 리턴하는 동시에 삭제 popleft() : 덱의 왼쪽 끝 요소를 리턴하는 동시에 삭제 (== 큐의 dequeue) extend(lis..
파이썬의 정렬은 list.sort()와 sorted()가 있습니다. 기본적으로 리스트를 오름차순으로 정렬해주는데요. 내림차순으로 정렬해야하는 경우에는 다음과 같이 사용하면 됩니다. 📌 list.sort() 사용하는 경우 >>> l = [1, 2, 3, 4, 5] >>> l.sort(reverse=True) [5, 4, 3, 2, 1] 이 경우 원본 데이터가 변함에 유의해야합니다. 📌 sorted() 사용하는 경우 >>> l = [1, 2, 3, 4, 5] >>> r = sorted(l, reverse=True) >>> print(r) [5, 4, 3, 2, 1] 이 경우에 변수에 저장을 해줘야 한다는 점에 유의해야 합니다. * reverse = False를 입력하면 그냥 오름차순이 되는데 굳이 적을 필요..
