본문 바로가기

Algorithm236

[Swift][DP] 백준 5557번 (1학년) 요구능력 DP(메모이제이션) 문제설명 이론적으로 설명을 아주 잘 정리 해놓으신 분이 계신데 추천드립니다. https://everenew.tistory.com/34 [백준] No.5557 - 1 학년 (C++) 문제 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 everenew.tistory.com 후기 DP는 많이 풀어보는게 답이고, 다양한 풀이법을 계속해서 반복해야한다. 코드 let n = Int(String(readLine()!))! var arr = readLine()!.split(separator: " ")... 2022. 3. 21.
[Swift][알고리즘][꿀팁] Queue 구현하기 Queue 따로 구현해야 하는 이유? 보통 우리가 Swift에서 Queue를 구현 할 때는 하나의 배열에서 removeFirst()를 이용해 앞에서 빼고 append()를 이용해 뒤로 넣는 방식으로 구현합니다. 하지만, removeFirst()의 경우에는 O(n)의 시간복잡도를 갖기 때문에 많은 양의 원소가 왔다갔다하는 Queue에서 아주 비효율적입니다. (저는 초반에 큐를 이용하는 BFS문제들에서는 시간초과가 안나오다가 갈수록 모든 문제에서 시간초과가 발생하더라구요!) 자, 우선 전체 코드를 한번 읽어보세요! 보통 일반적인 경우에는 큐를 push, pop, empty()정도만 사용하는 것 같아서 저는 3가지만 간단하게 구현해보았습니다. 아래 코드를 완벽하게 이해하기 위해서 Swift Generic T와.. 2022. 3. 21.
[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][DFS] 백준 1248번 (맞춰봐) 요구능력 : DFS 재귀 코드설명 : 일단 문제를 이해해야하는데,, 예제입력 1에 적혀있는 -+0++++--+로 예를 들어 설명해보자. 규현이가 쓴 수가 A[]라는 배열에 4개가 저장되어 있다고 가정해보면 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합이 음수, 양수, 0으로 구분되어 저장되는 것이라고 보면된다. 예제 출력1처럼 -2 5 -3 1일 때 A[0]의 합, A[0] ~ A[1]의 합, A[0] ~ A[2]의 합, A[0] ~ A[3]의 합을 직접해보면 -+0+가 나오는걸 알 수 있다. 이후에도 A[1]의 합, A[1] ~ A[2]의 합, ... 이렇게 구해보면 문제에서 뭘 구해야하는지 이해가 갈것이다. 나는 처음에 result배열에 그냥 평범.. 2022. 3. 15.

티스토리툴바