연습17 [Swift][BFS] 백준 2206번 (벽 부수고 이동하기) 요구능력 : BFS && 그리디(?) 코드설명 : 처음에 문제를 읽고나서 벽을 1개 부수는게 어떻게 부숴야 최소값이 나오지..라고 당황했다. 내가 생각한 이 문제에서의 핵심 1. 큐마다 벽을 부쉈는지 안부쉈는지를 체크해준다. bfs로 탐색해주면 어차피 모든곳을 탐색하면서 최단경로를 찾기때문에 1을 부쉈는지 여부만 체크해주고 안부쉈는데 앞에 1이있으면 부수고 큐에 부쉈다는 표시를 해주고 다음거부터 안부수면 된다. 2. 벽을 부수고 방문한것인지 벽을 부수지 않고 방문한것인지를 체크해줘야한다. 저는 이 부분을 생각안하고 풀어서 11%에서 틀렸습니다. 백준 문제해결에서 찾은 반례이다. 6 4 0000 1110 0110 0000 0111 0000 위 예제를 보고 예를 하나 들어보면 맨 처음 시작지점을 (0,0)이.. 2022. 1. 3. [Swift][DFS] 백준 16929번 (Two Dots) 요구능력 : DFS응용 코드설명 : 문제를 보면 똑같은걸 연속해서 찾는것(?) 이므로 깊이우선탐색으로 풀리는 문제이다. 이 문제에서의 핵심 1) 각각의 점이 들어있는 칸이 변을 공유한다.(상하좌우로 이동가능하다.) 2) dk와 d1이 인접해야한다. d1은 맨 처음에 방문하는 점인데 결국, dk까지 방문해서가면 d1은 이미 방문처리 되어있지만 dk에서 이동가능한 점이라서 맨 마지막에 확인이 가능하다. 1. 변수선언 및 입력 좀 복잡하게 입력받은거 같은데 입력받은줄을 for문을 이용해 캐릭터배열로 넣어서 2차원 캐릭터배열로 옮긴것이다. let nm = readLine()!.split(separator: " ").map{Int(String($0))!} let n = nm[0] let m = nm[1] var .. 2021. 12. 31. [Swift][DP] 백준 12865 (평범한 배낭) 요구능력 : DP문제풀이능력 코드설명 : 문제에 대한 설명은 다른 블로그를 참고했는데 여기 보다 잘 설명할 자신이없어서 소개드립니다. 내가 이해한걸 그대로 적어보면 우선 이 dp문제는 2차원dp이다. 처음에 1차원으로 풀어보려다가 뭔가 1차원으로 푸는게 말이안되는 느낌이 들어서 2차원으로 풀기시작하다가 풀이를봤다. 그런데 역시나 2차원으로 풀리는 dp문제는 표를 그려서 푸는게 가장 이상적인것같다. 이곳에 표를 그려서 푸신 분이 계신다. 내가 가장헷갈렸던 부분은 이 중 for문안에 첫번째 조건인 if j >= items[i - 1][0] 부분인데 왜 저렇게 작은 수부터 시작하지 싶었지만 이 문제는 dp이고 j는 배낭무게이기 때문에 배낭무게에 따라 최대값을 구해주는게 맞는거였다. 그리고 dp[i][j] = .. 2021. 12. 28. [Swift][BruteForce] 백준 2003번 (수들의 합 2) 요구능력 : 반복문의 활용 코드설명 : 이 문제는 수를 연속해서 더해줘야된다는게 핵심이다. 연속해서 더해주다가 원하는 수가 나오려면 시작지점이 계속해서 바뀌는 방법이 있다. 예제 10 5 1 2 3 4 2 5 3 1 1 2 를 보면 5가 나오려면 2 + 3, 5, 3 + 1 + 1이 나와야 한다. 1에서 시작하면 뒤에 아무리 더해도 5가 안나온다. 2에서 시작하면 2 + 3이되서 5가된다. 3에서 시작하면 다음에 4를 더하니 불가능하다. . . 5에서 시작하면 5니까 뒤에 안더해도 나왔다. 3에서 시작하면 3 + 1 + 1이니까 5가 나온다. . . 이렇게 풀면된다. 후기 : 간만에 간단한문제를 푼거같다. let nm = readLine()!.split(separator: " ").map{Int(Stri.. 2021. 12. 28. 이전 1 2 3 4 5 다음