전체 글
-
[자료구조] [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 리스..
-
[Spark] 아파치 스파크 개념 정리중Data miner/Development log 2021. 2. 17. 18:32
스파크는 컴퓨터 클러스터에서 작업을 조율하는 프레임워크. 클러스터의 데이터 처리 작업을 관리 및 조율. 데이터프레임의 추상화를 통해 대용량의 데이터 처리 가능. 스트림처리, 그래프처리, SQL, 머신러닝 기능 제공 스파크 애플리케이션은 드라이버 프로세스(driver process) 와 익스큐터 프로세스(Executors)로 구성 드라이버 프로세스는 스파크 애플리케이션의 중심 본체로서, main()함수 실행 및 SparkContext를 생성함 익스큐터 프로세스는 드라이버 프로세스가 할당한 작업을 수행. 드라이버가 할당한 코드 실행/ 진행 상황을 다시 드라이버 노드에 보고 스파크 스트리밍 : 다양한 데이터 소스에서 유입되는 실시간 스트리밍 데이터를 처리하는 프레임워크 장애가 발생하면 연산 결과를 자동으로 복..
-
[자료구조] [python] [heapq] Minimum Average Waiting TimeData miner/Algorithm & Data structure 2021. 2. 17. 10:25
다음의 문제는 heapq을 활용해서 푸는 문제에 해당한다. Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/minimum-average-waiting-time/problem Minimum Average Waiting Time | HackerRank Calculate the minimum average wait time of a person to receive his/her pizza? www.hackerrank.com 풀이 로직은 다음과 같다. 일단 어떤 작업이 끝난 시점에, 들어온 작업들 중에서 가장 작업량이 적은 주문을 선택해야, 전체의 평균 대기 시간을 줄일 수 ..
-
[자료구조] [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..