설모의 기록

이 문제는 DFS와 Backtracking을 이용해 중복되지 않은 알파벳은 방문하지 않는 조건으로 (0, 0) 에서 갈 수 있는 경로의 최대거리를 구하는 문제입니다. 저는 char 자료형 특징을 이용할 생각을 못하고 지금까지 지나온 알파벳을 ArrayList에 저장해 다음 경로로 갈 때마다 체크해주는 코드로 짜봤는데요. 시간이 8000ms가 넘길래 너무 놀라서 검색해봤는데 char 자료형을 이용하면 훨씬 수월하게 탐색할 수 있는 방법이 있었습니다. 아래에 비효율적으로 짠 코드와 최적화한 코드를 차례로 첨부하겠습니다. 우선 대문자 알파벳이기 때문에 'A' ~ 'Z' 까지가 범위가 되며 int형으로 바꾸면 65 ~ 90이 됩니다. 그래서 저는 check 배열의 인덱스를 (입력 알파벳 - 'A' ) 이라 생각..

이 문제는 주어진 숫자들 중 중복되지 않고 순서에 관계없이 6개의 숫자를 골라 오름차순으로 정렬해 출력하는 문제입니다. 재귀함수를 이용해 모든 경우를 고른 후 이전에 뽑았던 숫자조합인지를 확인해도 되지만, 굳이 전에 뽑은 숫자 조합을 다시 뽑지 않도록 한번의 반복문과 calculate 함수 내에서 백트랙킹을 이용했습니다.

탐색 알고리즘에는 여러가지가 있습니다. 가장 기본적인 알고리즘이 BFS 와 DFS 인데요. 각각 아래에서 살펴보겠습니다. BFS(Breath First Search) BFS 는 너비우선탐색 알고리즘입니다. 위의 트리는 깊이(depth)가 2인 이진트리입니다. BFS는 루트부터 시작해서 깊이별로 가로방향을 먼저 탐색해나가는 방식입니다. 따라서 1단계에 있는 a를 먼저 탐색하고, 2단계에 있는 b,c 를 탐색하고, 마지막으로 3단계에 있는 d,e,f,g 를 탐색하는 방식입니다. 장점너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장합니다.최단경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단경로를 반드시 찾을 수 있습니다.노드의 수가 적고 깊이가 얕은 해가 존재..