- [ 코딩테스트/프로그래머스 ][프로그래머스] 타겟 넘버(Swift)2024-08-22 16:45:45난이도: Level 2 사용 알고리즘: DFS index를 돌면서 모든 경우의 수들 중 sum이 target과 일치하면 되는 문제였다.그림(못남)처럼 dfs로 모든 경우의 수를 따라가도록 하였다. import Foundationfunc solution(_ numbers:[Int], _ target:Int) -> Int { var count = 0 func dfs(idx: Int, sum: Int) { if idx == numbers.count && sum == target { count += 1 return } if idx + 1
- [ 코딩테스트/백준 ][백준/BOJ] 1520번 내리막 길(Swift)2024-08-18 21:22:15문제 난이도: 골드 3 사용 알고리즘: DFS, DP M,N은 각각 500 이하이고 최대 250,000까지 연산이 필요하다.제한 시간은 2초이므로 200,000,000번(2억번)의 연산이 넘어가게 되면 시간초과가 된다. 대충 O(N^4)을 넘지 않으면 시간초과는 뜨지 않는다. 첫번째 풀이는 DFS에 백트래킹을 적용해서 문제풀이를 진행했다.다만 백트래킹을 적용하게 되면 셀의 모든 방향에 대하여 재귀 호출이 발생하여 시간초과가 뜬다.import Foundationlet size = readLine()!.split(separator: " ").map { Int($0)! }let y = size[0]let x = size[1]var map: [[Int]] = []var visited = Array(repeati..
- [ 코딩테스트/백준 ][백준/BOJ] 2468번 안전 영역(Swift)2024-08-15 22:24:57문제 난이도: 실버 1 사용 알고리즘: DFSimport Foundationlet n = Int(readLine()!)!var map: [[Int]] = []var heights = Set()var sortedHeights = [Int]()let directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]var visited = Array(repeating: Array(repeating: false, count: n), count: n)var mapCount = 0var result = 0for _ in 0 ..= n || y = n || map[y][x] i { dfs(x: x, y: y, height: i) mapCoun..
- [ 알고리즘 ][알고리즘] DFS(Depth-First-Search, 깊이 우선 탐색)2024-08-13 15:07:20DFS란? 그래프 탐색 알고리즘으로 그래프의 모든 정점(vertex)을 깊이 탐색하는 방법(알고리즘) DFS는 시작 정점에서 인접한 정점들을 방문하고, 인접 정점들의 인접 정점을 방문하는 방식으로 동작한다.BFS와 다르게 하나의 경로를 깊이(끝)까지 탐색한 후에야 다른 경로로 되돌아와 탐색을 진행한다. 표현 방법// 인접 리스트1 - [2, 8]2 - [1, 3, 6, 7]3 - [2, 4, 5]4 - [3, 5]5 - [3]6 - [2]7 - [2]8 - [1, 9]9 - [8]// 인접 행렬 1 2 3 4 5 6 7 8 91 [0 1 0 0 0 0 0 1 0]2 [1 0 1 0 0 1 1 0 0]3 [0 1 0 1 1 0 0 0 0]4 [0 0 1 0 1 0 0 0 0]5 [0 0 1 1 0 0..
- [ 자료구조 ][자료구조] 트리(Tree)2024-08-13 12:29:41트리란?트리는 그래프의 일종으로 계층적인 구조를 가지며 노드(Node)로 구성된다.각 노드는 데이터를 포함하고, 다음 노드들과 연결될 수 있다. 용어루트 노드(Root)- 부모가 없는 트리의 최상위 노드- 트리는 하나의 루트 노드 가짐 부모 노드(Parent)- 자식 노드를 가지는 노드로 상대적 개념- 2의 부모 노드는 1- 4의 부모 노드는 2 자식 노드(Child)- 부모 노드로 부터 가리켜지는 하위 노드- 1의 자식 노드는 2, 3- 2의 자식 노드는 4, 5 리프 노드(Leaf)- 자식 노드가 없는 트리의 말단 노드- 4, 5, 6이 해당 형제 노드(Sibling)- 같은 부모를 가지는 노드- 2, 3은 1을 부모 노드로 둔 형제 노드 레벨(Level)- 트리의 각 노드가 어느 깊이에 위치하는지 ..
- [ 자료구조 ][선형 자료구조] 덱/데크(Deque)2024-08-12 15:06:52덱(Deque)이란?덱(Deque)은 큐와 스택의 특성을 모두 가지는 자료구조이다.일반적인 큐와 달리, 덱은 양쪽 끝에서 삽입과 삭제가 가능하다. - 양쪽 끝에서의 삽입/삭제: 덱은 양쪽 끝에서 삽입과 삭제가 가능하며, 이로 인해 여러 가지 패턴의 자료처리가 가능합니다.- FIFO와 LIFO: 덱은 큐처럼 FIFO(First-In-First-Out) 방식으로도 동작할 수 있고, 스택처럼 LIFO(Last-In-First-Out) 방식으로도 동작할 수 있습니다. 구현class Deque { private var enque: [T] private var deque: [T] = [] var isEmpty: Bool { return enque.isEmpty && deque.i..
- [ 자료구조 ][선형 자료구조] 큐(Queue)2024-08-12 14:39:39큐(Queue)란?FIFO(First In First Out)으로 가장 먼저 삽입된 요소가 가장 먼저 제거되는 구조를 가진다.큐의 주요 연산으로는 Enqueue와 Dequeue가 있다. Enqueue - O(1)큐의 뒤쪽에 새로운 요소를 추가하는 연산 Dequeu - O(1)큐의 앞쪽에서 요소를 제거하고 반환하는 연산 사용 사례iOS GCD는 작업 수행을 위해 큐를 제공한다.UI 업데이트의 경우 메인 스레드에서 이루어져야 하기 때문에, GCD의 메인 큐를 사용하여 먼저 들어온 작업부터 처리하게 된다. 종류기본 큐 (Simple Queue)선입선출(FIFO, First In First Out) 방식으로 요소를 처리한다.원형 큐 (Circular Queue)배열의 끝과 시작이 연결된 형태로, 큐의 뒤쪽에서 ..
- [ 자료구조 ][선형 자료구조] 스택(Stack)2024-08-12 13:39:47스택이란?LIFO(Last In First Out)으로 가장 마지막으로 삽입된 요소가 가장 먼저 제거되는 구조를 가진다.이러한 특징을 가진 스택은 Push와 Pop을 기본 연산을 가지게 된다. Push데이터를 스택 맨 위에 쌓는 연산 Pop스택 맨 위에 데이터를 제거하고 반환하는 연산 사용 사례iOS에서 실제로 UINavigationController는 Push, Pop을 통해 뷰컨트롤러들의 스택을 관리하며 화면을 나타낸다. 그 외에도 DFS를 사용할 때 깊이 탐색을 위해 Stack을 사용하여 재귀 호출을 대체할 수 있다. 구현struct Stack { private var elements: [T] = [] init() { } mutating func push(_ element: ..