목차 knapsack 문제는 무게 제한이 있는 가방에, 무게 제한을 지키면서도 배낭에 담긴 물건의 가격의 합이 가장 큰 경우를 알아내는 문제이다. 이런 배낭 문제를 푸는 다양한 방법을 소개할 것이다. 그리디한 방식과 그 한계 일반적인 동적 계획법과 개선된 버전 backtracking - dfs 그리고 BFS를 이용한 분기 한정법 (dfs 보다 더 나을게 없다.) 이를 개선한 Best First Search를 이용한 분기 한정법! 이렇게 5가지 방식을 소개할 것이다. 1. 배낭 문제와 그리디한 풀이 knapsack 문제는 배낭에 물건을 채우는 문제이다. 보통 물건들의 무게와 그 가격이 정해져 있는 상황이 주어지고, 최대 이득이 되는 만큼 물건을 채워야 하는 문제이다. 배낭은 감당할 수 있는 무게의 상한이 ..
[자료구조] 트라이 트라이는 기본적으로 문자열의 구성 character를 노드로 만든 만든 트리입니다. 전처리 과정이 매우 헤비한 대신, 탐색이 매우 빠릅니다. 문자열에서 이어지는 문자의 시퀀스에 따라 새로운 노드를 만들어 다음 문자를 넣어주고 또 그 노드에 다음 철자의 노드를 만들어 주는 식으로 진행합니다. 이렇게 해주면 접두사가 겹치는 문자열들에 대해 빠른 탐색이 가능하겠죠? 포인트는 문자열 끝의 구분인데, 노드에서 bool이나 다른 여러 장치를 이용해서 현재 노드가 어떤 문자열의 끝 문자임을 알리는 기능을 만들어야합니다. 이를 통해 어떤 문자열이 실제로 존재하는지 파악 할 수 있습니다. 트라이는 정말 정말 빠른 시간 내에 탐색을 진행 할 수 있습니다. 실제로 거의 탐색을 안 하는거나 마찬가지입니다...
[백준 130505] 두 수 XOR [백준 130505] 두 수 XOR 두 수 XOR은 최대 1,000,000,000의 숫자들 10만개가 주어지고 그 중 XOR이 가장 큰 두 쌍의 XOR연산값을 2초 안에 구하는 문제이다. 당연히 수가 10만개가 되기 때문에 직접 XOR 연산을 해준다면 (10만^2/1억) 초 정도의 시간이 소요되기 때문에 시간초과가 된다. 해당 연산에 트라이를 적용하면 더 빠른 연산이 가능해진다. 기본적으로 이진수 연산을 위해 모든 수를 이진수 문자열로 만들어 준 후, 그 수들로 트라이를 만들어 준다. 이후 모든 수들로 한번 더 탐색을 진행해준다. 이진수 XOR연산은 두 수가 같으면 0, 다르면 1을 결과로 갖는다. 넣어줬던 수들을 또 트라이에서 탐색하되, 지금 탐색중인 문자 (0 or..
1. About Map map은 제가 그리 자주 쓰는 자료구조는 아니지만, IT기업 코딩테스트 대비 과정에서 생각보다 Set과 Map의 이용이 잦았고, 정리가 필요함을 느껴 이렇게 정리하게 되었습니다. (굳이 굳이 굳이 직접 해시 함수를 만들어서 테이블을 이용하곤 했습니다.) map은 자료를 유일한 key와 하나의 value 쌍으로 저장하는 자료구조입니다. 정확히는 각 노드가 key, value 쌍으로 이루어진 'Tree'구조를 띄고 있습니다. key와 value의 타입은 서로 다를 수 있으며, 일반 map은 key 값을 오름차순 정렬하여 저장합니다. 이는 간단한 테스트를 통해 확인 할 수 있습니다. 위와 같이 내부적으로 key를 정렬하는 것을 확인할 수 있습니다. 그래서 수행 속도가 중요시 되는 테스트..
C++에서 코드로 input 파일을 열 때 freopen함수를 쓰려고 하면 IDE에 따라 freopen_s를 쓰라고 귀찮게 할 때가 있다. 그럴때는 ifstream을 쓰는게 낫다. 코드는 아래와 같다 fstream을 include하고 아래와 같이 ifstream cin; cin.open("파일명"); 을 써주면 된다. 물론 인풋 파일은 소스코드 파일과 같은 폴더에 있어야한다. 위에 ios::sync_with_stdio(false); cin.tie(NULL);도 같이 적어주면 좋은데, cin의 속도를 줄여준다. (입력 속도를 줄여준다) 보통 입력을 이렇게까지 해서 불러오는 경우는 입력의 용량이 클 때이니 같이 적어주면 좋다요. 필요에 따라 cout내용도 많다면 cout도 적어주어서 속도를 줄여주면 되겠다.
벨만-포드 알고리즘(Bellman-Ford Algorithm)은 그래프 탐색의 최단거리 알고리즘 중 하나입니다. 잘 알려진 다익스트라, 플로이드-마샬 알고리즘과 달리 벨만-포드 알고리즘은 음수 가중치를 가진 그래프의 최단 경로를 찾아낼 수 있습니다. 또한 최단 거리 알고리즘에서 치명적인 음수 사이클의 존재도 알아차릴 수 있게 해줍니다. (짱짱 👍👍👍) 이 알고리즘은 저에게 조금 신선하고 재밌는 알고리즘이였습니다. 처음엔 이해도 잘 안 가서 고생했습니다 ㅠㅠ 그래서 제 딴에서는 이해하기 쉽게 알려드리고 싶지만 잘 되려나 모르겠습니다. 벨만-포드 알고리즘의 특징과 구현, 그리고 문제를 풀며 얻은 팁들을 소개해드리려 합니다. 잘 부탁드립니다. 🙏🙏🙏 (gd 스타일 ㅋ) 일단, 이 알고리즘의 특징은 기존의 그래..
다익스트라 알고리즘은 최단 경로 알고리즘 중에 가장 기초가 되는 알고리즘입니다. 🏃🏃 그동안 최단거리를 구할 때 죽어라고 BFS를 이용해왔으나(제일 재밌는걸요), 가중치가 있는 상황에서는 항상 풀이가 까다로웠습니다. 저는 이제까지 BFS의 다음 노드 탐색 과정에서 가중치가 더 적은 노드의 탐색을 단순히 '코드 상으로 더 위쪽에' 작성함으로서 먼저 탐색하도록 했습니다. 이는 나름 괜찮은 방법이였지만, 당연히 한계가 있었습니다. 이럴 때 사용 할 수 있는 것이 '최단 경로 알고리즘'입니다. 가중치가 더 적은 쪽을 우선적으로 탐색하도록 하는 알고리즘이죠. 1. 다익스트라 알고리즘: 가중치가 있는 그래프 탐색의 최단 경로 찾기. 셋 중에 가장 빠름! 2. 벨만-포드 알고리즘: 음수 가중치가 있는 그래프 탐색의 ..
https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net [백준 5719] 거의 최단 경로 (platinum 5) 거의 최단 경로 문제는 최단경로를 제외한 경로들 중 가장 짧은 경로를 찾아 그 길이를 출력하는 문제입니다. 최단 경로를 알아내는 과정이 여러번 필요할 것으로 예상되므로, 최단 경로 알고리즘 중 저에게 가장 익숙한 다익스트라 알고리즘으로 풀어보겠습니다. (저는 그래프 관련 알고리즘 중에 다익스트라가 제일 재미있는..
16933번: 벽 부수고 이동하기 3 (acmicpc.net) 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net [백준 16933] 벽 부수고 이동하기 3 (gold 1) 위 문제는 벽 부수고 이동하기 1, 2를 푼 이후에 풀어보는 것을 추천합니다. 벽뿌이 1, 2에서 새로운 요소가 추가된 문제들이기 때문입니다. 벽뿌이 3은 벽뿌이 1, 2에서 '가만히 있을 수 있는' 기능과, 낮과 밤의 개념이 추가되었습니다. 위 두가지 기능을 어떻게 구현하였는지를 중점으로 설명하겠습니다. 일..
