Data miner/Algorithm & Data structure
-
[자료구조] [python] Down to Zero IIData miner/Algorithm & Data structure 2021. 2. 6. 19:54
Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/down-to-zero-ii/problem Down to Zero II | HackerRank Find the minimum number of moves to reduce N to zero using the constraints given. www.hackerrank.com queue 자료형을 이용해서 문제를 풀지 않았다. 문제에 제시된 N의 크기의 list를 생성한 후, 2부터 값을 하나씩 보면서 가능한 곱의 값들을 최소값과 비교하며, 값을 업데이트 하는 식으로 풀었다. 다만, 7과 같이, 소수인 경우 7->6->5..
-
[자료구조] [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) 성능으로 원소를 추..
-
[자료구조] [python] Balanced Brackets (stack)Data miner/Algorithm & Data structure 2021. 2. 2. 18:30
Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/balanced-brackets/problem Balanced Brackets | HackerRank Given a string containing three types of brackets, determine if it is balanced. www.hackerrank.com Stack의 개념과 가장 맞닿아 있는 문제이다. 빈출되었던 문제이기도 하다. 문제를 풀이하는데 있어서 어려웠던 점은 다음과 같다. 괄호의 순서가 '균형되어'(Balanced) 있다면, '{[()]}' 완전히 양쪽의 대괄호가 균형된 예시만을 처리..
-
[자료구조] [python] Equal StacksData miner/Algorithm & Data structure 2021. 2. 1. 22:05
Hackerrank의 Data structures 관한 문제 중에서 Easy에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. www.hackerrank.com/challenges/equal-stacks/problem Equal Stacks | HackerRank Equalize the piles! www.hackerrank.com 문제의 하단에 문제에 서술된 상황을 묘사하는 그림이 있어서, 이해하는 데 어렵지 않았다. 문제를 풀이하는 데 있어서 'stack' 자료구조를 활용하는 것이 도움이 되었다. 스택은 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조다. 파이썬에서는 append()와 pop() 메서드로 스택을 구현한다. 아래 그림의 h1 실린더의 블록은 [3,2,1,1,1]로 구성되어 ..
-
[Machine learning] Evaluating metric 의 역할 및 설정하는 방법Data miner/Algorithm & Data structure 2020. 11. 22. 20:09
머신러닝의 프로세스에는 1) 아이디어를 설정하고, 2) 특정 아이디어를 시도해보고, 3) 그 아이디어가 목적에 맞는 것이었는지 확인하는 단계가 있다. 아이디어를 구체화 할 수 있는 알고리즘 모델이 문제를 푸는 데 있어서 적절한 것인지, 성능을 평가하기 위해서 평가 지표(Evaluating metric)를 사용한다. 어떤 알고리즘이 우수한지 가늠하기 위해서 보통은 하나의 평가 지표를 사용하고자 하며, 머신러닝 영역에서는 정밀도(Precision)와 재현율(Recall)의 조화 평균인 F1 score을 사용한다. 그러나, 하나의 평가 지표만으로 하나의 알고리즘을 선택하기가 어려울 수 있다. 모델을 만들거나 모델을 실제 응용 분야에서 활용하는데 있어서 영향을 미치는 외적 조건들을 최소한으로 만족시켜야 하는 경..
-
[Union_find][Algorithm] 백준 4195. 친구네트워크Data miner/Algorithm & Data structure 2020. 4. 6. 20:37
Union_find를 사용해서 푸는 문제들을 여러 풀면서 정리해 보았다. 문제를 간단히 정리하자면, input으로 들어오는 두 친구 정보 (ex. ("Fred", "Barney")) 사이에 존재하는 친구 수를 구하는 문제이다. 다만, 이 입력되는 친구가 서로 이미 친구라고 가정한다. 또한, 친구 수에는 본인도 포함한다. 따라서, Fred는 Barney는 본인을 포함하여 최소 2의 값을 가진다. https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을..
-
[DP] [Algorithm] Fractional Knapsack AlgorithmData miner/Algorithm & Data structure 2020. 3. 26. 16:30
https://pongdangstory.tistory.com/487 이전 포스팅에서, Unfractional knapsack problem을 다루었다. 이번에는 가방에 물건을 담을 때, 물건의 일부를 담는 경우는 어떠할까? 믹서기 같은 물건의 경우, 믹서기를 쪼개면 그 기능을 다하지 못하기 때문에 쪼갤 수 없는 반면에, 초콜릿이라고 한다면, 초콜릿은 소분해서 담을 수 있고 그 가치도 그 소분한 가치만큼에 해당하기 때문에 쪼갤 수 있다. 이 경우 그리디 알고리즘의 접근법으로 비교적 간단히 풀 수 있다. 이전의 input과 동일하게 문제가 주어졌다고 가정하자. K는 가방에 담을 수 있는 최대 무게 상한선이다. 즉, 물건이든, 물건의 부분이든 이 K kg의 무게를 넘을 수 없다. stuff_array는 다음과..
-
[DP][Algorithm] Knapsack Algorithm. 백준 12865 평범한 가방Data miner/Algorithm & Data structure 2020. 3. 26. 15:53
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 냅색알고리즘이라고 불리는 이 유명한 문제는 다음과 같다. 가방에 가치를 극대화하도록 물건들을 담아야 한다. 이 때 가방은 특정 무게 이상을 담을 수 없다. 제한된 K kg의 이하의 물건들을 담을 수 있다. 물건들은 (Weight, Value)로 무게와 가치라는 원소를 가지고 있다...