lgvv98

[LeetCode] 11. Container With Most Water https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=leetcode-75  문제 풀이 접근법투포인터 활용투포인터 접근법은 가장 높은걸 기준으로 가장 멀리 있는것 부터 하나씩 체크해가는 로직왜냐하면 가장 멀리 있는 기둥일수록 가장 면적이 크게 잡히기 때문.면적을 계산한 후 두 기둥 중 더 높은 기둥을 기준 포인터로 남기고 기준 포인터에서 L, R을 옮겨가면서 판단하기이게 가능한 이유는 `거리`가 가중값 없이 존재하기 때문에 거리를 기반으로 L, R을 옮기면서 찾아보면 된다.만약 가중값이 존재한다면 그래프 알고리즘으..

[LeetCode] 334. Increasing Triplet Subsequencehttps://leetcode.com/problems/increasing-triplet-subsequence/?envType=study-plan-v2&envId=leetcode-75     문제 풀이 아이디어증가하는 K(3)개의 수를 찾는 문제로 일반화K개의 값이 증가하는 패턴을 찾기그리디 알고리즘으로 접근K개를 먼저 준비해두고, 0번 인덱스부터 값을 교체해가며 연속하는 배열을 찾아냄  class Solution { func increasingTriplet(_ nums: [Int]) -> Bool {// kLengthArray는 현재까지 발견한 k개의 증가하는 수열을 저장 var k = 3 v..

[LeetCode] 605. Can Place Flowers  - DP 활용해 누적곱으로도 풀어낼 수 있는데, 특정 조건이 만족하면 그대로 종료할 수 있는 로직을 통해 특정 데이터 조건에서 시간 복잡도 개선이 불가하여, 다른아이디어 적용  문제 링크https://leetcode.com/problems/can-place-flowers/?envType=study-plan-v2&envId=leetcode-75  문제풀이아이디어, 나 자신을 제외한 모든 수를 곱하는 거라서, 이미 모든 수를 다 곱해놓고, 출력 전에 나 자신으로 나누기이 과정에서 특정 조건을 만족한 경우 엣지케이스를 통한 처리로 시간 복잡도 줄임 분석 및 주의점0이 2개 이상이면 모든 자리는 0이므로 전체 곱을 수행하는 도중에 0이 2개 이상이라..

BOJ 1516 게임 개발 ✅ 이 문제는 위상 정렬 문제인데 시간을 계산해야 해서 알고리즘이 약간 복잡했다. 근데 풀다가 못풀 것 같았는데 맞았을 때의 희열감이란,, ㅎ 🟠 문제풀이 플로우 우선 input은 기존의 위상정렬과 동일하게 Input을 받는다. 다만 중요한건, 시간을 처리하는 부분이다. 1. 우선 초기에 queue에 들어간 값의 경우에는 시간을 계산할 수 계산할 수 없어서 result에 세팅 2. while문을 위상정렬과 동일한 로직으로 돈다. -> while문 내에서 maxTime을 계산해주는데 2-1. 내 선수(내가 만족해야 하는 조건)의 초기 time값과 갱신된 시간을 비교하여 더 큰 값을 maxTime에 넣어준다. 2-2. 이 코드를 보자. result[i] = max(result[i]..

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

BOJ 2252 줄 세우기 ✅ 위상 정렬 문제이다. 진짜 많이도 틀렸다. 1. 2개의 틀렸습니다. 알고리즘 후에 마지막으로 출력할 때 1 2 3으로 해야하는걸 [1,2,3]으로 반환했기에 이를 수정해주었다. 2. 시간초과 3개는 동일 알고리즘에서 시간 초과가 나서 readLine 부분을 수정하였다. 처음에 readLine 부분을 개선하니 11%에서 시간초과 나던게 15%에서 시간초과가 나니 약간의 개선 효과는 있었던 듯 싶다. // 시간초과 11% readLine()!.split(separator: " ").map { Int($0)! } // 시간초과 15% (개선코드) readLine()!.split(separator: " ").map { Int(String($0))! } 3. 맞았습니다. 문제는 in..

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