본문 바로가기

728x90

백트래킹3

[Swift] 프로그래머스 위클리 챌린지 피로도 Problem 코딩테스트 연습 - 피로도 XX게임에는 피로도 시스템(0 이상의 정수로 표현합니다)이 있으며, 일정 피로도를 사용해서 던전을 탐험할 수 있습니다. 이때, 각 던전마다 탐험을 시작하기 위해 필요한 "최소 필요 피로도"와 던 programmers.co.kr Solution 해당 문제는 백트래킹으로 풀어야 하는 문제입니다. (혹시 백트래킹을 모르시는 분들은 여기 에서 보고 와주세요!) answer를 0부터 탐험을 시작해줍니다. func solution(_ k:Int, _ dungeons:[[Int]]) -> Int { var answer:Int = 0 explore(dungeons: dungeons, answer: &answer, k:k, count: 0) return answer } 던전들을 .. 2021. 12. 10.

[Algorithm] 백트래킹(Backtracking)이란? (feat. 예제포함) 안녕하세요 Foma 💻 입니다! 오늘은 프로그래머스 N-Queen 문제를 풀면서 해당 문제가 백트래킹 문제라는 것을 알게 되었는데요. 그래서 백트래킹이 무엇이고 어떻게 구현해서 사용해야 하는지에 대해 정리해보려고 합니다. 바로 시작할게요~ 백트래킹이란? 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만,.. 2021. 8. 28.

[Swift] 프로그래머스 N-Queen Problem 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr Solution 해당 문제는 백트래킹(DFS)으로 풀어야 하는 문제입니다. 1. 각 행마다 퀸을 놓을 수 있는 위치를 체크한다. 각 행마다 퀸은 하나씩밖에 못놓으므로 현재 행의 열들에 공격할 수 있는 퀸이 있는지 체크합니다. 만약 공격할 수 있는 퀸이 없다면 현재 위치를 history(퀸의 위치를 저장하는 2차원 배열)에 저장해놓고 다음 행으로 진행합니다. 이렇게 진행하면서 가장 마지막 행까지 도달한 경우는 배치할 수 있는 경우이므로.. 2021. 8. 28.

이전 1 다음

728x90

티스토리툴바