분류 전체보기

🕸️ 다익스트라 알고리즘그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.각 정점을 방문하면서 그 정점에 도달하는 최소값을 갱신해주는 방식이다. 다음 정점을 선택할 때 시작정점으로부터 가장 짧은 거리의 정점을 방문해야 한다.🔥 Swift 구현실제 구현은 아래와 같다. 다익스트라의 시간 복잡도는 O(V^2 + E)인데, 그것을 표현하고 싶어 아래와 같이 표현했다.struct Edge { var d: Int var w: Int}func dijkstra(graph: [[Edge]], start: Int) -> [Int] { var distances = Array(repeating: Int.max, count: graph.count) var visited = Array..

🥸 지난 글이전 글에서 0-1 배낭문제를 다이내믹 프로그래밍으로 푸는 방법을 소개했다. 이번에는 백트래킹으로 풀어보려고 한다. [Algorithm] 0-1 배낭문제(Knapsack Problem) - DP 풀이알고리즘 하면 나오는 대표 문제인 0-1 배낭문제에 대해서 글을 써보려고 한다.🎒 0-1 배낭 문제왜 0-1 배낭 문제일까? 0-1의 의미는 배낭에 넣기, 안 넣기 둘 중 하나만 선택이 되고, 일부만 넣는swift-library.tistory.com🛤️ Backtracking 백트래킹?나는 좀 더 간단하게 설명해보고 싶었다. 뭔가 의외로 엄청 어렵게 설명되어 있는 글들이 많았다... Backtracking이라는 단어의 뜻을 살펴보면 추적을 종료한다는 뜻으로도 보인다. 뭘 종료할 건데?? 이를 ..

알고리즘 하면 나오는 대표 문제인 0-1 배낭문제에 대해서 글을 써보려고 한다.🎒 0-1 배낭 문제왜 0-1 배낭 문제일까? 0-1의 의미는 배낭에 넣기, 안 넣기 둘 중 하나만 선택이 되고, 일부만 넣는 것은 불가능하기 때문에 0-1 배낭 문제라는 이름이 붙어졌다. 최대 15kg까지 넣을 수 있는 배낭에 다음과 같이 무게와 값어치를 가지고 있는 물건을 넣었을 때 어떻게 담아야 가장 비싸게 담을 수 있을까?물론 가장 좋은 방법은 물건을 쪼갤 수 있다면 무게당 가장 비싼 걸 1kg씩 차곡차곡 담으면 될 것이다. 하지만 이 문제의 핵심은 물건을 쪼갤 수 없다는 것이다. 그렇다고 무게당 가장 비싼 것부터 담게 된다면 이것이 가장 최적의 방법인지 장담할 수 없다.🎛️ 동적 계획법(DP)을 사용한 풀이가장 유..

🥸 문제 소개🧑🏻‍💻 문제 풀이사전을 순서대로 만들어 나가면서 target이 현재 추가된 단어와 같다면 값을 리턴하게 만들었다. 사전을 만들어 나가는 과정은 재귀함수를 활용하여 구현했다.func solution(_ target: String) -> Int { let vowels = ["A", "E", "I", "O", "U"] var found = false var answer = 0 func dfs(_ word: String) { if word.count > 5 || found { return } answer += 1 if word == target { found = true ..

🙇 시작하며물론 알고있는 내용들도 많지만 CPU에 대해서 간단하게 정리해보고 싶어서 이렇게 글을 먼저 작성하게 되었다. 아래와 같이 homebrew CPU라고 집에서 CPU도 만들 수 있다! (솔직히 나중에 만들어 보고 싶다... 극강의 공돌이만 도전 할 듯..?) Homebrew CPU Home PageMagic-1 is a completely homebuilt minicomputer.  It doesn't use an off-the-shelf microprocessor, but instead has a custom CPU made out of 74 Series TTL chips.  Altogether there are more than 200 chips in Magic-1 connected toge..

문제풀다가 사실 깜짝 놀랐다. 2차원 배열 회전을 하는 방법이 아리까리(?) 했던 것이다... 그래서 이번 기회에 확실하게 복습해보려고 한다.🕑 시계 방향 회전그림을 살펴보면 행이 열이 되고, 열은 행이 되면서 뒤집히는 효과(?)를 볼수 있다. 이것을 (n-1-열)로 나타낼 수 있다. 이것을 코드로 구현해보면 아래와 같다.func rotateClockwise(_ matrix: [[Int]]) -> [[Int]] { let n = matrix.count let m = matrix[0].count var rotated = Array(repeating: Array(repeating: 0, count: n), count: m) for i in 0..🕗 시계 반대 방향 회전반대로 ..

🧪 Test Double?항상 테스트를 하면서 Mock, Stub, Fake... 이런 키워드들을 보면서 언제 어떤 걸 쓰는 게 맞는 표현인지가 궁금해서 이번기회에 제대로 찾아보게 되었다.🤓 공식... 정의?솔직히 요즘 인공지능이 생겨나면서 인터넷에서 도대체 어떤것이 정확한 자료인지 항상 고민이 많이 된다. 그러다가 마틴 파울러 사이트에서 이것을 명확하게 정의한 것을 보게 되었다. 마틴 파울러가 누군지는 굳이 말할 필요 없을 것 같다. bliki: Test DoubleTest Double is generic term for fakes, mocks, stubs, dummies and spies.martinfowler.com마틴 파울러는 5가지를 소개하고 있다. Dummy, Fake, Stub, Spy,..

🌐 WWDC에서 설명하는 네트워크 구조, 테스트 방법WWDC 2018에서는 아래와 같이 네트워킹 과정을 설명하고 있다. 간단하게 말로 풀어보면 아래와 같지 않을까?원하는 요청 만들기서버에게 요청 보내고 응답 받기응답을 뷰에 맞는 형태로 바꾸기응답을 뷰에 표시하기만약 여기서 Server를 제외하고 중간 흐름 수준의 테스트를 하고싶다면?URLProtocol을 사용하면 된다!🍎 WWDC에서 설명하는 URLProtocol가상의 데이터, 응답을 줘서 직접적인 인터넷 연결 없이 내가 요청을 잘 만들었는지, 응답을 잘 처리하는지를 확인 할 수 있다. 네트워크 요청을 가로채는 것이다.Swift에서는 URLProtocol클래스를 상속받는 MockProtocol을 만들 수 있다. WWDC에서 소개하는 코드를 그대로 가..