Level 3. 부대복귀 전형적인 다익스트라 문제이다. 특정 지점에서 다른 지점까지의 최단 거리를 구할 때, 다익스트라를 사용한다. 이때 음수 가중치가 존재한다면, 벨만-포드를 사용한다. 벨만-포드는 음수 사이클을 확인할 때도 사용한다. 모든 지점 간의 최단 거리를 구할 때는 플로이드-워셜을 사용한다. 그 외에, 최소 신장 트리(MST)를 구할 때는 크루스칼을 사용한다. #include #include #include #define UNREACHABLE 200000 using namespace std; vector solution(int n, vector roads, vector sources, int destination) { vector answer; queue que; vector adj(n + 1..

Level 2. 이모티콘 할인행사 이모티콘의 개수가 다행이 7개 이하여서, 그냥 모든 할인율의 조합을 구해 풀라는 문제이다. 조합은 시작점과 레벨이 핵심인데, 이 문제에선 중복 조합이므로 레벨만 DFS 함수에 전달하면 된다. 이후, 이모티콘 플러수 가입자수를 키로 하고 최대 판매액을 값으로 하는 map을 만들어 계산하면 된다. #include #include #include #include using namespace std; void rDFS(int depth, vector& comb, vector& result) { if (comb.size()

Level 2. N-Queen 백트래킹(Backtracking)과 DFS(Depth-First Search) 1. 백트래킹? DFS? 백트래킹과 DFS는 어떻게 보면 분리하기가 애매한 개념이다. 굳이 분리해서 의미를 부여하자면 끝까지 가느냐 돌아오느냐로 간단하게 생각해볼 수 있다. DFS 역시 재귀를 통해서 kwanik.tistory.com DFS를 시도하다가 무조건 시간 초과가 날 것 같아서 다른 방법을 찾아봤더니 백트래킹이 있었다. 익히 들어봤지만 이름이 뭔가 어려울 것 같아서 공부하지 않고 있었는데, 그닥 어려운 개념은 아니었다. 간단히 말하면 조건부 DFS이다. DFS는 조건에 상관 없이 모든 경우를 탐색하기 때문에 시간이 많이 걸린다. 백트래킹은 조건을 확인해, 유망한(Promising) 경우 ..

Level 3. 스티커 모으기(2) [프로그래머스 lv3] 스티커 모으기(2) (DP 풀이) Summer/Winter Coding(~2018) 문제입니다. 문제 설명 N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어 latte-is-horse.tistory.com DP 문제라는 생각은 들었지만, 막상 풀이가 바로 떠오르지는 않았다. DP 문제에서는 DP 테이블의 의미를 정확히 아는 것이 중요하다. 이 문제에서는 i번째까지 스티커를 때었을 때 최댓값을 저장한다. 처음에는 2가지를 고려해야 한다. 첫 번째 스티커를 뜯고 시작하거나, 뜯지 않고 시작하거나 진행하면서는 2가지를 고려한다. i번째 스티커를 뜯거나, ..

Level 3. 경주로 건설 생각보다 엄청 쉬운 DFS 문제였는데, 길이가 아니라 비용이 추가되어 있어 좀 헷갈렸다. 단순 방문 여부를 저장하는 visited 배열로는 안 되고, 자신에게 온 4개 방향마다 비용을 저장해야 한다. 비용이 양수이므로, 이전보다 큰지를 통해 재방문 여부를 확인할 수 있는 게 핵심이다. 다음 칸으로 진행할 때 진행 방향을 전달하고, 왔던 방향과 같으면 100을, 다르면 600을 더해 전달하면 된다. 왔던 방향으로 다시 돌아가는 경우에도 600을 전달하면 알아서 재방문으로 처리되므로 문제 없다. DFS 문제일 것이라고 생각은 했지만, 이렇게 단순무식하게 모든 경우의 수를 탐색해야 하는지는 몰랐다. #include #include #include #include #include u..

Level 3. 보석 쇼핑 투 포인터 문제였다. 첫 시도에서 앞에서부터가 아니라 뒤에서부터 진행시켜서 조금 헷갈렸었다. 해시 테이블을 통해 보석 종류와 개수를 저장하고, 모든 보석이 포함된 경우 앞에서부터 1개씩 빼주면 된다. 그리고 최소 길이를 별도로 관리해 더 짧은 경우 정답을 갱신해주면 된다. 최소 길이를 변수로 관리할 생각도 못했어서 좀 헷갈렸었는데, 변수를 잘 활용하는 습관을 들이자. #include #include #include using namespace std; vector solution(vector gems) { vector answer; unordered_map umap, current; size_t n = gems.size(); int minLen = n; for (string& ..