dfs
-
[자료구조] [python] [Search] Cut the TreeData miner/Algorithm & Data structure 2022. 1. 24. 15:03
Hackerrank의 Algorithms 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/cut-the-tree/problem?isFullScreen=true * 재귀를 통해서 문제를 풀려고 했는데 제대로 알고리즘을 짠 것 같았는데 오류가 반복해서 발생하였다. 이는 다음의 코드를 삽입하지 않아서 발생한 문제였다. 파이썬의 기본 재귀 깊이(1000)를 더 크게 설정해야 다른 test case의 문제를 풀 수 있다. import sys sys.setrecursionlimit(10 ** 6) 본 문제는 그래프에 관한 문제이다. 인풋 데이터는 하나의 큰 그래프를 형성한다. 이를 두 개의 서브 그래프로 나눴을..
-
[자료구조] [python] [BFS/DFS] Connected Cell in a GridData miner/Algorithm & Data structure 2021. 2. 24. 17:30
Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/ctci-connected-cell-in-a-grid/problem?h_r=internal-search DFS: Connected Cell in a Grid | HackerRank Find the largest connected region in a 2D Matrix. www.hackerrank.com 1) 방문한 점의 값이 1이라면, 방문한 점을 기준으로 거리 1에 해당하는 지점을 리턴하는 함수를 만든다. 단, 한 번이라도 방문하여 체크한 적이 있는지 확인하는 n *m 리스트를 따로 만든다(아래 코드에서 check 리스..
-
[Basic_Algorithm] [BFS/DFS] #2Data miner/Developer 2020. 1. 5. 13:07
DFS로 풀어야 하는 문제 같은데, 처음 접근하는데 있어서 DFS로 접근하지 못하였다. 시행착오에 대해서 기록해두려고 한다. 먼저 문제는 다음과 같았다. (출처; https://programmers.co.kr/ 프로그래머스 > 코딩테스트 연습 > 깊이/너비 우선탐색 > 네트워크) """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발(주의해야 할 부분)합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열..
-
[Basic_Algorithm] [BFS/DFS]Data miner/Algorithm & Data structure 2020. 1. 3. 15:13
트리는 크게 두 가지 방식으로 탐색(traverse)될 수 있다. 하나는 깊이 우선 탐색인 Depth-Frist-Search이고, 또 다른 것은 Breadth-Frist-Search이다. 프로그래머스의 연습문제를 통해서 DFS를 실제 문제에서 어떻게 적용해서 푸는지 알아보는 시간을 갖도록 해보자. 먼저 문제는 다음과 같았다. (출처; https://programmers.co.kr/ 프로그래머스 > 코딩테스트 연습 > 깊이/너비 우선탐색 > 네트워크) """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 네트워크란 컴퓨터 상호 간에 정보를..