Algorithm123 [Swift][DP] 백준 14002 (가장 긴 증가하는 부분 수열4) 요구능력 : DP에 대한 이해 코드설명 : 첫번째로 가장 긴 증가하는 부분수열의 크기를 구해야하는데, 먼저 풀고오는 것을 추천한다. 이 문제에서 추가된 부분은 수열을 출력해주는것이다. dp에 우리가 저장한 수열 크기의 순서는 arr에 저장된 수열의 순서와 동일하다. 이게 무슨소린고 하면 아래 그림과 같다. 이거 처음에 나도 뭔소린가 했는데 밑에 var order = dp.max()! 부분부터 손디버깅 해보면서 써봐야 안다. 직접 생각하면서 써봐라. 참고로 아래 코드에서는 인덱스를 의도적으로 맞추지는 않았는데, dp값을 처음에 1로 초기화해놔서 정답이된다. (참고 : 어차피 배열의 뒤쪽에 있는 수가 큰 수 이므로 배열의 뒤쪽부터 찾아주는것이다.) 이제 이 인덱스가 같은점을 이용해서 문제를 푸는데, dp값이.. 2021. 10. 6. [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] 백준 1707번 (이분그래프) 요구능력 : DFS와 인접리스트와 이분그래프에 대한 이해 코드설명 : 이분그래프에 대해 알면 문제가 대충 보인다. 구글링하면 좋은자료가 많으니 구글링으로.. 일단 DFS와 BFS둘다 가능하다는데, 나는 DFS로 풀었다. 저번에도 비슷한문제를 푼적이 있는데, 이런식으로 간선에 대한 정보가 주어지는 DFS의 경우 인접리스트를 활용해줘야한다. 인접리스트를 하나씩 돌면서 방문하지 않은 노드에 대해서는 이전에 방문한 노드와 다른색을 지정해준다.(이분그래프의 특성) 그리고 이미 방문한 노드는 현재노드와 이전에 방문한 노드가 색이 같다면 그건 이분그래프가 아니므로 스위치(isColor)를 설정하여 NO를 프린트하도록 한다. 후기 : 이분그래프에 대해 이해하고 DFS를 잘 연계한다면 어렵지 않은 문제이다. 요즘 골드문.. 2021. 10. 2. [Swift][DFS] 백준 15657번 (N과M(8)) 요구능력 : DFS와 백트래킹에 대한 이해 코드설명 : N과M(7) 에서 비내림차순이 첨가되었다. 이전에도 비내림차순 관련문제가 있었는데, 이 문제는 시간적 효율성까지 따져서 막 풀다가는 시간초과에 걸리고 만다. 시간을 줄일 방법은 for문을 줄이는것이다. 줄인 방법을 설명하자면 다음과 같다. 4 2 9 8 7 1 예시를 이용해서 설명하자면, 원래대로라면 1 9 다음에 7 1이 나와야한다. 하지만, 비 내림차순이기 때문에 7뒤에는 7보다 작은 수가 나올 수 없다. 따라서, 이미 오름차순 정렬이 되어있는 arr배열의 for문의 시작을 이전 인덱스로 지정해주면 for문은 이전에 나온 수와 같거나 큰 수만 돌게된다. 그렇게되면 비 내림차순이 된다. 후기 : 예상치 못한 시간초과였다. 여태까지 푼 비내림차순은 .. 2021. 9. 30. 이전 1 ··· 10 11 12 13 14 15 16 ··· 31 다음
