728x90 알고리즘141 [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. [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. [Algorithm] DFS, BFS 그래프 탐색 비선형구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요 두 가지 방법 깊이 우선 탐색 (Depth First Search, DFS) 너비 우선 탐색 (Breadth First Search, BFS) DFS (깊이우선탐색) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법 마지막에 만났던 갈림길의 정점으로 되돌아가서 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용 DFS 알고리즘 시작 정점 v를 결정하여 반문 정점 v에 인접한 정점 중에서 방문하지 않는 정점 .. 2021. 10. 3. 이전 1 ··· 21 22 23 24 25 26 27 ··· 36 다음 728x90
