728x90 분류 전체보기279 [BOJ/Python] 12865. 평범한 배낭 📌 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 📌 문제 접근 방법 처음에는 가치가 큰 물건 별로 우선적으로 배낭에 넣는 방식으로 구현해보았으나 시간초과! 결국 구글링을 해보니 Knapsack Algorithm을 사용해야 하는 것이었다. 인덱스 에러가 나지 않도록 0번째 줄을 포함해서 2차원 배열을 생성한다. i 번째 물건을 가방에 넣었을 때 / 넣지 않았을 때의 최대 .. 2021. 10. 4. [Python] 진수 변환 10진수에서 변환 내장함수 사용 (bin, oct, hex) num = 19 print(bin(num)) # 2진수 print(oct(num)) # 8진수 print(hex(num)) # 16진수 # 0b10011 # 0o23 # 0x13 10진수로 변환 내장함수 사용 (int) print(int('0b10011', 2)) # 2진수 print(int('0o23', 8)) # 8진수 print(int('0x13', 16)) # 16진수 직접 함수로 만들어서 구현하기 def dec_to_base_x(num, base): result = [] while num: result.append(num%base) num //= base return ''.join(map(str, result[::-1])) num = .. 2021. 10. 3. [Algorithm] 힙 (Heap) 힙(heap) 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰/작은 노드를 찾기 위해서 만든 자료구조 힙의 키를 우선순위로 활용하여 우선순위 큐를 구현할 수 있음 최대 힙 (max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 > 자식 노드의 키 값} 루트 노드 : 키 값이 가장 큰 노드 최소 힙 (min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 {부모 노드의 키 값 < 자식 노드의 키 값} 루트 노드 : 키 값이 가장 작은 노드 삽입 연산 삭제 연산 힙에서는 루트 노드의 원소만을 삭제할 수 있음 루트 노드의 원소를 삭제하여 반환 힙의 종류에 따라 최대값 또는 최소값 구할 수 있음 2021. 10. 3. [Algorithm] Tree 트리 (Tree) 그래프 자료구조 중 하나 그래프와 트리의 차이점 싸이클 존재 여부 : 트리는 싸이클이 없다! 루트 노드가 반드시 하나 부모 노드가 반드시 하나 트리는 일반적인 경우, 암묵적으로 방향 표기x (단방향) 비선형 구조 : 원소들 간에 1 : n 관계 원소들 간에 계층관계를 가지는 계층형 자료구조 상위 원소에서 하위 원소로 내려가면서 확장되는 트리모양의 구조 용어 정리 트리 : 한 개 이상의 노드로 이루어진 유한 집합 부 트리 (subtree) : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리, 최상위 노드를 제외한 나머지 노드들은 분리집합으로 분리가능 -> 이는 각각 하나의 트리가 되며 (재귀적 정의) 루트의 부 트리 노드 (node) : 트리의 원소 (A, B, C, D, E, F, .. 2021. 10. 3. 이전 1 ··· 30 31 32 33 34 35 36 ··· 70 다음 728x90
