코딩테스트90 [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. [Swift][BruteForce] 백준 15658번 (연산자 끼워넣기 (2)) 요구능력 : 재귀함수 코드설명 : 내가 처음에 시간초과가 났던 코드는 문자열에 모든 연산자를 집어넣고 그 연산자를 백트래킹하면서 모든 경우의수를 다 세보는 코드다. 처음에는 연산자끼워넣기랑 똑같이 풀었다. 그러다 블로그를 서칭하던중에 내가 쓴 코드가 범위를 한참초과해서 시간초과가 난다는것을 알게되었다. 수의 개수는 최대 11개까지 들어온다. 그럼 연산자의 개수는 한번의 연산에 최대 10개를 쓸 수 있다. 그리고 연산자는 최대 4N개가 주어지니까 44개에서 10개를 뽑으면 44C10이 되고, 이걸 정렬하는 데는 연산자의 개수만큼 걸리니 44C10 * 10이 나온다. 그럼 시간초과가 나게된다. (다른분들은 다 11이라고 적으셧던데 저는 10이라고 생각해서 10으로 적었습니다. 틀렸다면 이유좀 댓글로 부탁드립.. 2021. 12. 27. 이전 1 ··· 18 19 20 21 22 23 다음
