나른한코딩_

개념 BFS (Breath First Search) 너비 우선 순회 queue로 구현 (queue를 활용하기 때문에 FIFO) 장점 : 최적해를 찾을 것을 보장한다 ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현 후, 짱구와 철수 사이의 관계 경로를 찾는 경우 BFS : 짱구와 가까운 관계부터 살핀다 DFS : 지구 상 모든 관계를 다 살펴봐야할지도,, 로직 시작 노드를 큐에 삽입하고 방문처리 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입 후 방문처리 (방문하면 현재 위치는 pop해주고 방문처리 -> 방문할 곳은 queue에 넣음) DFS (Depth First Search) 깊이 우선 순회 stack과 재귀 함수로 구현 두 노드 사이의 최단 경로 혹..

Trie 문자열 검색 문제에 특화된 트리 형태의 자료구조. 원하는 문자열을 O(m) (m = 문자열의 길이) 시간복잡도로 찾을 수 있다. struct Trie 내의 Trie 포인터 배열을 가지고 해당 키에 맞는 포인터로 이어지는 구조. Trie는 검색 후보 문자열을 하나의 트리로 만들어서, 한번의 검색 O(m) 만으로 문자열의 존재 여부를 검색 가능하다. 주의 항상 첫번째 root 노드는 빈칸이다. 트라이 객체마다 트라이 포인터 배열을 경우의 수만큼 가져야 하므로 공간복잡도가 매우 커질 수 있다. 공간복잡도 : O(key의 경우의수 * 포인터 크기 * 전체 트라이에 존재하는 노드 수) 필수 1) 다음 두 가지를 가지고 있어야 한다. - child (자식 노드를 담는 배열) - isTerminal (어떤 ..

** 작성자가 stack / queue를 연습하면서 작성한 기록을 남긴내용입니다. 나중에 자세한 설명가 추가 내용을 작성하며 수정할 예정입니다. ** Stack - LIFO, array로 구현 - 다양한 자료형을 수용할 수 있도록 generic을 이용 - push, pop 메서드의 경우 구조체 내부에서 데이터를 수정하기 때문에 mutating 키워드를 사용. struct Stack { var stack = [T]() var isEmpty: Bool { return self.stack.isEmpty } var top: T? { return self.stack.last } mutating func push(_ item: T) { self.stack.append(item) } mutating func pop(..

정수 배열을 파라미터로 주었을 때 버블 정렬한 배열을 리턴해주는 함수이다. import Foundation var randomArr = Array(1.. [Int] { var arr = array for _ in 0.. [Int] { var arr = array var flag: Bool for i in 1..