이 글은 Velog에서 이전한 글입니다. Velog 원문 보기프로그래머스 - Lv2. 피로도문제를 읽으면서 완전탐색 문제라고 생각했다. 그 이유는 제한사항 중 던전의 개수를 보면 알 수 있는데 던전의 개수는 1이상 8 이하이다. 즉, 완전탐색 방식으로 풀어도 메모리 초과와 시간 초과를 걱정하지 않아도 된다는 것이다.완전탐색 문제는 문제 조건만 맞다면 코드 구현은 매우 간단하다. 단순히 모든 경우의 수를 탐색해주면 된다.완전탐색 방법이 무식해보여도 때로는 최고의 방법인 경우도 있다는 것을 기억하자!완전탐색 풀이 코드import itertoolsdef solution(k, dungeons): answer = 0 nPr = list(itertools.permutations(dungeons, len(..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기프로그래머스 - Lv3. 여행 준비 DFS 알고리즘의 이해 부족을 느낀 문제이다.일단 문제를 처음 봤을 때 '그래프 탐색 문제, 항공권 정보는 딕셔너리로 정리하는게 좋겠다.'라고 생각했다. 여기까지는 좋았는데, 이후 익숙한 BFS로 문제를 풀려고 했지만 도저히 풀이 방법이 생각나지 않았다. 결국 다른 분들의 코드를 참고했다.이 문제는 DFS, BFS 두 방법 모두 풀이가 가능한데 문제 요구사항에 더 적합한 DFS 풀이 방법 먼저 살펴보자.DFS 스택 문제 풀이 코드defaultdictdefaultdict는 딕셔너리를 만드는 dict 클래스의 서브 클래스이다.작동 방식은 유사한데, defaultdict의 인자로 주어지는 객체의 기본값을 딕셔너리값..

이 글은 Velog에서 이전한 글입니다. Velog 원문 보기프로그래머스 - Lv3. 아이템 줍기문제 설명 제한 사항풀이나는 알고리즘 문제를 풀 때 문제를 세분화된 과제로 정리한다.문제 요구사항을 읽으면서 정리한 과제는 아래와 같다.겹쳐진 직사각형 사이에서 테두리 구분하기백트래킹시 테두리의 좌표를 어떻게 구별할 것인지사실상 테두리의 좌표만 정리한다면 그 이후부터는 일반적인 그래프 탐색 문제와 다를 것이 없다.처음에는 테두리 구분을 각각 직사각형을 모두 구분하며 하나하나 테두리를 찾으려고 했다.그러나 이는 높은 시간 복잡도를 요구하기에 바로 마음을 접었다.많은 고민을 했지만 결국 테두리를 구분할 방법을 찾지 못했다.다른 분의 아이디어를 참고하여 문제를 다시 풀었다.풀이 방법2차원 리스트를 만들어 테두리는..