lgvv98

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

프로그래머스 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..

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

BOJ 11053 가장 긴 증가하는 부분 수열 ✅ dp라는데 진짜 어려웠다. 우선 알고리즘 풀이법이 이해가 가지 않았다. 주어진 값이 10 20 10 30 20 50 있다고 가정하자. list 10 20 10 30 20 50 dp 1 2 1 3 2 4 코드를 보면 이해할 수 있는데, 어떤 수를 기준으로 나보다 작은 수를 비교한다. 나를 기준으로 내 앞을 비교한다. 나보다 작은 수(j)라고 하면 dp[j]는 dp[j]보다 작은 값들이 몇개 있는지 저장한다. 그게 가장 긴 부분 수열의 합이기 때문이다. 제일 중요한 것은 실제 문제 풀이에서 이를 떠올려야 한다는 점이다. 그렇다면 점화식을 어떻게 생각할 수 있을까?dp문제의 경우에는 그냥 손으로 쓰다보면 특정한 패턴을 찾을 수 있다.list를 놓고, 나보다 작..

BOJ 2579 계단 오르기 ✅ 점화식을 이용한 DP문제였다. 나동빈 책을 공부하면서 비슷한 문제를 해결하려는 노력을 했었는데, 진짜 너무나도 어려웠다. 여기서는 점화식을 세우기 위해 문제의 마지막 조건의 초점을 맞추는데, 마지막 계단은 꼭 밟아야 한다. 이 문장을 기준으로 점화식을 설계해보자!!!! 마지막 계단을 꼭 밟아야 하므로, 마지막 계단을 밟는 케이스를 보자면1. O X O O (끝 계단과 바로 이전 계단을 밟음, 3연속은 안된다, 근데 최댓값을 찾아야 하므로 전전전칸도 포함한다.)2. ? O X O(끝 계단과 그 전전 계단을 밟음) 케이스 1에서는 끝 패턴이 저걸로 고정 케이스 2에서는 끝 패턴이 저렇게 고정 ? 자리는 어떤게 올지 모른다는 말 -> 따라서 수식에 반영하지 않는다. 이를 점화식..

프로그래머스 LV2. 땅따먹기 ✅ 프로그래머스 LV2. 땅따먹기를 푸는데 생각보다 많이 어려웠음. 처음에는 최댓값 찾고 다음 Index의 값을 0으로 세팅하려고 했는데, 그러니까 실패함 -> 잘못된 접근 그래서 다음으로는 점화식을 찾아보려고 했는데, 에러 케이스를 스스로 발견하고 다른 방법을 고민함. 구글링 결과 어떤 분에게서 아이디어를 얻었는데, 이번에 느낀 점은 이러한 풀이 방식도 있다는 것을 기억하고, 문제 접근하는데 더 열린 사고로 다가가야겠음. 사실 그냥 여러 케이스를 경험해 보면서, 어떠한 문제를 만났을 때 이전에 시도해 본 방법 중 하나가 기억에 떠올라 그 방법을 풀기를 기대하는 측면이 더 큼. 일단 처음에는 정답은 맞았으나, 효율성을 0점을 받았는데, max의 parameter로 3개의 값..