lgvv98

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]..

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

BOJ 2352 반도체 설계 ✅ 이 문제는 아래 문제 코드와 아예 똑같다.. 근데 하나 다른 점이라면 풀이를 떠올리기가 훨씬 더 어려웠다는 점. 2022.05.12 - [코딩테스트] - [Swift] BOJ 12738 가장 긴 증가하는 부분 수열 3 [문제 설명] 꼬이지 않는다라는 말이 이해가 가지 않았는데, 연결 선이 서로 겹쳐지지 않는다는 말임결국은 증가하는 부분수열 처럼 되는 문제임. ✅ 코드 let _ = Int(readLine()!)! let input = readLine()!.split(separator: " ").map { Int($0)! } var list = [input[0]] input.forEach { element in if element == list.last { } else if..

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 1920 수 찾기 ✅ 이진탐색을 구현하는 문제이다. 아니 이진탐색 그 자체이다. ✅ 코드 자료구조와 함께 추가하였다. 이진 탐색 포스팅은 최대한 빨리 하도록하자 import Foundation /// 오름차순으로 정렬 된 리스트에서 item의 index를 반환합니다. 없으면 -1 func binarySearchForAscending(array: [T], item: T) -> Int { var low = 0 var high = array.count - 1 while low item { high = mid - 1 } else { low = mid + 1 } } return -1 } _ = Int(readLine()!)! var searchList = [Int]() var input = readLine..

BOJ 7453 합이 0인 네 정수 ✅ 와 진짜 하루종일 풀어도 안풀렸다. 이진 탐색 분야인데 이게 개념은 늘 그냥 하면 되는거지 싶었는데, 막상 적용하려니까 엄청나게 어렵다. ✅ 알고리즘 접근법 이 문제의 경우에는 시간 제한이 있기 때문에, 다중 for문과 contains로는 해결할 수 없다. 1. input과정에서 column을 4개를 만들어서 따로 받는다. 2. col 1,2 그리고 col3,4를 for문으로 더해서 나올 수 있는 케이스를 구한다. (sumAB, sumCD) 3. sumAB와 sumCD를 정렬한다.(나는 오름차순으로 정렬) 4. [핵심] sumAB는 앞 부분부터 sumCD는 뒤 부분부터 순회하면서 값을 비교합니다. -> 왜냐하면 가장 작은 값과 가장 큰 값의 합이어야 0이 나올 수 ..

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..

BOJ 1916 최소비용 구하기 ✅ 아 이거 다익스트라 문제인데, 안풀린다. 거의 어제부터 오늘까지 이틀을 풀었는데 풀지 못하다니! 차라리 반례라도 많아서 어느 지점에서 내 알고리즘이 잘못 되었던 것인지 캐치하고 싶은데 ㅜ 내가 유독 약한게 그래프 부분인 것 같다. 근데 안되는거 오래 붙자고 있지 말라고 해서 그냥 다른 사람 코드 좀 보고 이해하는 방향으로 공부했다. 이걸 하루종일 할 수는 없으니까.- ✅ 코드 let n = Int(readLine()!)! var cities = [[(end: Int, value: Int)]](repeating: [], count: n+1) // label을 달아서 배열 생성 for _ in 0..