컴퓨터 프로그래밍(암호학, 알고리즘)

[문제] 아래 그림과 같이 N x N개의 방에 임의의 양수가 들어 있다. 왼쪽 위에서 출발해서 맨 오른쪽 아래로 이동하려 할 때, 지나치는 방들의 숫자의 합이 최대가 되는 경로를 택했을 때 나오는 최댓값을 구하시오. (단, 이동은 오른쪽 혹은 아래쪽으로만 가능하고, 위로 혹은 왼쪽으로 이..

[문제] 아래와 같은 규칙성을 갖는 수열이 있을 때(피보나치 수열), 임의로 주어지는 n번째 수열 값을 구하시오. (위치 시작은 0) 0 1 1 2 3 5 8 13 ... (n-2) (n-1) n n = (n-2) + (n-1) 입력: 5 출력: 5 입력: 6 출력: 8 [풀이] 피보나치 수열의 규칙성은 다음과 같다. 1) f0) = 0 2) f(n) = f(n-2) + f(n-1) 재귀 호출로 ..

문제 아래 그림과 같은 규칙성을 가진다고 할 때(파스칼의 삼각형), 열번호와 행번호를 주면 해당 번호에 위치한 수를 리턴하는 함수를 제작하시오. (행과 열번호는 0부터 시작) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 ... 입력: 행번호 열번호 출력: 해당 행,열에 위치한 갓 ex) 입력: ..

Dynamic Programming은 산업공학에서 다루던 최적화문제를 구할 때 사용되는 기법으로 '동적 계획법'이라고 불리는 알고리즘이다. 이 기법의 근본 아이디어는 이미 계산된 값을 보관하고 있다가 다시 사용하는 것. 해서, '다이나믹 프로그래밍'이라 하면, 원래는 최적화문제를 푸는 방법을 의..

컴퓨터를 이용해서 최대공약수를 구할 때, 유클리드 알고리즘이 최적이라고 생각하기 쉬우나, 사실 그렇지 않다. 1961년 스페인 Josef Stein에 의해 고안된 이진 GCD알고리즘이 더 최적이다. 이 알고리즘에서는 나눗셈을 사용하지 않고, 오직 뺄셈, 홀짝판정, 짝수의 반감에 의해서만 gcd를 구..

<문제> 두 수 a, b가 있을 때, 두 수의 최대공약수를 GCD(a,b)라 표기하고, 최대공약수 관련해서 아래와 같은 수식이 만족된다고 알려져 있다. GCD(a,0) = a GCD(a,b) = GCD(b,a) GCD(a,b) = GCD(a-b,b) GCD(a,b) = GCD(a%b, b) 위와 같은 성질을 이용해서 두 수의 최대공약수를 구하시오. 예) GCD(30,280) = 30 <풀..

[문제] 큰 자릿수의 정수가 아래와 같이 byte형 배열로 표현될 때, 이 큰 정수를 2진수, 16진수의 배열로 표현하시오. ex1) a = {0x11,0x22} 일 때, a_2 = {1 ,0,0,0,1,0,0,1,0,0,0,1,0,} a_16 = {11,22} ex2)a={0x88,0x77,0x66,0x55,0x44,0x33,0x22,0x11} a_2 = ... a_16 = {88,77,66,55,44,33,22,11} [풀이] 변환해야할 정수의 크기가, 프로그..

## 문제 ## 아래의 그림처럼 1초에 한칸씩 이동하는 개미가 있다. 이 개미는 아래의 표에 나와있는 숫자 규칙대로 이동을 한다. 우리는 수 초 뒤에 개미가 과연 어떤곳에 위치하고 있는지를 알고 싶다!! (x < 200, y < 200) 사용자가 임의의 숫자(초)를 입력하면 개미의 위치를 좌표로 출력한..

## 문제 ## 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다. 두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다. 세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까? (출처: https://projecteuler.net ) ## 풀이 ## ##..

## 문제 ## 가게에 점원을 고용했는데 조금 띨띨해서 잔돈을 거슬러주는 것을 잘 하지 못한다. 구두쇠인 아저씨는 이로 인해서 손해가 나는 것을 알았다. 그래서 당신에게 손님에게 거슬러 줄 돈을 계산하는 프로그램을 만들어 달라고 부탁했다. 화폐 단위는 다음과 같다. • quartes $0.25 ..