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

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 ..

##문제## N x M 크기의 바닥에 타일을 붙이려고 합니다. 단, 타일을 왼쪽 그림과 같이 바닥의 테두리에만 붙이고 싶습니다. 붙이려고 하는 타일이 P x 1 크기의 한가지 종류만 사용한다고 할 때, 타일이 겹치는 부분 없이 바닥을 모두 덮을 수 있는지 확인할 수 있는 프로그램을 만들어 주세요..

문제 게시판에 포스터를 붙일 때, 이미 포스터가 붙여져 있으면, 기존의 포스트 면적의 절반 이상은 가릴 수 없도록 되어 있다. 만약 두 개의 포스터가 겹쳐져서 붙여져 있을 때, 아래 포스터의 보이는 부분의 면적을 구하라. 포스터는 둘 다 직사각형이며, 게시판 벽에 평행하게 붙어 있..

############# 문제 ############# a,b,c,d,e,f,g,h의 8개 영문자로 만들 수 있는 순열수는 8! = 40,320이다. 이 순열들을 사전 순서로 배열하고 이들의 순서를 적어보면 아래와 같다. 문자열 순서 abcdefgh 1 abcdefhg 2 abcdegfh 3 ... ... fbhacdeg 26521 ... ... hgfedcba 40320 이렇게 8개의 영문자로 만들어진 순열이 주어질..