너비우선탐색2

• 

  백준 1600 말이 되고픈 원숭이 - JAVA 이 문제를 푸는데 3시간이 걸렸다. 혼자 푼 건 아니고 로직은 맞는데 메모리 초과가 나서 구선생님의 도움을 받았다. 배열로는 메모리 초과가 뜨는데 Monkey 객체로 푸니까 문제가 풀렸다. 마치 int를 long으로 선언해서 맞은 기분이랄까? 6%에서 자꾸 시간 초과, 메모리 초과, 틀렸습니다가 떠가지고 너무 당황스러웠다. 문제 풀이의 핵심은 다음과 같다. 1. 최소한의 동작으로 목적지 도달 -> BFS(너비 우선 탐색) 2. 벽이 있는 곳은 가지 못함 3. 쓸모없는 탐색, 함수 호출 제거 4. 배열이 아닌 객체 선언 및 생성을 통한 메모리 초과 해결 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 3. 20.

• 

  그래프(Graph), 그리고 DFS와 BFS - 1. 그래프에 관하여 DFS와 BFS는 탐색 알고리즘의 한 종류이다. 이 알고리즘은 그래프를 알고 있어야 이해할 수 있는 알고리즘이다. 그래서 그래프부터 다루고자 한다. 그래프란 점(정점)과 선(간선)으로 이루어진 자료구조를 의미한다. 별개 아니다. 그냥 숫자(인덱스)가 붙은 점들과 그 점들 간의 관계를 선으로 표시한 것 뿐이다. 단순한 점과 선들의 조합인 그래프를 활용해 마크주커버그가 페이스북을 만들었다. 이 페이스북을 사례로 그래프를 설명할 것이다. 자고로 본인은 페이스북 안한지 100만년된 듯 싶다. 각 점을 사람으로 간주하고 각 선을 팔로우하여 관계를 표시하면 그것이 그래프다. 눈치 챈 사람도 있겠지만 A가 B를 팔로우하였다. B가 A를 맞팔로우하였다와 같이 (간)선들은 일종의 방향성을 가질 수 있다. 이와 같은 방향.. 알고리즘공부(Algorithm Study)/알고리즘이론(AlgorithmTheory) 2022. 2. 22.