본문 바로가기

728x90

DFS11

[Swift] 2022 KAKAO BLIND RECRUITMENT 사라지는 발판 Problem 코딩테스트 연습 - 사라지는 발판 [[1, 1, 1], [1, 1, 1], [1, 1, 1]] [1, 0] [1, 2] 5 [[1, 1, 1], [1, 0, 1], [1, 1, 1]] [1, 0] [1, 2] 4 programmers.co.kr Solution 해당 문제는 완전 탐색으로 풀 수 있는 문제입니다. 1. 플레이어의 위치와 게임 끝났을 때 움직인 횟수와 승자를 알려줄 구조체를 만든다. struct Location { var x:Int,y:Int } struct GameResult { var count:Int,isWinnerA:Bool } 2. board의 가장 자리를 0으로 감싸준다. Index out of range 오류를 쉽게 피하기 위해서 입니다. func wrapBoard.. 2022. 1. 20.

[Swift] 2022 KAKAO BLIND RECRUITMENT 양과 늑대 Problem 코딩테스트 연습 - 양과 늑대 [0,0,1,1,1,0,1,0,1,0,1,1] [[0,1],[1,2],[1,4],[0,8],[8,7],[9,10],[9,11],[4,3],[6,5],[4,6],[8,9]] 5 [0,1,0,1,1,0,1,0,0,1,0] [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]] 5 programmers.co.kr Solution 해당 문제는 완전탐색과 DFS로 풀어야 하는 문제입니다. 1. edge를 이용해 부모와 자식을 연결해줍니다. func connectEdge(_ edges:[[Int]]) { for edge in edges { if pc[edge[0]] == nil { pc[edge[0]] = [edg.. 2022. 1. 19.

[Swift] 2022 KAKAO BLIND RECRUITMENT 양궁대회 Problem 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr Solution 해당 문제는 DFS 및 완전탐색 문제입니다. 1. 각 점수마다 이길지 질지를 결정한다. 10점부터 1점까지 어피치를 이길 수 있는지를 판별합니다. 만약 이길 수 있다면 해당 점수를 얻는 방법과 그냥 0발을 쏴서 다른 점수를 얻을 방법을 택합니다. DFS를 사용해서 이기는 경우와 그냥 0발을 쏘고 다음 단계로 넘어갈 경우 2가지를 재귀해줍니다. func dfs(leftArrow:Int,depth:Int,history:[Int],info:[.. 2022. 1. 19.

[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.

[Swift] 프로그래머스 위클리 챌린지 9주차 전력망을 둘로 나누기 Problem 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr Solution 1. 전선망의 연결 정보를 connect 이중배열을 만들어서 저장한다. var connect = Array(repeating: Array(repeating: false, count: n+1), count:n+1) wires.forEach { connect[$0[0]][$0[1]] = true connect[$0[1]][$0[0]] = true } 2. 연결된 전선을 하나씩 잘라보며 왼쪽과 오른쪽의 갯수를 세주고 최솟값과 비교합니다. 우선 최솟값을 .. 2021. 10. 7.

[Swift] 2020 KAKAO INTERNSHIP 경주로 건설 Problem 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr Solution 해당 문제는 DFS로 풀어야 하는 문제입니다. 1. 자동차와 상하좌우 방향 모델을 만들어준다. (필수는 아님) 자동차에 필요한 x,y,price,prev와 상.. 2021. 8. 31.

[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.

[Swift] 2019 카카오 개발자 겨울 인턴쉽 불량 사용자 Problem 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr Solution 1. 불량 사용자와 유저 아이디를 비교한다. func isEqual(userId:String,bannedId:String) -> Bool { if userId.count != bannedId.count { return false } let uid = userId.map{String($0)} let bid = bannedId.map{String($0)} for (i,b) in bid.enumerated() { if b != "*" &.. 2021. 6. 26.

[Algorithm] 깊이 우선 탐색(DFS,Depth-First-Search)이란? (feat.Swift) 안녕하세요 Foma 👟 입니다! 오늘은 알고리즘 문제에서 엄청 빈번하게 출제되고 알아두면 정말 유용한 DFS에 대해서 알아보도록 하겠습니다. 바로 시작할게요! DFS란? "깊이 우선 탐색은 맹목적 탐색 방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다." - 위키 백과 - 이게 뭔말이야....;;; 쉽게 예제를 통해서 설명드리겠습니다. 아래 사진과 같이 지구 안에 세 나라만 있고 모든 나라와 나라의 도시들을 탐색한다고 가정하겠습니다. 어떤 사람은 "난 먼저 어떤 나라들이 있는지 부터 확인하고 그 나라 안에 있는.. 2021. 6. 5.

[Swift] 프로그래머스 월간 코드 챌린지 2 모두 0으로 만들기 Problem 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr Solution 1. 0으로 만들 수 있는 트리인지 확인하기 각 가중치의 모든 합이 0이라면 0으로 만들 수 있는 트리입니다. 만약 0으로 만들 수 없다면 -1을 반환합니다. (canMakeZero 함수를 참고해주세요!) 2. 각 정점마다 부모와 자식을 세팅하기 각 edges에 연결된 정점들을 서로 부모와 자식으로 설정합니다. (setChildren 함수를 참고해주세요!) 3. DFS로 리프 노드 찾기 0부터 시작해 0과 연결된 .. 2021. 6. 2.

이전 1 다음

728x90

티스토리툴바