자료구조
-
[자료구조] [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] Shortest Reach in a GraphData miner/Algorithm & Data structure 2021. 2. 25. 11:12
Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/ctci-bfs-shortest-reach/problem?h_r=internal-search BFS: Shortest Reach in a Graph | HackerRank Implement a Breadth First Search (BFS). www.hackerrank.com 노드의 연결정보를 나타내는 n * n 매트릭스를 만든다. 두 노드가 연결되어 있다면 1, 아니면 0. 특히, 매트릭스의 인덱스가 0부터 시작하므로, (node값-1) 위치에 넣어야 함을 유의한다. 이 매트릭스는 대각선들의 값이 모두 0인 대칭행렬의 ..
-
[자료구조] [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 리스..
-
[자료구조] [heapq] Jesse and CookiesData miner/Algorithm & Data structure 2021. 2. 9. 18:30
다음의 문제는 heapq을 활용해서 푸는 문제에 해당한다. Hackerrank의 Data structures 관한 문제 중에서 Easy에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/jesse-and-cookies/problem Jesse and Cookies | HackerRank Calculate the number of operations needed to increase the sweetness of the cookies so that each cookie in the collection has a sweetness >=K. www.hackerrank.com "전체 쿠키의 당도 정보가 포함되어 있는 리스트중에서, 전체 쿠키가 만족시켜야..
-
[자료구조] [python] [heapq] QHEAP1Data miner/Algorithm & Data structure 2021. 2. 9. 16:35
우선순위 큐(priority queue)는 각 항목에 우선순위가 있는 스텍/큐이다. 파이썬의 heapq 모듈에는 이를 구현 할 수 있는 힙heap 자료형이 있다. 힙(Heaps)는 이진트리이며, 부모노드가 자식노드보다 값이 작거나 같다. 루트인 heap[0]가 heap의 모든 요소들의 최소값이다. 배열, 리스트에서 가장 작은/큰 요소에 반복적으로 접근하는 작업에 유용하다. heapq.heapify(list) : 리스트를 힙으로 변환하는 시간 복잡도 O(n) heapq.heappop(list) : 가장 작은/큰 값 호출시 처리하는 시간 복잡도 O(1) heapq.heappush(list, item) : 값 조회, 새로운 값 추가, 수정시 처리하는 시간 복잡도는 O(log n) heapq.heappushpo..
-
[자료구조] [python] Truck TourData miner/Algorithm & Data structure 2021. 2. 8. 18:27
Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/domains/data-structures?filters%5Bsubdomains%5D%5B%5D=queues Solve Programming Questions | HackerRank Join over 7 million developers in solving code challenges on HackerRank, one of the best ways to prepare for programming interviews. www.hackerrank.com 트럭이 전 펌프를 순회할 수 있는 펌프 지점을 찾되, 가장 index가 작은 값을 찾아야 하..
-
[자료구조] [python] Queries with Fixed Length (min-max)Data miner/Algorithm & Data structure 2021. 2. 7. 21:43
Hackerrank의 Data structures 관한 문제 중에서 Hard(success rate 60%)에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/domains/data-structures?filters%5Bstatus%5D%5B%5D=unsolved&filters%5Bstatus%5D%5B%5D=solved&filters%5Bsubdomains%5D%5B%5D=queues&badge_type=problem-solving Solve Programming Questions | HackerRank Join over 7 million developers in solving code challenges on HackerRank, one of the best w..
-
[자료구조] [python] Castle on the Grid (deque)Data miner/Algorithm & Data structure 2021. 2. 3. 18:30
Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/castle-on-the-grid/problem Castle on the Grid | HackerRank Determine the number of steps to move a castle to the goal position on a given grid. www.hackerrank.com Deque는 python의 collection 모듈에 구현된 객체/자료형이다. stack과 que의 일반형태의 자료형이며, Deque는 thread-safe (스레드 안전)을 지원하며, 자료의 양방향에서 O(1) 성능으로 원소를 추..