lgvv98

BOJ 1766 문제집 ✅ 이것도 위상정렬 문제입니다. 위상정렬 알고리즘은 쉬운데 어느때에 사용해야할 지 판단하는게 중요하다. 물론 위상정렬 알고리즘 포스팅에도 적어 두었지만, 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 쉽게 말해서 선수과목 같은 조건이 있는 경우에 사용한다. ✅ 코드 알고리즘은 줄 세우기 알고리즘과 같다. 다만, queue를 sort해야하는 부분만 조금 다르며, queue의 경우에는 줄 세우기는 데이터가 커서 index로 접근하지만 이 문제에서는 removeFirst로 처리한다. 2022.05.24 - [코딩테스트] - [Swift] BOJ 2252 줄 세우기 //https://www.acmicpc.net/problem/1766 import Foun..

BOJ 23034 조별과제 멈춰! ✅ 시간초과로 인하여 실패한 문제입니다. 누군가 이 문제를 푼다면 제게 꼭 알려주세요! 그냥 쉽게 크루스칼 사용해서 풀면 되겠다 싶었는데, 시간 초과를 해결할 수 없었다. Swift 언어로 통과한 사람이 아무도 없는걸 보면은 안되는건가 싶으면서도, 주어진 데이터 크기와 알고리즘을 고려해 보았을 때, 해결할 방법이 분명히 있을탠데 모르겠다. 🟠 시도해 본 방법 1. FileIO 사용해서 데이터 빨리 입력 받기 (https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88) 2. cost의 범위를 Double로 바꾸기 (Int형 오버플로 날 수도 있어서) 3. questions tuple -> Array로 변경..

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

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프로에 속하나보다 ㅎㅎ 이게 개념은 쉬운데, 문제 해결을 위해 적용하는게 어렵더라. ✅ 알고리즘 접근법. 이 문제는 알고리즘 접근법이 생각보다 어려웠다. 나동빈 책 이분탐색 부분을 보면 파라메트릭 서치라는 개념이 있는데, 그 개념을 사용해서 풀어야 했다. 이건 추후에 ..