lv34 [Swift][프로그래머스][DP] N으로 표현 요구능력 DP 문제풀이 이 문제는 N을 이용해서 number를 만드는데 N을 최소개수로 사용해서 number를 만들때 몇개를 써야하는지를 묻는문제이다. DP를 생각하게된 이유? 카테고리가 DP로 분류되어있다. 예제를 보자. 12 = (55 + 5)/5 가 있다. 이게 5를 4번 사용한것이라고한다. 그렇다면 55는 5를 2번사용했다는 말이되는데, (55 + 5)는 5를 3번 사용한것이다. DP문제를 조금 풀어봤으면 감이 올것이다. 현재 이 식은 dp[4] = dp[3] + dp[1]과 같은 형태구나 라는것을.. 사실, dp는 다른 알고리즘 문제들과는 조금다르게 감각(?)이 필요한 문제같다. 그래서 다양한문제를 많이 접해봐야하는데, 만약 이런감이 안잡힌다면, DP문제를 많이 풀어보기를 추천드립니다. 이 문제.. 2022. 5. 2. [Swift][프로그래머스][그래프] 가장 먼 노드 요구능력 넓이우선탐색(BFS) + 그래프 문제풀이 항상 그래프문제에서는 간선이 주어지면 인접리스트를 만들어야된다. 나는 graph 프로퍼티에 2차원배열로 인접리스트를 만들었다. 이렇게 만들면 graph[1] = [2, 3]과 같이 1번노드는 2번과 3번과 연결되어있다고 저장할 수 있다. 여기서 1번노드를 타고 2번노드를 들어가면 그대로 1번이 또 있게된다. 이 부분은 visited로 방문처리를 함으로써 재방문하지 않게해줄것이다. 문제에서 최단경로로 이동해야된다고 했다. 최단경로하면 가장 먼저 생각나는 알고리즘은 BFS이다. BFS를 사용해서 노드를 탐색하는데, 1번노드에서 가장 먼 노드의 개수를 찾아야되므로, maxCount변수에 가장 먼 거리를 저장해줬다. moveCntArr에는 거리에있는 노드를 구해.. 2022. 5. 2. [Swift][프로그래머스][DFS] 네트워크 요구능력 : DFS 재귀 코드설명 : 네트워크가 따로따로(?)있는게 몇개인지 구하는 문제이다. 예를 들어서 1번과 2번이 연결되어 있고 3번은 따로있으면 네트워크는 2개이다. 만약 1번과 2번과 3번이 모두 연결되어있지 않으면 네트워크는 3개이다 1번과 2번과 3번이 모두 연결되어있으면 네트워크는 1개이다. 나는 우선 연결그래프를 만들어주었다. 이렇게 노드의 개수와 연결된 간선이 주어지는 경우에는 연결그래프를 만들어주고 문제를 푸는게 좋다. 만약 입출력 예의 1번같은 경우에는 graph에 다음과 같이 들어갈 것이다. graph = [[0,1], [0,1], [2]] 나는 노드를 0번부터 세어주었다. 그래서 0번노드는 0번과 1번이 연결되어있고, 1번노드도 0번과 1번이 연결되어있고, 2번노드는 2번 자신.. 2022. 3. 15. [Swift][누적합][LV_3] 파괴되지 않은 건물 요구능력 : 누적합 코드설명 : 카카오테크블로그에 정말 설명이 쉽게 잘되어있습니다. 사실상 똑같은 유형의 문제를 접해보지 않는이상 이 문제는 풀기 어려운것같습니다. 누적합을 공부하고 이 문제를 풀어보면서 너무 많이 돈다고 생각했는데, 알고보니 변화하는 부분을 한번에 다 체크해주고 누적합을 한번에 구하는것이었습니다. 후기 : 개념을 알고있으면 쉬운문제인데 개념을 모른다면 효율성테스트를 절대 통과할 수 없다. func solution(_ board:[[Int]], _ skill:[[Int]]) -> Int { let n = board.count let m = board[0].count var count = 0 var preArr = Array(repeating: Array(repeating: 0, count.. 2022. 2. 24. 이전 1 다음