lgvv98

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

BOJ 7576 토마토 ✅ 토마토 문제는 조금 더 생각해야 했으나 그래도 어렵지는 않았다. 다만, 시간초과를 해결하지 못해서 구글링을 했었는데, 자료구조에 대한 이해도 확실히 중요하다고 느낀 시간이었다. ✅ 시간초과가 나고 나름 개선한코드 queue에서 removeFirst()를 사용하면 O(N)이 걸리니 index로 참조하게끔 수정 그러나 시간초과는 여전히 똑같았다. let n = readLine()!.components(separatedBy: " ").map { Int("\($0)")! } var matrix = [[Int]](repeating: [Int](repeating: 0, count: n[0]), count: n[1]) var visited = [[Bool]](repeating: [Bool]..

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 10844 쉬운 계단 수 ✅ dp를 이용한 문제인데, 점화식을 찾았는데 이를 수학적으로 해결하려다가 시간이 매우 오래걸린 문제 일단 손으로 해보니까 일정한 패턴을 찾을 수 있었음 0 -> 1개 1~8 -> 2개 9 -> 1개 이렇게 노드를 만들 수 있었음. 처음에는 이를 해결하려고 수학적으로 접근을 했는데, 노드를 n = 4까지 직접 그려봐서 패턴을 찾으려고 함. 근데 이게 검증을 하려고 하니까 적어도 n = 5까지는 있어야할 것 같은데 너무 노가다인거 같은거임. 그래서 방법을 바꿈. 0 : dp[N][L] = dp[N-1][L+1] 1~8 : dp[N][L] = dp[N-1][L+1] + dp[N-1][L-1] 9 : dp[N][L] = dp[N-1][L-1] 이러한 패턴을 갖게 된다. 여기서 ..

BOJ 2158 포도주 시식 ✅ 비슷한 유형을 일전에 풀어본 기억이 있어서 금방 풀겠다 했었는데, 무지 오래 걸렸음. 백준 2579번 계단오르기와 비슷한데, 약간 다른 점이 있음 계단 오르기에서는 마지막값을 무조건 선택하지만 포도주는 마지막을 선택하지 않을 수도 있음. 무슨 말이냐면 [100 100 1 1 100 100]의 결과가 있다고 하자. 계단 오르기 알고리즘을 적용하면 301이 나오나, 포도주 시식 문제에서는 400이 나와야 함. ✅ 알고리즘 접근법우선 계단 오르기와 마찬가지로 ? X O? X O O로 나누어서 생각했음.? 자리는 dp배열에서 O자리는 리스트에서 뽑기따라서 우리는 점화식을 만들 수 있는데, 끝자리를 i라고 가정했을 시 1. dp[i-2] + list[i] 2. dp[i-3] + l..

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]에 현재값을 넣는다. 근데 여기서 하나 주의할게 있는데, 만약..

프로그래머스 LV2. 가장 큰 수 ✅ 프로그래머스 LV2. 가장 큰 수 이번 문제를 포스팅 하는 이유는 조금 특이한 정렬 방법 때문이다. 우선 정렬를 저렇게 하는데, 저렇게 하면 각 숫자의 길이에 관계없이, 정렬을 할 수가 있다. 그리고 0000을 반환하는 옵션을 하나 추가하는데, 내림차순임으로 가장 앞자리가 0이면 모든 값이 0이라는 의미니까 이렇게 작성한다. //https://programmers.co.kr/learn/courses/30/lessons/42746 import Foundation struct p42746 { static func run() { // print(p42746.solution([6, 10, 2])) // 6210 // print(p42746.solution([3, 30, 34..