나른한코딩_

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

문제링크 https://programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 문제 요약 두 수의 최소공배수란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. n개의 수의 최소공배수는 n개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니니다. n개의 숫자를 담은 배열 arr가 입력되었을 때 이 수들의 최소공배수를 반환하는 함수를 완성. - arr의 길이는 1이상 ..

** 작성자가 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(..

오늘은 DFS와 BFS의 예제를 구현해보며 로직을 이해해보고자 합니다. DFS와 BFS를 구현하려다보니, 그래프를 먼저 구현하는 해야겠더라구요🤔 그런데 그래프를 어떻게 구현해야할지 몰라서 우선은 하드코딩으로 그래프를 생성한 후, DFS / BFS를 구현해보았습니다. 다음 글에 그래프 구현에 대한 글을 올려두겠습니다 😄 DFS와 BFS의 개념을 간단하게 소개한 후 바로 코드로 넘어가겠습니다. . . . . 그래프를 탐색하는 방법에는 크게 DFS와 BFS가 있습니다. 1. DFS (Depth-First Search) '깊이우선탐색(DFS)'은 가장 깊은 노드까지 내려단 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동하여 탐색을 합니다. root 노드(혹은 다른 임의의 노드)에서 시작하여 다른 branch..

알고리즘 문제를 풀 때, 수학적으로는 생각이 나는데 코드로 생각이 안날 때! 참고하면서 익히려고 적는 글입니다. 계속 추가될 예정입니다! Factorial(!) 수학적 정의: 자연수의 계승 또는 팩토리얼은 그 수보다 작거나 같은 모든 양의 정수의 곱이다. 수식: func factorial(_ n: Int) -> Int { var n = n var result = 1 while n > 1 { result *= n n -= 1 } return result } *👩🏻‍🏫 : 재귀로도 작성해보자. func factorialRecursion(_ n: Int) -> Int { if n==0 { return 1 } return n * factorialRecursion(n - 1) } 순열(Permutation) 수학..

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