Cara's Moving Cara's Moving

문제 소스 링크 : 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개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다...

문제 소스 링크 : 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 ≤..

문제 소스 링크 : 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보..

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]일 경우의 최대값을 저장하고, 두 번째 원..

Hackerrank의 Data structures 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/equal/problem?isFullScreen=true 문제의 제약 조건은 다음과 같이 두 가지가 있었다. - "한 명을 제외하고 초콜릿을 나눠줄 수 있다." - "결과적으로 배분한 초콜릿의 개수가 같아야 연산이 끝이 난다." 문제를 풀어나가는 아이데이션 과정부터 쉽지 않았다. 특히 첫번째 조건을 코드로 처리하는 데 있어서 어려움을 겪었다. 오직 딱 한 명을 제외하고 숫자를 더해서(1,2,5) 모든 Array의 숫자들을 동일하게 만드는 것이 어려웠다. 구글링을 통해 문제를 해결해 나갈 수 있었는데, 먼..

Hackerrank의 Data structures 관한 문제 중에서 Algorithms에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/coin-change/problem?isFullScreen=true 문제를 푸는 아이디어를 떠올리는 것은 어렵지 않다. Coins 리스트에서 앞의 원소의 코인부터 시작해서 무제한으로 제공되는 코인을 통해 가능한 금액의 경우의 수를 구하고, 이후 인덱스의 코인들의 조합을 통해 가능한 금액을 업데이트 하는 식으로 구하면 된다. 하지만, 실제 이를 코드로 구현하는 과정에서 시간이 소요되었다. 실제 풀이한 코드 방법은 다음과 같다. 문제에서 주어진 우리가 만들어야 하는 금액이 n이고, Coins 리스트에..

Hackerrank의 Algorithms 관한 문제 중에서 Medium에 속하는 문제이다. 원 문제 링크는 다음을 따라가보자. https://www.hackerrank.com/challenges/cut-the-tree/problem?isFullScreen=true * 재귀를 통해서 문제를 풀려고 했는데 제대로 알고리즘을 짠 것 같았는데 오류가 반복해서 발생하였다. 이는 다음의 코드를 삽입하지 않아서 발생한 문제였다. 파이썬의 기본 재귀 깊이(1000)를 더 크게 설정해야 다른 test case의 문제를 풀 수 있다. import sys sys.setrecursionlimit(10 ** 6) 본 문제는 그래프에 관한 문제이다. 인풋 데이터는 하나의 큰 그래프를 형성한다. 이를 두 개의 서브 그래프로 나눴을..

버킷 정렬(Bucket Sort)의 단점을 해소하기 위한 알고리즘이 기수 정렬 알고리즘(Radix Sort)이다. 각 자리 수에 해당하는 숫자에 정렬하고자 하는 숫자들을 차례대로 저장하는 방식이다. 이미지 출처; www.btechsmartclass.com/data_structures/radix-sort.html Data Structures Tutorials - Radix Sort Algorithm with an example Radix sort is one of the sorting algorithms used to sort a list of integer numbers in order. In radix sort algorithm, a list of integer numbers will be sorted..