lgvv98

BOJ 1516 게임 개발 오랜만에 위상정렬 문제인데 시간을 계산해야 해서 알고리즘이 약간 복잡했음.예전에 속에 있어서 풀었는데, 위상정렬 문제를 오랜만에 보니까 알고리즘이 가물가물해서 엄청 오래걸렸음. 좋았던 점은 알고리즘을 단기 암기식으로 한게 아니라, 원리를 명확하게 알아두어서 시간만 여유롭다면 직접 천천히 구현해가면서 할 수 있음. 문제풀이 플로우 우선 input은 기존의 위상정렬과 동일하게 Input을 받는다. 가장 중요한 건 시간을 처리하는 부분 1. 우선 초기에 queue에 들어간 값의 경우에는 시간을 계산할 수 계산할 수 없어서 result에 세팅2. while문을 위상정렬과 동일한 로직으로 돈다. -> while문 내에서 maxTime을 계산해주는데 2-1. 내 선수(내가 만족해야 하는..

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

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. 맞았습니다. 문제는 input시에 ..

BOJ 12738 가장 긴 증가하는 부분 수열 3 가장 기본적인 유형의 dp 문제. 알고리즘 접근법이진 탐색을 이용하였는데, C++에는 lower_bound를 제공해주어서 그런지, 이 부분을 따로 구현하지 않더라.진짜 Swift로 알고리즘 공부하는데 가장 힘든 것은 직접 전부 구현해야 하는 것들이 정말 많음 1. list의 마지막 값과 현재 값을 비교.2. 2-1. 현재 값이 list의 마지막 값보다 크다면 list의 끝에 현재 값을 대입 2-2. 현재 값이 list의 마지막 값보다 작다면 list를 거꾸로 순회 2-2-1. lowerBound를 통해서 나보다 작은 값의 index를 찾음. 2-3. lowerBound를 통해 찾은 list[index]를 현재 값으로..

BOJ 1931회의실 배정 ✅ 알고리즘 자체는 쉬웠음 먼저 정렬을 해야하는데, 끝나는 시간을 기준으로 수행하며 만약 그 끝나는 시간이 같다면 시작 시간이 빠른 것을 앞에다가 배치함. 그 이후로는 그리디(그냥 for문 다 돌리라는 말)로 풀면 되는데, 현재 시간과 시작시간을 비교해서 시작시간이 같거다 더 뒤에 있으면 카운트를 증가시키고 현재 시간을 끝나는 시간으로 바꿔주면 된다. 포스팅을 한다는 건 생각보다 오래 걸렸단 말이겠지? 백준 문제가 너무 불친절해서,, 테스트 케이스가 하나만 있던데, 당연히 정렬이 되어있는줄 알았음. 정렬이 안되어 있어서 그래서 정렬하니까 완료 나는 처음에 85%쯤에서 막혔는데 반례를 찾았음 [반례] 3 3 3 2 3 3 3 올바른 답: 3 let iterator : Int! =..