Python

[python] 이진 탐색 트리 (binary Search tree) - 1. 클래스 정의, 초기화, 노드 추가

📗 이진 트리 (binary Search tree) 🔵 이진 탐색 트리 클래스 정의 및 초기화 먼저 Node 클래스를 정의해 보자. Node 클래스는 노드값인 self.val 와 왼쪽 노드 self.left 오른쪽 노드 self.right 의 속성을 가진다. 초기화 시 Node값만 주어지고 왼쪽, 오른쪽 노드는 비어있다. - 노드 구성 # 노드 만들기 # A(val) # / \ # B(left) C(right) class Node: def __init__(self, item): self.val = item self.left = None self.right = None Node 클래스를 만들었다면, BinaryTree 를 만들어보자. 처음에는 Node의 값이 없는, 노드 하나를 가진 트리로 초기화한다. -..

[python] 백준 - 9084. 동전

🤔문제 해결 1. S1 | 다이나믹 프로그래밍 2. target(만들어야 하는 금액)의 길이만큼의 리스트를 만든다. 3. 내가 가진 동전을 하나하나 꺼내서 리스트의 인덱스(내가 만들 수 있는 금액)과 비교하여 만들 수 있으면 카운트를 세어준다. 4. 위의 표 처럼 각 동전을 꺼냈을 때 미리 만들어진 금액(인덱스)에 꺼낸 동전을 더해서 값을 쌓는다. 💨 다이나믹프로그래밍은 한번 해결한 문제는 다시 해결하지 않는다. 그리고 작은 문제를 해결하여 큰 문제를 해결한다는 의미!!!!!!!!! DP는 항상 어렵다.... 💻소스 코드 def _dp(): dp = [0] * (target + 1) # 경우의 수를 업데이트 할 리스트 dp[0] = 1 for coin in coins: # print('꺼낸 동전: ',c..

[python] filter

📗 filter python의 built-in함수로 리스트나 딕셔너리같은 iterable한 데이터를 조건에 맞는 값만 추출할 때 사용하는 함수이다. 🔵 사용법 filter(function(함수), iterable(리스트나 딕셔너리등) 🔹 함수를 넣어 사용할 때 def func(x): if x % 2 == 1: return x lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] odd_lst = list(filter(func, lst)) print(odd_lst) # >>> [1, 3, 5, 7, 9] 🔹 lambda로 사용할 때 lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] odd_lst = list(filter(lambda x: x % 2 == 1, lst)) pr..

[python] defaultdict

📗 defaultdict defaultdict 는 dict 의 서브 클래스이다. 이름에서 유추할 수 있듯이 기본값(default)를 설정할 수 있는 좋은 친구이다. 🔵 defaultdict 이러한 번거로움을 없애주는게 바로 defaultdict이다. defaultdict는 처음 선언할 때 다양한 기본값을 지정할 수 있다. from collections import defaultdict my_defaultdict = defaultdict(int) print(my_defaultdict) # defaultdict(, {}) my_defaultdict = defaultdict(dict) print(my_defaultdict) # defaultdict(, {}) my_defaultdict = defaultdict..

[python] 백준 - 1309. 동물원

🤔문제 해결 1. S1 | DP 2. 사자가 없는 경우, 사자가 왼쪽에 있는 경우, 사자가 오른쪽에 있는 경우의 리스트를 만든다. 3. i번째에서 i-1번째에 사자의 상태에 따라 i번째의 경우의 수가 결정된다. (1) i번째에 사자가 없는 경우는 i-1번째에 사자가 왼쪽, 오른쪽 그리고 없어도 된다. (2) i번째에 사자가 왼쪽에 있는 경우는 i-1번째에 사자가 오른쪽에 있는 경우와 없는 경우만 가능하다. (i-1번째에 왼쪽에 있으면 i번째에서는 왼쪽에 있을 수 없다) (3) 오른쪽도 마찬가지 4. 경우의 수를 점차 더해나가면서 마지막 경우의 수를 다 더해준다. 💨 마지막에만 9901로 나누려고하면 메모리초과가 발생한다. 값을 쌓을 때 부터 나눠주면서 하자. 💻소스 코드 if __name__ == "__..

[python] 백준 - 1992. 쿼드트리

🤔문제 해결 1. 분할정복 | S1 2. 재귀함수를 이용했다 3. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 를 차례로 쪼개서 모두 1이나 0으로 이루어져 있는지 확인하고 4. 아닐 경우 다시 쪼개서 확인한다. 💨 맨 처음 배열이 모두 1인지 0인지 확인을 안해서 잠시 고민을 했던 문제!!! 답이 0이나 1이 될 수 있다 문제를 이해하는 것은 쉬우나 재귀함수를 사용했기 때문에 답을 출력하는게 힘들 수 있다. 맨 처음 함수에 들어왔다는 것은 하나의 묶음을 생성해야 하기 때문에 괄호를 사용해서 적절히 묶어준다.( 시작할 때 끝날 때) 💻소스 코드 from itertools import chain # 2중 리스트를 단일 리스트로 바꾸기 위해서 chain 함수 사용했음 def compression(lst)..