전체 글
-
[백준] [Brute Force] 제곱수 찾기Data miner/Algorithm & Data structure 2022. 11. 14. 18:35
문제 소스 링크 : https://www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지 www.acmicpc.net 제곱수 찾기 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 4297 1392 1105 31.973% 문제 N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다. 연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다...
-
[백준] [DP] 제곱수의 합Data miner/Algorithm & Data structure 2022. 11. 11. 15:07
문제 소스 링크 : https://www.acmicpc.net/problem/1699 문제 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다. 주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N이 주어진다. (1 ≤..
-
[백준] [DP] 연속합 / 리스트의 임의의 수열에서 연속된 합의 값 중 최대값 찾기Data miner/Algorithm & Data structure 2022. 11. 7. 16:03
문제 소스 링크 : https://www.acmicpc.net/problem/1912 연속합 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 (추가 시간 없음) 128 MB 111739 39798 28006 34.357% 문제 n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다. 예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다. 입력 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보..
-
[코드리뷰] Transformer의 positional_embeddingData miner/Information Retrieval 2022. 11. 2. 21:59
논문을 구현한 코드에서 단어 토큰들의 위치 정보를 임베딩 하기 위한 여러 방식들이 있는데, "absolute", "relative_key", "relative_key_query"가 그에 해당한다. - 'absolute'의 경우 - position_embeddings이란 이름으로 토큰 시퀀스의 위치 인덱스를 나타내는 정수형 타입의 텐서값을 받아 임베딩한다. (max embedding 크기 X hidden size) - word_embeddings, token_type_embeddings, position_embeddings의 값은 추후에 합산되어 학습되므로 이들의 임베딩 hidden size는 동일하다. Embedding X by Y 에서 Y값이 동일하다는 의미. - 한편 토큰 시퀀스의 위치 인덱스의 경우..
-
[자료구조] [python] [Dynamic Programming] Sherlock and CostData miner/Algorithm & Data structure 2022. 2. 14. 13:24
Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/sherlock-and-cost/problem?isFullScreen=true - A Array의 앞에서부터 원소값을 결정한다고 하였을 때, A[i] - A[i-1]를 최대화 시키는 값을 가지는 A[i]의 경우의 수는 결국 A[i] =B[i] 이거나 A[i] = 1 이다. 이와 같은 성질을 이용하여, temp라는 임시 Array에 초기값이 (0, 0) 튜플을 원소로 가지는 배열을 만든다. 이 temp Array의 경우, 각 튜플의 첫번째 원소는 A[i]가 B[i]일 경우의 최대값을 저장하고, 두 번째 원..
-
[자료구조] [python] [Dynamic Programming] EqualData miner/Algorithm & Data structure 2022. 2. 12. 00:42
Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/equal/problem?isFullScreen=true 문제의 제약 조건은 다음과 같이 두 가지가 있었다. - "한 명을 제외하고 초콜릿을 나눠줄 수 있다." - "결과적으로 배분한 초콜릿의 개수가 같아야 연산이 끝이 난다." 문제를 풀어나가는 아이데이션 과정부터 쉽지 않았다. 특히 첫번째 조건을 코드로 처리하는 데 있어서 어려움을 겪었다. 오직 딱 한 명을 제외하고 숫자를 더해서(1,2,5) 모든 Array의 숫자들을 동일하게 만드는 것이 어려웠다. 구글링을 통해 문제를 해결해 나갈 수 있었는데, 먼..
-
[자료구조] [python] [Dynamic Programming] The Coin Change ProblemData miner/Algorithm & Data structure 2022. 2. 8. 20:15
Hackerrank의 Data structures 관한 문제 중에서 Algorithms에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true 문제를 푸는 아이디어를 떠올리는 것은 어렵지 않다. Coins 리스트에서 앞의 원소의 코인부터 시작해서 무제한으로 제공되는 코인을 통해 가능한 금액의 경우의 수를 구하고, 이후 인덱스의 코인들의 조합을 통해 가능한 금액을 업데이트 하는 식으로 구하면 된다. 하지만, 실제 이를 코드로 구현하는 과정에서 시간이 소요되었다. 실제 풀이한 코드 방법은 다음과 같다. 문제에서 주어진 우리가 만들어야 하는 금액이 n이고, Coins 리스트에..
-
[자료구조] [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) 본 문제는 그래프에 관한 문제이다. 인풋 데이터는 하나의 큰 그래프를 형성한다. 이를 두 개의 서브 그래프로 나눴을..