목차 knapsack 문제는 무게 제한이 있는 가방에, 무게 제한을 지키면서도 배낭에 담긴 물건의 가격의 합이 가장 큰 경우를 알아내는 문제이다. 이런 배낭 문제를 푸는 다양한 방법을 소개할 것이다. 그리디한 방식과 그 한계 일반적인 동적 계획법과 개선된 버전 backtracking - dfs 그리고 BFS를 이용한 분기 한정법 (dfs 보다 더 나을게 없다.) 이를 개선한 Best First Search를 이용한 분기 한정법! 이렇게 5가지 방식을 소개할 것이다. 1. 배낭 문제와 그리디한 풀이 knapsack 문제는 배낭에 물건을 채우는 문제이다. 보통 물건들의 무게와 그 가격이 정해져 있는 상황이 주어지고, 최대 이득이 되는 만큼 물건을 채워야 하는 문제이다. 배낭은 감당할 수 있는 무게의 상한이 ..
[자료구조] 트라이 트라이는 기본적으로 문자열의 구성 character를 노드로 만든 만든 트리입니다. 전처리 과정이 매우 헤비한 대신, 탐색이 매우 빠릅니다. 문자열에서 이어지는 문자의 시퀀스에 따라 새로운 노드를 만들어 다음 문자를 넣어주고 또 그 노드에 다음 철자의 노드를 만들어 주는 식으로 진행합니다. 이렇게 해주면 접두사가 겹치는 문자열들에 대해 빠른 탐색이 가능하겠죠? 포인트는 문자열 끝의 구분인데, 노드에서 bool이나 다른 여러 장치를 이용해서 현재 노드가 어떤 문자열의 끝 문자임을 알리는 기능을 만들어야합니다. 이를 통해 어떤 문자열이 실제로 존재하는지 파악 할 수 있습니다. 트라이는 정말 정말 빠른 시간 내에 탐색을 진행 할 수 있습니다. 실제로 거의 탐색을 안 하는거나 마찬가지입니다...
1. About Map map은 제가 그리 자주 쓰는 자료구조는 아니지만, IT기업 코딩테스트 대비 과정에서 생각보다 Set과 Map의 이용이 잦았고, 정리가 필요함을 느껴 이렇게 정리하게 되었습니다. (굳이 굳이 굳이 직접 해시 함수를 만들어서 테이블을 이용하곤 했습니다.) map은 자료를 유일한 key와 하나의 value 쌍으로 저장하는 자료구조입니다. 정확히는 각 노드가 key, value 쌍으로 이루어진 'Tree'구조를 띄고 있습니다. key와 value의 타입은 서로 다를 수 있으며, 일반 map은 key 값을 오름차순 정렬하여 저장합니다. 이는 간단한 테스트를 통해 확인 할 수 있습니다. 위와 같이 내부적으로 key를 정렬하는 것을 확인할 수 있습니다. 그래서 수행 속도가 중요시 되는 테스트..
벨만-포드 알고리즘(Bellman-Ford Algorithm)은 그래프 탐색의 최단거리 알고리즘 중 하나입니다. 잘 알려진 다익스트라, 플로이드-마샬 알고리즘과 달리 벨만-포드 알고리즘은 음수 가중치를 가진 그래프의 최단 경로를 찾아낼 수 있습니다. 또한 최단 거리 알고리즘에서 치명적인 음수 사이클의 존재도 알아차릴 수 있게 해줍니다. (짱짱 👍👍👍) 이 알고리즘은 저에게 조금 신선하고 재밌는 알고리즘이였습니다. 처음엔 이해도 잘 안 가서 고생했습니다 ㅠㅠ 그래서 제 딴에서는 이해하기 쉽게 알려드리고 싶지만 잘 되려나 모르겠습니다. 벨만-포드 알고리즘의 특징과 구현, 그리고 문제를 풀며 얻은 팁들을 소개해드리려 합니다. 잘 부탁드립니다. 🙏🙏🙏 (gd 스타일 ㅋ) 일단, 이 알고리즘의 특징은 기존의 그래..
다익스트라 알고리즘은 최단 경로 알고리즘 중에 가장 기초가 되는 알고리즘입니다. 🏃🏃 그동안 최단거리를 구할 때 죽어라고 BFS를 이용해왔으나(제일 재밌는걸요), 가중치가 있는 상황에서는 항상 풀이가 까다로웠습니다. 저는 이제까지 BFS의 다음 노드 탐색 과정에서 가중치가 더 적은 노드의 탐색을 단순히 '코드 상으로 더 위쪽에' 작성함으로서 먼저 탐색하도록 했습니다. 이는 나름 괜찮은 방법이였지만, 당연히 한계가 있었습니다. 이럴 때 사용 할 수 있는 것이 '최단 경로 알고리즘'입니다. 가중치가 더 적은 쪽을 우선적으로 탐색하도록 하는 알고리즘이죠. 1. 다익스트라 알고리즘: 가중치가 있는 그래프 탐색의 최단 경로 찾기. 셋 중에 가장 빠름! 2. 벨만-포드 알고리즘: 음수 가중치가 있는 그래프 탐색의 ..
