lgvv98

BOJ 4386 별자리 만들기✨ ✅ 별자리 만들기 문제이다. 알고리즘은 크루스칼 알고리즘인데 간선의 정보를 직접 구해야 한다. 간선의 정보를 다 구하려면 2중 for문을 거쳐야해서 이게 맞나 싶었는데, 데이터 수가 크지 않아서 가능했다. 크루스칼을 풀면서 자주 실수를 하는데, 그것은 크루스칼 알고리즘 쪽에 정리해 두었다. ✅ 코드 import Foundation let v = Int(readLine()!)! // 별의 갯수 var input: [[Double]] = [] // [x,y] 좌표들의 list var parent = Array(0...v) // // 2차원 배열로 세팅함. for _ in 0..

BOJ 1197 네트워크 연결 🎉 시작하기에 앞서 🎉 400번째 포스팅이다 ㅎㅎ 꾸준히 공부한 것들을 기록하고 있는데, 다음 100개의 포스팅은 SwiftUI로 꽉꽉 채워보자! ✅ 최소 스패닝 트리의 기본적인 유형이다. find - union 과 최소 신장 트리를 찾는 크루스칼 알고리즘을 적절히 섞으면 된다. 근데, 이 알고리즘을 잘 이해하고 있지만 구현하는데 자잘한 실수를 해서 실수를 정리하고 한다. 최소 스패닝 트리에서의 내 실수들 1. union함수에서 num1, num2도 find함수를 통해서 해야한다. -> 자꾸만 난 parent[i] 로 세팅하는 실수를 범한다. 2. parent의 개수를 지정할 때는 노드의 개수(정점의 수)만큼 지정해야 한다. -> 실수로 간선의 개수로 설정하기도 한다. 3...

BOJ 1647 도시 분할 계획 ✅ 이 문제는 살펴 보아야할 것들이 조금 많다. 우선 나동빈 책에 있는 대표적인 유형이다. 크루스칼 알고리즘을 사용하면 쉽게 풀 수 있었지만, Swift를 사용하는 내게 시간초과라는 결과를 받음. ✅ 내가 처음에 푼 알고리즘. (시간초과) let firstLine = readLine()!.split(separator: " ").map { Int($0)! } var parent = Array(0...firstLine[0]) // 부모노드 생성 for i in 0...firstLine[0] { parent[i] = i } // print(parent) var edges = [(Int, Int, Int)]() // 시작, 끝, 비용 for _ in 0.. Int { if par..

BOJ 1197 최소 스패닝 트리 ✅ 나동빈 책을 보고 나서 풀어보려고 했는데, 생각보다 잘 안풀린다. 요즘 자주 참고하는 블로그가 있는데, https://icksw.tistory.com/101 [백준] 1197번 최소 스패닝 트리 [Swift] 문제 링크 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주 icksw.tistory.com 이번 코드도 여기서 참고 했다. ✅ 코드 let firstLine = readLine()!.split(separator: " ").map({Int($0)!}) let v = firstLine[0]..

Swift 디자인패턴 Adapter Pattern (어댑터 패턴) Adapter Pattern은 서로 호환되지 않는 인터페이스를 가진 클래스들이 함께 동작할 수 있도록 중간 역할을 하는 구조 패턴.기존 코드를 변경하지 않고, 원하는 인터페이스를 갖춘 어댑터를 추가하여 두 시스템을 연결 히스토리2022-05-13: 디자인 패턴 스터디 정리2024-11-28: 포스팅 글 재정리 및 예제 변경 Adapter Pattern어댑터 패턴은 4가지 구성요소로 이루어져 있음클라이언트(Client):특정 인터페이스를 기대하며 동작하는 코드.타겟(Target): 클라이언트가 호출하려는 인터페이스.어댑터(Adapter): 타깃 인터페이스를 구현하여, 실제 서비스를 제공하는 어댑티(Adaptee)를 감싸는 객체.어댑티(Ada..

BOJ 2143 두 배열의 합 ✅ 두 배열의 합 난이도는 골드3.. 근데 투 포인터 + 이진탐색? 영역이라서 극한으로 어려웠다. 이 문제를 풀기 전에 2022.05.12 - [코딩테스트] - [Swift] BOJ 7453 합이 0인 네 정수 위 문제 푸는데 엄청나게 시간 많이 들었는데 ㅠ 투 포인터라니.. 이런 흐름을 가져가는 문제도 있다는 것을 알아두면 코딩 테스트에서 구현할 수 있겠지. [알고리즘 접근법] 1. 부분합(연속적이어야함) 을 A,B 배열을 찾는다. 2. 정렬을 한 후에, 위 아래로 하나씩 보고 두 수를 더했을 때 찾는 수와 같다면 중복을 체크하여 validCase에 반영한다. 3. 두 수가 더했을 때, 다르다면 그 크기를 체크하여 aIdx or bIdx를 옮긴다. ✅ 코드 let t = ..

BOJ 2805 나무 자르기 ✅ 나무 자르기 나동빈 책에서 같은 논리로 푸는걸 보았는데, 쉽다고 생각했는데 안되었음. 내가 이 문제를 못 푼 이유가 있는데, 이게 나무가 정확히 m만큼 나온다고 생각했었음.이게 경우에 따라서는 m보다 더 가져갈 수 밖에 없을 수도 있음 [틀린 코드 부분에서의 반례] 4 8 20 15 10 17 15일 때 -> result 7 14일 때 -> result 10 따라서 답은 14이지만 8보다는 많이 가져가면서 최소로 가져감. 이 로직이 가장 중요한 부분이었다. ✅ 코드 // 나무의 수 N, 상근이가 가져가려는 나무의 길이 M let input = readLine()!.split(separator: " ").compactMap{ Int(String($0))} let m = in..

BOJ 12738 가장 긴 증가하는 부분 수열 3 ✅ 풀었다. 일단 이 문제는 dp를 사용해서 풀려고 했었는데, 시간 초과로 다른 접근 방법이 필요했다. 2022.04.01 - [코딩테스트] - [Swift] BOJ 11053 가장 긴 증가하는 부분 수열 [Swift] BOJ 11053 가장 긴 증가하는 부분 수열 BOJ 11053 가장 긴 증가하는 부분 수열 ✅ dp라는데 진짜 어려웠다. 우선 알고리즘 풀이법이 이해가 가지 않았다. 주어진 값이 10 20 10 30 20 50 있다고 가정하자. list 10 20 10 30 20 50 dp 1 2 1 3 2 4.. rldd.tistory.com 위의 문제는 dp로 해결이 가능했었는데 아무튼 아이디어가 도통 떠오르지 않아서 다른 분들의 로직을 참고하였음...

BOJ 1300 K번째 수 ✅ wow 생각보다 오래걸렸다. 문제보고 한 10초만에 해결하겠다 싶었는데 메모리 초과 ! 문제 조건을 보니까 10^9(10의 아홉제곱!) 까지 가능하다고 한다. 처음에는 그냥 배열을 N by N으로 만들어서 배열 인덱스 값의 곱을 배열 value로 저장하고 flatMap 이후에 sort해서 찾았다. 메모리 초과라니.. 나동빈 책 보니까 이진탐색을 정말 잘 구현하는 개발자는 10프로 정도밖에 안된다는데, 나도 90프로에 속하나보다 ㅎㅎ 이게 개념은 쉬운데, 문제 해결을 위해 적용하는게 어렵더라. ✅ 알고리즘 접근법. 이 문제는 알고리즘 접근법이 생각보다 어려웠다. 나동빈 책 이분탐색 부분을 보면 파라메트릭 서치라는 개념이 있는데, 그 개념을 사용해서 풀어야 했다. 이건 추후에 ..

BOJ 1238 파티 ✅ BOJ 1238 파티 스위프트는 다익스트라 알고리즘 풀려면 진짜 극악이다. 특히 효율성을 따져야한다면 힙을 구현해서 사용해야 하는데, 이거 진짜 너무나도 노가다 작업인듯. 다익 쓰면 쉽게 푸는데 이거 다익을 구현하는게 결국은 관건임.다른 사람들도 효율성을 위해서 힙을 사용했는데, 하 힙 구현해서 쓰기 너무나도 귀찮음 .. . . . ✅ 코드 // // b1238.swift // Algorithm // // Created by Hamlit Jason on 2022/05/11. // // https://www.acmicpc.net/problem/1238 import Foundation struct b1238 { static func run() { let input = readLine..