https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 활용하는 문제이다. 다이나믹 프로그래밍은 주어진 문제를 여러 개의 부분 문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다. 분할정복 문제와도 비슷한데 다른 점은 다이나믹 프로그래밍은 겹치는 문제가 발생하기 때문에 메모이제이션 등이 필요하다. 이미 계산한 정보를 배열에 저장하여 나중에 동일한 계산을 해야할 때 저장된 값을 반환한다. 첫번째는 top-down 방식으로 작성하였다. 계산한 정보를 저장할 배열을 d라고 했고 1000001 크기를 가지도록 했다. f(n)이 최소횟수라 하자...
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다. 다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다. N이 주어졌을 때, (r, www.acmicpc.net c언어로 재귀함수를 이용하여 문제를 풀었다. https://ggsmainstay0297.tistory.com/m/2 p1074 https://..
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net [알고리즘] 큐의 개념을 이용한다. 큐는 FIRST-IN, FIRST-OUT 이다. 따라서 k주기가 아닐때는 delete한다음 큐에 다시 집어넣어 주고 k주기일때는 그냥 delete해주면 된다. python3로 제출했을때는 시간초과가 떠서 실패하였고 pypy3로 제출하니 성공하였다. 시간초과가 난 이유를 다음과 같은 이유라고 예상하였다. n=3, k=3일때를 생각해보면 [인덱스] 012 [값] 123 (초기 큐) [인덱스] 0123 [값] 231 [인덱스] 01234 [값] 312 [인덱..
https://www.hackerrank.com/challenges/sparse-arrays/problem Sparse Arrays | HackerRank Determine the number of times a string has previously appeared. www.hackerrank.com 위의 사진과 같이 첫번째 줄에는 strings배열에 입력할 문장의 개수를 입력한다. 그다음 그 개수만큼 문장들을 입력한다. 입력을 했으면 이번에는 queries 배열에 입력할 문장의 개수를 입력한다. 그리고 그 개수만큼 입력을 한다. 출력되는 값은 queries 배열에 입력한 문장이 strings안에 몇개있는지이다. 즉 sample을 살펴보면 queries에 입력되는 값은 aba, xzxb, ab이고 이들..
https://www.hackerrank.com/challenges/staircase/problem Staircase | HackerRank Print a right-aligned staircase with n steps. www.hackerrank.com sample input과 output 과 같이 값을 입력하면 그에 맞게 계단이 나타나면 된다. 6을 입력하면 6개의 계단이 나타나는 것이다. 계단을 출력하는 함수 각 계단에서 맨 앞에서 빈칸이 출력되어야 하니 빈칸 부터 출력하도록 한다. j=0부터 n-1-i전까지 빈칸을 출력한다. n-1-i개 만큼 빈칸이 출력되는 것이다. 그리고 k가 0부터 i까지 #을 출력을 한다. 즉 i+1개 만큼 #이 출력이 된다. 이런식으로 코드를 짜면 계단을 만들 수 있다.
Recursive Digit Sum - https://www.hackerrank.com/challenges/recursive-digit-sum/problem Recursive Digit Sum | HackerRank recursively sum all digits in a number until there is only one left www.hackerrank.com 파라미터로 전달받는 숫자를 각 자리마다 더해서 일의 자리가 될 때 return 하는 함수를 만들면 된다. n=148, k=3일때를 예시로 들어보자. n은 파라미터로 전달하는 숫자이고 이를 k번 곱하면 P가 된다. 즉, P는 148148148이 된다. super_digit(P) = super_digit(148148148) = super_di..
