백준177 [Swift][DP] 백준 1912번 (연속합) 요구능력 : DP에 대한 이해 코드설명 : 이 문제에서 만들어 놓은 함정에 빠지고 문제를 풀 수 없었다.. 함정은 바로 음수를 빼는 조건을 거는것이다. 음수포함해서도 연속값이 큰값이 나올 수 있다. 만약 음수를 빼는 조건을 거셨다면, 2번째 예제에서 14가 안나올것이다. 일단, 이 문제는 문제이름대로 dp에 연속적으로 합을 누적시킨다고 생각하면 된다. dp[0] = arr[0] 을 해준 이유는 dp[0]에는 arr[0]만 누적된거다. dp[1] = max(arr[1], dp[0] + arr[1]) dp[2] = max(arr[2], dp[1] + arr[2]) . . 이런식으로 값을 계속해서 누적 시킨다. max를 쓰는 이유는 값의 누적이 쓸모없어졌을 순간, 바로 현재 값이 이전에 (누적된 값 + 현재값.. 2021. 10. 5. [Swift][DFS] 백준 10971번 (외판원 순회 2) 요구능력 : DFS에 대한 이해 코드설명 : 문제의 입력에는 4 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0 가 적혀있다. 나처럼 이해못하는 사람을 위해서 해석해보자면, 도시가 4개 있는데, 1번도시는 1번에서 1번가는데 비용이 0 1번에서 2번가는데 비용이 10 1번에서 3번가는데 비용이 15 1번에서 4번가는데 비용이 20 이런식이다. 문제를 이해하고, 이 부분을 본다면 DFS와 인덱스를 이용해서 접근해야겠다고 생각이 든다. 1. 우선 입력을 쭉 받아놓는다. let n = Int(String(readLine()!))! var w: [[Int]] = Array(repeating: [], count: n) for i in 0.. 2 -> 2 -> 3 -> 1 이런식으로 자기자신을 .. 2021. 10. 4. [Swift][DFS] 백준 1707번 (이분그래프) 요구능력 : DFS와 인접리스트와 이분그래프에 대한 이해 코드설명 : 이분그래프에 대해 알면 문제가 대충 보인다. 구글링하면 좋은자료가 많으니 구글링으로.. 일단 DFS와 BFS둘다 가능하다는데, 나는 DFS로 풀었다. 저번에도 비슷한문제를 푼적이 있는데, 이런식으로 간선에 대한 정보가 주어지는 DFS의 경우 인접리스트를 활용해줘야한다. 인접리스트를 하나씩 돌면서 방문하지 않은 노드에 대해서는 이전에 방문한 노드와 다른색을 지정해준다.(이분그래프의 특성) 그리고 이미 방문한 노드는 현재노드와 이전에 방문한 노드가 색이 같다면 그건 이분그래프가 아니므로 스위치(isColor)를 설정하여 NO를 프린트하도록 한다. 후기 : 이분그래프에 대해 이해하고 DFS를 잘 연계한다면 어렵지 않은 문제이다. 요즘 골드문.. 2021. 10. 2. [Swift][BFS] 백준 13913번 (숨바꼭질 4) 요구능력 : BFS에 대한 이해 코드설명 : "이게틀려?" 를 많이 시전한 문제이다. 이 문제를 풀기전에 숨바꼭질부터 풀고오자. 숨바꼭질에서 달라진점은 지나온경로를 찾는것이다. 지나온경로는 코드에서 visited배열에 저장해줬다. 방문처리와 동시에 경로를 저장했다. 이렇게 안해주고 배열을 따로 추가하면 메모리초과가난다. 경로추가하는 부분은 아래 주석처리를 해두었다. 1. 메모리초과 => 크기가 100001인 배열 3개를 만들어서 메모리초과가 났다. => 아, 참고로 경로를 찾기위한 배열(아래코드에선 visited)에 초기값을 0으로 세팅하면 당연히 메모리 초과가 난다. => 이유는 2 * x에 0이들어가면 0인걸 참고하면 된다. 2. 컴파일에러 처음에 n을 방문처리해줬는데, 방문처리를 하면 코드가 꼬이게.. 2021. 10. 2. 이전 1 ··· 23 24 25 26 27 28 29 ··· 45 다음
