lgvv98

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

BOJ 11724 연결 요소의 개수 ✅ 예전이면 이걸 어떻게 하지 싶었는데, 이제는 쉽게 풀어낼 수 있다. BFS / DFS의 경우에는 tree형태로 이론을 배웠어서 그래프 형태면 늘상 포기하곤 했었는데, 그래프도 해결할 수 있었다니..! 신기해 근데 원래는 문제 풀다가 어려운거 아니면 포스팅 안하는데, 어느 순간부터인가 모든 문제를 포스팅 하고 있다. 나동빈 파이썬 책에서는 BFS가 DFS보다 빠르다라고 하였지만, 스위프트에서는 구현에 따라 BFS보다 DFS가 빠를 수 있다. 아래의 글은 내가 DFS / BFS를 구현한 알고리즘이다. 2022.04.02 - [코딩테스트] - [Swift] BOJ 1260 DFS와 BFS 나는 주로 BFS의 경우 removFirst를 이용하기 때문에, 배열의 write ..

BOJ 1697 숨바꼭질 ✅ 일단 이 문제를 풀면서 그동안 자주 사용했던 BFS 패턴을 적용했는데, 시간 초과로 통과할 수 없었음. 질문란이나 다른 분들이 Swift는 Queue를 만들어야 통과한다고 제시하는 의견도 있었는데, 내가 보니까 이게 그렇게 큰 영향을 주는 것 같지는 않았음. 그러다가 정말 좋은 블로그를 발견해서 이 분의 아이디어를 기반으로 아주 약간만 개선하고 이 분의 코드를 학습함. 스위프트는 유독 2차원 배열보다 차라리 1차원 배열에 튜플을 넣는게 속도가 엄! 청! 나! 게! 빠름 그러니까 2차원 배열 만들지말자..! 아래는 시간 비교이다. ✅ 코드 let info = readLine()!.split(separator: " ").map{ Int(String($0))! } let subin..

BOJ 2667 단지번호붙이기 ✅ BOJ 2667 단지번호붙이기 이거 하루 반 풀었는데, 논리로는 알겠는데 안되다가 유기농 배추 풀고나서 다시 풀면서 맞음. ✅ 알고리즘 접근법 유기농 배추와 유사하나 각 그룹의 갯수를 따로 저장해야하므로 그것만 한번 더 체크하면 된다. 근데 내 알고리즘의 치명적인 문제가 있다. 단독 그룹인지 체크할 수는 있으나, 단독 블럭일 경우 그 블럭이 count를 계산할 수 없다는 점. 그래서 보완을 위해 dx,dy에 0,0을 추가하여 해결하였다. 유기농 배추를 먼저 읽어보고 이 문제를 풀면 수월하게 이해할 수 있다. 2022.04.03 - [코딩테스트] - [Swift] BOJ 1012 유기농 배추 [Swift] BOJ 1012 유기농 배추 BOJ 1012 유기농 배추 ✅ 오 일..

BOJ 1012 유기농 배추 ✅ 오 일단 문제 이름이 정말 맘에 든다. 각설하고, 알고리즘은 한번에 확 떠올렸는데, 이 논리가 다른 문제에 코드로 구현하다가 막혀서 그 문제를 건너 뛰고 하다가 그냥 다시 도전해봄. 일단 풀긴 풀었는데 시간은 1시간 걸림. 이유는 count를 처리해야 하는 부분이 내 논리상 while을 탈출한다면 queue가 비면서 하나의 블럭(그룹)이 만들어졌다는 말로 이해하는데, 근데 visited 처리 부분에서 좀 꼬인게 있었나봄. 풀었으니까 이번 문제는 리뷰가 절대적으로 필요할 것 같아서 리뷰함. ✅ 알고리즘 접근법.우선 미로 찾기 문제와 다르게 얘는 어디가 시작 포인트가 되는지 알 수가 없음.그래서 이중 for문을 돌면서 1이 어디있는지 찾고자 함.그리고 1을 찾으면 그 위치에서..

BOJ 2606 바이러스 ✅ 이건 진짜 쉬웠음. ( solved.ac 기준 실3 ) 사실 이전에 다른 문제가 안풀려서 이걸로 이동함 그 문제는 문제 설계는 했는데, 뭔가 어디서 오류가 나는지 제대로 안되어서 걍 패스했음. 다른건 아니고 주의할 점 하나만 남겨두겠음. 내가 흔히 하는 실수 중 하나가, 데이터를 입력 받는 순간에서 저지르는 실수인데 그래프 형태라면 서로가 서로를 배열에 담아야 함. 무슨 말이냐면 나는 주로 [ Int: [Int] ] 형태로 입력을 처리하는데 2번과 5번의 경우 2: [1,3,5] 5: [1,2,6] 이렇게 가져야한다는 말임. 근데 나는 트리처럼 처리를 해서 실수를 종종함. 나는 그냥 DFS로 했는데 BFS사용해도 상관 없음 🟠 코드 import Foundation struct..

BOJ 2178 미로 탐색 ✅ BFS 문제였다. DFS의 경우에는 하나의 노드를 깊게 탐색하여 그 노드가 최선값이 아니면 기회비용이 더 들어간다. 그리고 나동빈 책에서도 DFS보다 BFS가 일반적인 코딩테스트에서 더 빠르다고 권장함. 일단 BFS에 아직 익숙치 않아서 어려웠음. 그동안 문제 풀면서 가장 어려웠던 유형이 이렇게 N x M 배열에서 무언가 최선의 값을 구하거나 경로를 구하는 등의 작업이면 진짜 힘들었음. 나름의 방법으로 해결하겠다고 한 것이 재귀를 이용하여 풀어보려는 시도를 아주 많이 해보았으나, 대부분 fail. BFS 공부는 진짜 많이 했는데, 적용이 도저히 안되겠어서 구글링의 도움을 받아 적용시켜봄 ✅ 알고리즘 순서 1. queue에 시작점을 세팅한다. 2. 현재위치에서 상하좌우 4번의..

BOJ 1912 연속합 ✅ 연속합은 스스로 빠르게 풀었다. 알고리즘에 매우 근접했으나, 다만 몇몇 예외 케이스를 제대로 확인하지 못해서 틀렸었다. 백준의 반례를 찾아 해결하긴 했으나, 이 부분까지 혼자 커버 가능하다면 더욱 좋을 것 같다. [반례] 10 15 40 80 84 -22 -28 72 80 69 -44 answer : 390 3 -1 -4 5 answer : 5 🟠 문제 접근법 이것도 종이에 쓰면서 푸니까 쉽게 패턴을 찾을 수 있었다. i번째 순서에서 dp[i-1]과 list[i-1]에서의 값을 비교해서 더 큰 값을 고른다. (value) value와 현재 값을 비교해서 현재값이 value보다 크다면 내가 연속합이 최선임으로 dp[i]에 현재값을 넣는다. 근데 여기서 하나 주의할게 있는데, 만약..

BOJ 1932 정수 삼각형 ✅ dp를 이용한 문제였는데, 스스로 점화식을 찾아서 풀었다~! 처음으로 점화식을 찾아서 푼 문제라 엄청 뿌듯하기도 하고, 점화식을 찾는데도 시간이 꽤 걸렸지만 너무나도 행복하다 ㅎㅎ solved.ac 이용해서 난이도 확인해 봤는데 실버1이라니.. ㅎ 근데 시간을 더 올리는게 중요하겠음. 어떻게 풀었냐면 아래 사진을 참고하면 좋을듯하다. 🟠 예전에 어떤 글을 보다가 알고리즘 잘하는 사람은 손으로 안하고 머리로만 딱 해서 하는게 진짜 잘하는 사람이라는 글을 봤었는데, 그래서 일부러 종이를 안쓰고 머리속으로 생각하는 연습을 함. 근데 나는 아직 그정도가 아니라서 종이를 쓰면서 하는게 더 낫겠음. 🟠 dp값을 지정할 때, 나는 주로 dp[1]과 dp[2]를 먼저 세팅해주는데, 문제..