Data miner/Algorithm & Data structure
-
[DP] [DFS] 백준 1520 내리막길 +aData miner/Algorithm & Data structure 2020. 3. 21. 15:49
문제 출처; https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지 www.acmicpc.net 위의 그림에서 왼쪽 끝에서부터 오른쪽 아래까지 지나갈 수 있는 경로 수에 대해서 구해야 한다. 단, 움직일 때 원래 위치한..
-
[자료구조] [heap] 대기 시간 최소화Data miner/Algorithm & Data structure 2020. 3. 4. 21:02
Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://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 문제는 다음과 같다. 피자 가게에서 고객들의 대기시간을 최소화하는 것을 목표로 평균 대기시간을 구하는 것이다. 피자 만드는 시간은 각기 다르며, 주문이 들어올 때, 선입선출(First in, Fir..
-
[자료구조] [heap] 업데이트 되는 array값의 중앙값 구하기Data miner/Algorithm & Data structure 2020. 3. 3. 17:33
Hackerrank의 Data structures 관한 문제 중에서 Hard에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/find-the-running-median/problem?h_r=internal-search Find the Running Median | HackerRank Find the median of the elements after inputting each element. www.hackerrank.com 연속적으로 주어지는 배열의 평균값들을 반복적으로 구하는 문제이다. [12,4,5,3,8,7]이 주어지면 앞에서부터 한 개씩 차례대로 추가하여 추가된 값들까지의 중앙값을 구하고, 이들이 포함된 리스트를 구하면 ..
-
#String_slicing #문자열 슬라이싱하기Data miner/Algorithm & Data structure 2020. 1. 23. 19:37
코드를 짤 때, 이젠 코드의 시간 복잡도를 꼭 염두하며 짜는 습관이 생겼다. 오늘 풀었던 문제는 문자열이 주어졌을 때, index로 접근하고자 할 때, 문자열 자체가 1,000,000까지 늘어날 수 있다면 이를 어떻게 효과적으로 접근할지에 대해서 다루고자 한다. 바이너리 시퀀스형(bytes, bytearray, memoryview)를 사용하면, silcing을 할 때 copying 하는 방식으로 접근하지 않아 보다 효율적이라고 한다. (*문제에서는 엄밀히 말하면, slicing이 아니라 index를 통한 접근이기 때문에 사실 memoryview를 활용했을 때, 그렇지 않았을 때보다 훨씬 성능이 좋지 않았다. Slicing문제에서는 memoryview를 통해서만 풀어야 한다.) 슬라이싱 문제의 경우 시간복..
-
[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/ 프로그래머스 > 코딩테스트 연습 > 깊이/너비 우선탐색 > 네트워크) """""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""" 네트워크란 컴퓨터 상호 간에 정보를..