본문 바로가기

자료구조와 알고리즘

(5)
냅색(knapsack) 알고리즘 가방 허용 무게가 정해서 있을 때 가방에 넣을 수 있는 물건들의 최대값을 구할 때. 최대 가치를 가지는 물건을 넣는 식으로 greedy 알고리즘으로 문제를 해결하려고 하면 해결 할 수 없다. ex ) 가방의 허용 무게 7kg. 물건들 (6kg 13) (4kg, 8) (3kg, 6) (5kg, 12) 일 때 (4kg, 8) (3kg, 6) 담는 경우가 정답인데 그리디 알고리즘으로 해결하려고 하면 (6kg 13) 나옴 분할가능 냅색 알고리즘 - 담을 물건이 소금 등 분할 가능 할 때 무게당 가치로 정렬하고 그리디 알고리즘을 수행하면 해결 가능 0-1냅색 알고리즘(분할 불가능) 담을 물건이 나누어 지지 않을 때 사용하는 알고리즘 DP 알고리즘으로 점화식 이용 2차원 리스트 L 를 만든다. (row : 물건 갯..
[python] 다익스트라 최단 경로 알고리즘 / 플로이드 워셜 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 기본적으로 그리디 알고리즘으로 분류됨 -> 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정 반복 알고리즘의 원리 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 위 과정에서 3과 4번을 반복한다. 그림으로 이해하는 다익스트라 알고리즘 출처 : https://www.youtube.com/watch?v=F-tkqjUiik0 방법 1. 구현하기 쉽지만 느리게 동작하는 코드 시간 복잡도는 O(V..
[python] 힙 구조 모듈 heapq 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 힙 함수 활용하기 heapq.heappush(heap, item) : item을 heap에 추가 heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) ) 최대 힙 만들기 파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다. IDEA: y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다. 힙에 원소를 추가할 때 (-item, ..
자료구조와 알고리즘 자료구조 자료구조는 말 그대로 자료(data)를 담는 구조이다. 자세히 말하면 컴퓨터 과학에서 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 책장을 예로 들어보면, 책장에 책을 꽂아 넣으려고 하는데 책을 알파벳 순서로 꽂아둘 것인지 아니면 책상에 쌓아 올려둘 것인지를 결정하는 것, 즉, 이런 데이터가 저장된 형태를 결정하는 것이 자료구조이다. 자료 구조의 분류 자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라 여러 가지 종류의 자료구조 중 하나를 선택할 수 있다. 자료구조의 종류로는 자료형의 따라 분류하는 단순 ..
[python] 너비우선탐색, 깊이우선탐색(bfs, dfs) 1. 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 출처 https://developer-mac.tistory.com/64 💡 깊이 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다. 2. 너비 우선 탐색 (BFS, Breadth-First Search) : 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동 출처 https://developer-mac.tistory.com/64 💡 너비 우선 탐색의 개념 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로, 시작 정점..