lgvv98

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

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

chapter 5. DFS/BFS ✅ DFS/BFS에 대해서 알아보자! DFS/BFS는 인공지능 수업시간에 공부했어서 그 개념은 알고 있었지만, 코드로 작성해 본 경험은 예전에 급하게 문제를 풀 때를 제외하곤 없었다. 알고리즘을 풀면서 DFS/BFS는 음.. 뭐랄까, 재귀나 완전탐색 등 다른 방법으로도 풀리는 문제들도 있었는데 가끔은 DFS/BFS가 아니면 풀 수 없겠는 문제(아니면 매우 복잡한)가 많더라. 그래서 공부해봄 ✅ DFS DFS는 깊이 우선 탐색 알고리즘이다. 이 알고리즘은 특정한 경로로 탐색하다가 특정 상황에서는 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가서 다른 경로로 탐색하는 경로로 탐색하는 알고리즘이다. import Foundation func DFS (graph: [T: ..