Computer & Books

재귀와 완전탐색 우선 재귀 함수에 대해 설명하기 전에 두 코드를 비교해보자. 1. 반복문을 통한 1 부터 n 까지의 합 int sum(int n) {    int ret=0,i;    for(int i=1; i <= n; i++)       ret += i;    return ret; } 2. 재귀 함수를 통한 1 부터 n 까지의 합 int recursiveSum(int n) {    if (n==1) return 1; //더 이상 쪼개지지 않을 때    return n + recursiveSum(n-1); } 모든 재귀함수는 위와 같이 더 이상 쪼개지지 않는 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문을 포함해야한다. 이때 쪼개지지 않는 가장 작은 작업들을 가리켜 재귀 호출의 기저 사례 라고 한다. 재귀호출은 1번과 같은 반복문과 그리 큰 차이는 없지만 코딩을 훨씬 간편하게 해줄 수 있다. 재귀 함수는 완전 탐색이라는 무식하게 모두 세는 방식을 사용하여 알고리즘을 짤 때 좋다. 처음에 문제를 파악한 뒤 재귀 함수를 써야한다면 기저 사례를 선택해야한다. 여기서 팁이 있다면, 입력이 잘못되었거나 범위에서 벗어난 경우도 기저 사례로 택해서 처음에 처리하면 함수 호출 과정에서 오류 검사를 할 필요가 없어지기 때문에 속도가 빨라진다. 많이 등장하는 완전 탐색 유형 1. 모든 순열 만들기 서로 다른 N 개의 원소를 일렬로 줄 세운 것을 순열이라고 한다. int factorial(int n) { if (n <= 1) return 1; //위에서 본 기저 사례 return n*factorial(n - 1); } 2. 모든 조합 만들기 서로 다른 N 개의 원소 중에서 R 개를 순서 없이 골라낸 것을 조합이라고 한다. int binco(int n,...

알고리즘 패러다임 공부 시작. 1. 무식하게 푸는 재귀함수를 시작으로 2. 분할정복 알고리즘 ---- 병합 정렬                             ---- 퀵 정렬 3. 동적 계획법 4. 탐욕법 5. 조합 탐색 출처 : 알고리즘 문제해결 전략

삼각형의 종류를 판별하라 삼각형의 세변의 길이가 주어질때 직각삼각형인지, 예각삼각형인지, 둔각 삼각형인지를 판별하시오 --------------------------------------------------------------------- package trycatch; import java.util.Scanner; public class no4 { public static void main(String [] args){ Scanner sc=new Scanner(System.in); System.out.print("숫자 3개를 입력하시오 : "); int fst=sc.nextInt(); int snd=sc.nextInt(); int lst=sc.nextInt(); String result=Trian(frs,scd,lst); System.out.println(result); } static String Trian(int a,int b,int c){ int sum=(int)Math.pow(a,2)+(int)Math.pow(b,2); if(sum==Math.pow(c,2))return "직각"; else if(sum>Math.pow(c,2))return "예각"; else return"둔각"; } } ------------------------------------------------------------------------------- 이렇게 풀었으나 정답은 입력값으로 하는 것을 원한게 아니라 그냥 고정값을 원했다. 이게 더 어려워 보여서 그냥 이걸로 올릴란다.

영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p) 이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다. 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p 2파운드를 만드는 서로 다른 방법은 모두 몇가지나 있습니까? ------------------------------------------------------------- target = 200 coins = [1, 2, 5, 10, 20, 50, 100, 200] ways = [1] + [0]*target for coin in coins:     for i in range(coin, target+1):         ways[i] += ways[i-coin] print ways[-1] ----------------------------------------------------------------- 이런 알고리즘 사용하는 게 아직 쉽지 않다.. 나는 for문 여러개 만들어서 했지만 답은 dp 알고리즘이 더 간단하다. 아직 읽지 못한 알고리즘 책을 읽어야겠다..

각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다. 1634 = 1 4  + 6 4  + 3 4  + 4 4 8208 = 8 4  + 2 4  + 0 4  + 8 4 9474 = 9 4  + 4 4  + 7 4  + 4 4 (1 = 1 4 의 경우는 엄밀히 말해 합이 아니므로 제외합니다) 위의 세 숫자를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다. 그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까? ------------------------------------------------------------------------------------- res=0 ans=0 num=2 while True:     strNum=str(num)     for i in range(0,(len(strNum))):         res+=pow(int(strNum[i]),5)     if(res==num):         ans+=num     num+=1     res=0     if(num==200000):break print ans ---------------------------------------------------------------------------------------- 반복문 종료조건을 정확히 했어야 했는데 수학적으로 접근하기 힘들어서 그냥 무한루프 돌리고 마지막 값 종료 조건으로 해서 풀었다. 뭔가 맞히고도 찜찜하다...

해당하는 모든 소수를 출력하라 소수란 1과 자기 자신만을 약수로 가지는 수이다. 100이하의 자연수 중 모든 소수를 출력하시오. 소수를 오름차순으로 출력한다. 각 출력값 사이는 공백으로 구분하고, 출력값 5개 마다 줄바꿈을 한다. ------------------------------------------------------------------- public class Main { public static void main(String[] args) { int count=0,count1=1;         int i,j;         System.out.print(2+" ");         for(i=3;i             for(j=2;j                 if(i%j==0)break;                 else count++;             }             if(count1==4 && count==i-2){             System.out.println(i+" ");             count1=0;                 continue;             }     ...

2 ≤  a  ≤ 5 이고 2 ≤  b  ≤ 5인 두 정수  a ,  b 로 만들 수 있는  a b 의 모든 조합을 구하면 다음과 같습니다. 2 2 =4,  2 3 =8,  2 4 =16,  2 5 =32 3 2 =9,  3 3 =27,  3 4 =81,  3 5 =243 4 2 =16,  4 3 =64,  4 4 =256,  4 5 =1024 5 2 =25,  5 3 =125,  5 4 =625,  5 5 =3125 여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다. 4,  8,  9,  16,  25,  27,  32,  64,  81,  125,  243,  256,  625,  1024,  3125 그러면, 2 ≤  a  ≤ 100 이고 2 ≤  b  ≤ 100인  a ,  b 를 가지고 만들 수 있는  a b 는 중복을 제외하면 모두 몇 개입니까? ---------------------------------------------------------- result=list() for i in range(2,101):     for j in range(2,101):         result.append(pow(i,j)) result=list(set(result)) n=len(result) print n ------------------------------------------------------------- 문제가 점점 가면 갈수록 쉬워지고 코드가 짧아지니 ...

주어진 숫자를 한글로 읽어보자 숫자단위에 아직 미숙한 어린 아이들을 대상으로 숫자가 한글로 출력되는 프로그램을 만들고자 한다. --------------------------------------------------------------------------------------------------- package trycatch; import java.util.Scanner; public class no2 { public static void main(String[] args){ Scanner scan=new Scanner(System.in); int i,plc=0,result; String numString=null; int num=scan.nextInt(); String[] han={"일","이","삼","사","오","육","칠","팔","구"}; String[] han1={" ","십","백","천","만","십만","백만","천만","억",}; no2 myNo2=new no2(); int findNum=myNo2.find(num)-1; for(i=findNum;i>=0;i--){ plc=(int) (num%Math.pow(10,i)); plc=num-plc; result=(int)(plc/Math.pow(10,i)); result=result%10; switch(result) { case 1 : numString="일"; break; case 2 : numString="...

숫자 1부터 시작해서 우측으로부터 시계방향으로 감아 5×5 행렬을 만들면 아래와 같이 됩니다. 21  22 23 24  25 20   7   8   9  10 19  6   1   2 11 18   5   4   3  12 17  16 15 14  13 여기서 대각선상의 숫자를 모두 더한 값은 101 입니다. 같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선상의 숫자를 더하면 얼마가 됩니까? --------------------------------------------------------------------------- result=0 for i in range(2,502):     result+=2*(pow((2*i-1),2)+pow((2*i-3),2)+2*(i-1)) print result+1 ----------------------------------------------------------------------------- 그냥 수열화해서 풀었다. 

오일러는 다음과 같은 멋진 2차식을 제시했습니다. n 2  +  n  + 41 이 식의  n 에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다. 하지만  n  = 40일 때의 값 40 2  + 40 + 41 은 40×(40 + 1) + 41 이므로 41로 나누어지고,  n  = 41일 때 역시 41 2  + 41 + 41 이므로 소수가 아닙니다. 컴퓨터의 발전에 힘입어  n 2  − 79 n  + 1601  이라는 엄청난 2차식이 발견되었는데, 이것은  n 이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다. 아래와 같은 모양의 2차식이 있다고 가정했을 때, n 2  +  an  +  b     (단  |  a  | < 1000, |  b  | < 1000) 0부터 시작하는 연속된  n 에 대해 가장 많은 소수를 만들어내는 2차식을 찾아서, 그 계수  a 와  b 의 곱을 구하세요. ------------------------------------------------------------------------------- import math def get_primes(n):     numbers = set(range(n, 1, -1))     primes = []     while numbers:         p = numbers.pop()         primes.append(p)       ...

피보나치 수열은 아래와 같은 점화식으로 정의됩니다. F n  = F n -1  + F n -2   (단, F 1  = 1, F 2  = 1). 이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다. F 1  = 1 F 2  = 1 F 3  = 2 F 4  = 3 F 5  = 5 F 6  = 8 F 7  = 13 F 8  = 21 F 9  = 34 F 10  = 55 F 11  = 89 F 12  = 144 수열의 값은 F 12 에서 처음으로 3자리가 됩니다. 피보나치 수열에서 값이 처음으로 1000자리가 되는 것은 몇번째 항입니까? ------------------------------------------------------------------ a,b,i=0,1,1 while b     a,b=b,a+b     i=i+1 print b , i ------------------------------------------------------------------- 제일 적은 코드로 쓴 것이다. a,b=b,a+b라는 코드를 구글 보고 찾아냈다. 파이썬이라 그런지 굉장히 간편했다.

여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일  names.txt  이 있습니다 (우클릭해서 다운로드 받으세요). 이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다. 먼저 모든 이름을 알파벳 순으로 정렬합니다. 각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 숫자(A=1, B=2, ..., Z=26)를 모두 더합니다. 여기에 이 이름의 순번을 곱합니다. 예를 들어 "COLIN"의 경우, 알파벳에 해당하는 숫자는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다. names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까? ---------------------------------------------------------------------- result=0 sum=0 li=list() f = open("C:/Users/15U530/Desktop/names.txt",'r') lines = f.readline() li=lines.split(',') li.sort() for i in range(0,5163):     for j in range(0,len(li[i])-2):         sum+=ord(li[i][j+1])-64     result+=sum*(i+1)     print result     sum=0 f.close() -------------------------------------------------------------------------- 이때까지 파일 입출력과 문자열이 나오면 굉장히 힘들었지만 파이썬으로 하니 함수가 다 있어 너무 편하다. 좋다. 프로젝트 오일러 문제는 파이썬으로 풀어야겠다.

n 의 약수들 중에서 자신을 제외한 것의 합을  d ( n ) 으로 정의했을 때, 서로 다른 두 정수  a ,  b 에 대하여  d ( a ) =  b  이고  d ( b ) =  a  이면 a ,  b 는 친화쌍이라 하고  a 와  b 를 각각 친화수(우애수)라고 합니다. 예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은  d (220) = 284 입니다. 또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로  d (284) = 220 입니다. 따라서 220과 284는 친화쌍이 됩니다. 10000 이하의 친화수들을 모두 찾아서 그 합을 구하세요. --------------------------------------------------------------------------- sum=0; sum2=0; Fsum=0; for i in range(2,10001):         for j in range(1,i):         if i%j==0:             if i==j:                 break;             sum+=j;         else:             continue;     for k in range(1,sum):         if sum%k==0: ...

n ! 이라는 표기법은  n  × ( n  − 1) × ... × 3 × 2 × 1을 뜻합니다. 예를 들자면 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 이 되는데, 여기서 10!의 각 자리수를 더해 보면 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 입니다. 100! 의 자리수를 모두 더하면 얼마입니까? --------------------------------------------------------------------------------- ans = 1; i=1 j=1; sum; for j in range(1,100):      ans *= j; print ans; while True:     if ans==0:         break;          if i==1:         sum = ans%10;     else:         sum+=ans%10;          ans= ans // 10; //버젼 3으로 올라가면서 자동으로 소수점을 없앤다지만 버젼 2는 아직                              //연산자를 써야 소수점이 없어진다.     i=i+1;       print sum; ------------------------------------------------------------------------------ 파이썬은 프로젝트 오일러를 풀기에 적합한...

프로젝트 오일러 17 1부터 5까지의 숫자를 영어로 쓰면 one, two, three, four, five 이고, 각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다. 1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요? 참고:  빈 칸이나 하이픈('-')은 셈에서 제외하며, 단어 사이의 and 는 셈에 넣습니다.   예를 들어 342를 영어로 쓰면 three hundred and forty-two 가 되어서 23 글자,   115 = one hundred and fifteen 의 경우에는 20 글자가 됩니다. ----------------------------------------------------------------------------- #include void main() {  int sum = 854;  // 1부터 99까지 합  int num[9] = { 3, 3, 5, 4, 4, 3, 5, 5, 4 }; //백의 자리 글자 one 부터 nine 까지  long long i,part;   long long result=0;  for (i = 0; i < 9; i++) //one 부터 nine 까지 9번 반복  {   part = num[i] *100 + 997 + sum;  // 백의 자리 글자 100번과 hundred and 99번과 hundred 1번과   result += part;                       ...

프로젝트 오일러 14 양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다. n  →  n  / 2  ( n 이 짝수일 때) n  → 3  n  + 1  ( n 이 홀수일 때) 13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다. 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다. (역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다) 그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까? 참고:  계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다. ----------------------------------------------------------------------- #include #define  num 1000000 //num을 백만으로 초기화 long long calc(long long, long long); //사용자 함수 void main() { long long count = 0, n = 0, max = 0; long long i, j; for (i = 2, j = 2; i < num; j++) //i 가 num일 때까지 반복 { while (true) //짝수홀수 계산하여 i 가 1 일때까지 무한루프 또한 계산한 것을 count 함. { i = calc(i, n); count++; if (i == 1) break; else continue; } if (j == 2) //처음 count 값을 ...

프로젝트 오일러 12 1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다. 예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다. 이런 식으로 삼각수를 구해 나가면 다음과 같습니다. 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... 이 삼각수들의 약수를 구해봅시다.  1 : 1  3 : 1, 3  6 : 1, 2, 3, 6 10 : 1, 2, 5, 10 15 : 1, 3, 5, 15 21 : 1, 3, 7, 21 28 : 1, 2, 4, 7, 14, 28 위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다. 그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까? --------------------------------------------------------------- #include void main() { __int64 n = 1, i, count = 0, k; while (1) { k = (n*(n + 1)) / 2; for (i = 1; i <= k; i++) { if (k%i == 0) count++; } printf("%d\n", k); if (count == 500) break; n++; count = 0; } printf("%I64d\n", k); } -------------------------------------------------------------------- 이건 몇 분이 걸린지도 모르겠다. 다른 사람들이 푼 것들을 보니까 0.1초까지 단축이 되기도 한다. 알고리즘이라는 게 참 시간 단축에 굉장한 기여를 하는 듯하다. 오일러 프로젝트 13 아래에 50자리 숫자가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까...

Reference  http://forum.falinux.com/zbxe/index.php?document_srl=408129&mid=C_LIB http://forum.falinux.com/zbxe/?document_srl=408126&mid=C_LIB&sort_index=readed_count&order_type=desc 프로젝트 오일러 11 아래와 같은 20×20 격자가 있습니다. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10  26  38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95  63  94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17  78  78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35  14  00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 ...

프로젝트 오일러 9 세 자연수  a ,  b ,  c  가 피타고라스 정리  a 2  +  b 2  =  c 2  를 만족하면 피타고라스 수라고 부릅니다 . 예를 들면  3 2  +  4 2  = 9 + 16 = 25 =  5 2 이므로 3, 4, 5는 피타고라스 수입니다. a  +  b  +  c  = 1000  인 피타고라스 수  a ,  b ,  c 는 한 가지 뿐입니다. 이 때,  a  ×  b  ×  c   는 얼마입니까? --------------------------------------------------------------------------------------------------- #include int main() { int a,b,c,mult; //a,b,c,mult 초기화 for(c=300;c {                              900은 넘을리 없다고 생각해서 반복문을 최소화함. for(a=1;a { for(b=1;b { if(a+b+c == 1000 && c*c == a*a + b*b) //조건을 충족시키는 {                                                 ...