본문 바로가기

Languages/Python

 (7)
[Python] 이분 탐색 [이분탐색 개념] 정렬되어 있는 배열에서 데이터를 찾을때, 처음부터 끝까지 데이터를 탐색하는 순차 탐색과는 달리 데이터를 절반으로 줄여가며 탐색하는 알고리즘이다. 예를들어, 책에서 127p를 찾을려고 할때 먼저 책의 아무 페이지나 펼친다. 만약 100p를 펼쳤다고 하면 이제 100p 이후에서 원하는 페이지를 찾는다. 이렇게 특정 값의 왼쪽과 오른쪽 중에 한 곳을 탐색하는 방법이 이분탐색이다. 보통 특정 값은 배열의 중간에 위치한 값을 사용한다. [코드] def binary_search(a,x): start = 0 end = len(a) -1 while start x : end = mid - 1 else: start = mid + 1 d = [1,2,4,6,8,13,35,60] print(binary_se..
[Python] 트리 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조다. 정점(node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한다. [트리의 용어] 루트노드(root node) : 부모가 없는 최상위 노드 단말노드(leaf node) : 자식이 없는 노드 크기(size) : 트리에 포함된 모든 노드의 개수 깊이(depth) : 루트 노드부터의 거리 높이(height) : 깊이 중 최댓값 차수(degree) : 각 노드의 (자식 방향) 간선 개수 기본적으로 트리의 크기가 N일때, 전체 간선의 개수는 N-1개 이다. [이진 탐색 트리] 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종이다. 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 를 만족시킨다. [트리의 순회]..
[python] 투 포인터(Two Pointers) 알고리즘 코딩테스트를 풀다보면 투 포인터로 풀어야하는 문제들을 자주 볼 수 있습니다. 오늘은 투 포인터 알고리즘에 대해 알아봅시다. [투 포인터(Two Pointers) 알고리즘] 리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 시작점과 끝점 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 위 그림과같이 두 개의 포인터(점)의 위치를 기록하면서 처리한다. [시간복잡도] O(N) 매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝난다. 각각 배열 끝에 다다르는데 O(N)이라 둘을 합해도 여전히 O(N)이다. [예제] 백준 3237 두 수의 합이 투 포인터의 예제입니다. ht..
정규표현식 re/compile/파이썬 정규표현식은 특정한 규칙을 가진 문자열의 집합을 표현하는데 사용하는 형식 언어이다. 정규 표현식에서 사용하는 메타 문자는 다음과 같다. . ^ $ * + ? { } [ ] \ | ( ) 문자 클래스 [ ] [ ] 사이의 문자들과 매치 ex) [abc] -> a,b,c 중 한 개의 문자와 매치 "a" : a가 있으므로 매치 "before" : b가 있으므로 매치 "dude" : a,b,c 중 하나도 포함하고 있지 않으므로 매치되지 않음 [ ] 안의 두 문자 사이에 '-' 사용하면 문자 사이의 범위를 의미한다. ex) [a-c] = [abc] , [0-5] = [012345] [a-zA-Z] : 알파벳 모두 [0-9] : 숫자 문자 클래스 [] 안에서 ^ 메타 문자를 주의해야한다. ^를 사용하면 반대라는 의..
힙 / 힙큐(heapq) 힙 특정한 규칙을 가지는 완전 이진 트리로 최댓값과 최솟값을 찿는 연산을 빠르게 하기 위한 자료구조이다. A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립 최소 힙 : 부모 노드의 키값이 자식 노드의 키 값보다 항상 작은 힙 최대 힙 : 부모 노드의 키값이 자식 노드의 키 값보다 항상 큰 힙 파이썬에서는 heapq를 제공한다. 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2)보다 작거나 같은 최소 힙의 형태로 정렬된다. import heapq heapq.heappush(heap,item) # item을 heap에 추가 heapq.heappop(heap) # heap에서 가..
파이썬 스택, 큐 파이썬에서 스택과 큐를 사용하는 방법을 알아봅시다!! 스택(Stack) - 나중에 넣은 데이터가 먼저 반환되도록 설계한 메모리 구조 - Last In First Out (LIFO) - 데이터의 입력은 Push ( append() ), 출력은 Pop ( pop() ) 큐(Queue) - 먼저 넣은 데이터가 먼저 반환되도록 설계한 메모리 구조 - First In First Out (FIFP) - 데이터의 입력은 Push ( append() ), 출력은 Pop ( pop(0) ) 큐에서 pop(0)을 하면 앞에서 하나를 비우고 뒤에 있는 모든 데이터들을 한칸씩 앞으로 당기는 작업을 한다. 따라서 시작 복잡도가 O(n)이 걸린다. (너무 느림!!) from collections import deque # (*d..
Hash(해시) Hash? key와 Value로 이루어진 데이터 구조를 의미한다. 파이썬에서는 딕셔너리 타입이 해시 테이블과 같은 구조이다. 장점 데이터 저장/검색 속도가 빠르다. 해시는 키에 대한 데이터가 있는지 확인이 쉽다. 단점 일반적으로 저장공간이 좀더 많이 필요하다. 여러 키에 해당하는 주소가 동일할 경우 충돌을 해결하기 위한 별도 자료구조가 필요하다. 시간복잡도 일반적인 경우(충돌이 없는 경우) : O(1) 최악의 경우(모든 경우에 충돌이 발생하는 경우) : O(n)

티스토리툴바