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& ..
Level 2. 광물 캐기 우선순위 큐를 활용한 문제인 줄 알았는데, 그냥 완전 탐색 문제였다. 최소 비용을 반환하는 DFS 재귀 함수를 만들고, 5개씩 각 곡괭이로 캐보고 가장 적은 비용인 경우를 반환하면 된다. #include #include #include #include #include using namespace std; int calculate(int pick, size_t from, vector& minerals) { static unordered_map cost[3] = { {{"diamond", 1}, {"iron", 1}, {"stone", 1}}, {{"diamond", 5}, {"iron", 1}, {"stone", 1}}, {{"diamond", 25}, {"iron", 5}, {..
Level 2. 혼자서 하는 틱택토 정답률이 낮은 다른 Level 2 문제에 비해 굉장히 쉬운 편이다. 보드 크기가 3 x 3 고정이 아니었다면, 적절한 난이도였을 텐데 고정이어서 쉽게 풀 수 있었다. 우선 O, X의 개수를 세어 (O - X) 가 0 혹은 1이 아니면 잘못된 판이다. 그리곤 승리한 경우를 확인해, O가 승리한 경우 X의 개수는 1 작고, X가 승리한 경우 O의 개수는 같다. 이 조건을 만족하지 못해도 잘못된 판이다. 마지막으로 O와 X가 모두 승리한 경우도 잘못된 판이다. #include #include using namespace std; int solution(vector board) { int nO = 0, nX = 0; for (string& s : board) for (char..