Koo's.Co

bisect 라이브러리에 있는 bisect_left, bisect_right에 대해 공부하려 합니다. 1. bisect? - 정렬된 리스트에서 이진 탐색을 이용해 데이터를 찾는 메서드를 제공 - O(logN)의 시간 복잡도로 데이터를 찾을 수 있다 - bisect_left는 lower bound로, bisect_right는 upper_bound로 사용할 수 있다 2. lower bound와 upper bound bisect 라이브러리에서 제공하는 메서드는 이진 탐색과 완전히 일치하지는 않고 조금 차이점이 있다. 위에서 말한 것처럼 bisect_left는 lower bound 알고리즘을, bisect_right는 upper bound 알고리즘을 수행한다. - binary search: 찾고자 하는 값이 존..

Python을 공부하면서 Bitwise 연산자를 사용할 일이 많지 않아 논리 연산자와의 차이점을 잘 몰랐는데 알고리즘 문제를 풀며 공부할 기회가 생겨 정리를 해보려 한다. 1. 논리 연산자와 bitwise 연산자의 값 비교 1) 홀수인 경우 AND, OR 연산 # AND 연산, & 연산 print(21 and 1) # 1 print(21 and 0) # 0 print(21 & 1) # 1 print(21 & 0) # 0 # OR 연산, | 연산 print(21 or 1) # 21 print(21 or 0) # 21 print(21 | 1) # 21 print(21 | 0) # 21 2) 짝수인 경우 AND, OR 연산 # AND 연산, & 연산 print(20 and 1) # 1 print(20 and ..

(오늘 게시물에서 사용하는 AND, OR 연산자는 모두 Bitwise 연산자를 의미한다.) 홀수와 짝수를 판단할 때 2로 나눈 나머지를 이용해 판단할 수도 있지만 Bitwise 연산자를 이용해서 구하는 방법도 있다. 1. 2의 나머지를 이용한 홀수, 짝수 판단 num = int(input()) if num % 2 == 0: # 짝수인 경우 print("Even") elif num % 2 == 1: # 홀수인 경우 print("Odd") 2. Bitwise 연산자를 이용한 홀수, 짝수 판단 - Bitwise 연산자를 이용해 홀수와 짝수를 판단하려면 우선 AND연산과 XOR연산에 대해 알아야 한다. ① AND 연산자(&) 0 1 0 0 0 1 0 1 정수를 2진수를 이용해 나타내면 짝수인 경우 마지막 자리가..

1. 우선순위 큐 - 우선순위 큐는 각 원소들이 우선순위를 갖고 있는 추상 자료형이다. - FIFO 구조를 갖는 큐와 다르게 우선순위 큐는 들어온 순서와 상관없이 우선순위가 높은 원소가 먼저 나간다. - 원소를 추가하거나 제거할 때 우선순위를 갖고 수행해야 한다. - 우선순위 큐와 힙은 같지 않다. 우선순위 큐는 힙 외에도 배열이나 연결 리스트로도 구현 가능하다. - 배열을 이용해 우선순위 큐를 구현하면 삽입할 때 최악의 경우 시간 복잡도가 O(N)이 된다. (추가하는 위치 이후에 있는 모든 원소들을 뒤로 한 칸씩 옮겨줘야 하기 때문에) - 연결리스트로 구현할 때도 삽입 위치를 찾을 때 최악의 경우 O(N)이 소요되기 때문에 배열이나 연결 리스트보다는 힙을 이용한 우선순위 큐가 훨씬 효율적이다. 2. 힙..

1. 힙? - 힙은 최댓값이나 최솟값을 하기 위해 사용되는 완전 이진트리 형태의 자료구조이다. - 부모 노드는 항상 자식 노드보다 더 높은 우선순위를 가진다. - 힙은 완전 이진트리로 정렬된 구조가 아니다. - 부모 노드가 자식 노드보다 항상 작은 힙을 최소 힙, 부모 노드가 자식 노드보다 큰 힙을 최대 힙이라 한다. - 형제 노드 간의 대소 관계가 보장되는 이진 탐색 트리와 다르게 힙은 형제 노드 간의 대소 관계는 보장되지 않는다. - 힙은 부모 노드와 자식 노드 간의 대소 관계만을 보장한다. - 우선순위 큐와 힙은 다른 개념이다. 우선순위 큐는 각 원소들이 우선순위를 갖는 추상적인 자료형으로 여러 방법으로 구현할 수 있는데 그중에서 힙을 많이 사용하는 것이다. 2. 최소 힙과 최대 힙의 비교 파이썬에..

1. 이진탐색? - 이진탐색은 정렬되어 있는 선형자료구조에서 사용할 수 있는 탐색 방법이다. - 정렬되지 않은 자료형의 경우 처음부터 차례대로 값을 비교해야하기 때문에 O(N)의 시간복잡도를 갖는다. - 반면 자료가 정렬되어 있는 경우 이진탐색을 통해 O(logN)의 시간복잡도로 값을 찾을 수 있다. - 이진탐색은 범위를 주면 해당 범위 중간값을 기준으로 찾고자 하는 값이 중간값보다 큰지 작은지를 판단하는 방법이다. - ex) 책에서 원하는 페이지 번호를 찾으려 할 때 일단 책을 펴고 찾고자 하는 페이지 번호가 더 작으면 앞부분을, 찾고자 하는 페이지 번호가 더 크면 뒷부분을 보는 것과 같다. 2. 이진탐색 알고리즘 - 찾고자 하는 값을 target이라 한다 - 리스트 nums가 주어지면 가장 작은 인덱..

이진 탐색 트리를 구현하기에 앞서 기본적인 트리의 구현을 해보려 한다. 오늘 구현할 트리는 별도의 기능을 갖지 않고 트리의 순회를 중점적으로 보려 한다. 순회란 트리를 돌면서 어떤 원소가 있는지 확인하는 작업을 말한다. 이 때 어느 원소를 먼저 보는지에 따라 순회의 종류가 달라진다. 트리의 순회는 재귀 방법으로 쉽게 구현할 수 있다. 위의 트리를 코드로 구현해 보자 1. 트리의 구조 class Node(object): def __init__(self, item): self.item = item self.left = self.right = None class BinaryTree(object): def __init__(self): self.root = None - Node class에서 item원소는 루트(..

1. 행/열의 추가 1) 행의 추가 - DataFrame의 loc() 메서드를 이용해 행을 추가 - DataFrame.loc['새로운 행 이름'] = value or List - value를 전달할 경우 해당 행에 모두 동일한 값이 들어간다 - List를 전달할 경우 행에 값이 차례로 들어간다 - 전달되는 리스트의 개수는 열의 개수와 동일해야 한다 ① 값의 추가 df = pd.DataFrame([[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]], index=list('xyz'), columns=list('ABCDE')) df.loc['v'] = 30 print(df) ② 리스트의 추가 df.loc['w'] = [16, 17, 18, 19, 20] pri..

1. DataFrame? - 행과 열로 만들어지는 2차원 배열 구조의 자료형 - 행을 index, 열을 columns, 값을 values로 갖는다 df = pd.DataFrame([[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15]], index=list('xyz'), columns=list('ABCDE')) print('index: ', df.index) print('columns: ', df.columns, end='\n\n') print('values: ', df.values, end='\n\n') print('dtypes: ', df.dtypes) 2. DataFrame의 생성 1) Dictionary를 인자로 받는 경우 - Dictionary의 k..