Hwan. 001

문제 1. 최소, 최대

#include <iostream>
#include <vector>

using namespace std;

int min(vector<int>& arr) {
    int min = arr.front();

    for (int i = 0; i < arr.size(); i++) {
        if (arr.at(i) < min) {
            min = arr.at(i);
        }
    }

    return min;
}

int max(vector<int>& arr) {
    int max = arr.front();

    for (int i = 0; i < arr.size(); i++) {
        if (arr.at(i) > max) {
            max = arr.at(i);
        }
    }

    return max;
}

int main() {
    int a, tmp;
    vector<int> arr;

    cin >> a;

    for (int i = 0; i < a; i++){
        cin >> tmp;
        arr.push_back(tmp);
    }

    cout << min(arr) << " " << max(arr);

    return 0;
}

문제 2. 최댓값

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int tmp, max;
    vector<int> arr;

    for (int i = 0; i < 9; i++){
        cin >> tmp;
        arr.push_back(tmp);
    }

    max = arr.front();

    for (int i = 0; i < arr.size(); i++) {
        if (arr.at(i) >= max) {
            max = arr.at(i);
            tmp = i+1;
        }
    }

    cout << max << endl;
    cout << tmp;

    return 0;
}

문제 3. 숫자의 개수

#include <iostream>
#include <string>

using namespace std;

int main() {
    int a, b, c;
    int arr[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 
    string str_abc;

    cin >> a >> b >> c;
    str_abc = to_string(a * b * c);

    for (int i = 0; i < str_abc.length(); i++) {
        arr[int(char(str_abc[i])) - int('0')]++;
    }

    for (int i = 0; i < 10; i++) {
        cout << arr[i] << endl;
    }

    return 0;
}

문제 4. 나머지

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    vector<int> arr;
    int a;

    for (int i = 0; i < 10; i++) {
        cin >> a;
        arr.push_back(a % 42);
    }

    sort(arr.begin(), arr.end());
    arr.erase(unique(arr.begin(), arr.end()), arr.end());

    cout << arr.size() << endl;
    return 0;
}

문제 5. 평균

#include <iostream>

using namespace std;

int main() {
    int a, max;
    double aver=0;

    cin >> a;
    int* arr = new int[a];
    double* arr2 = new double[a];

    for (int i = 0; i < a; i++) {
        cin >> arr[i];

        if (i == 0) {
            max = arr[0];
        }

        if (arr[i] > max) {
            max = arr[i];
        }
    }

    for (int i = 0; i < a; i++) {
        arr2[i] = double(arr[i]) / max * 100;
    }

    for (int i = 0; i < a; i++) {
        aver += arr2[i];
    }

    cout.precision(6);
    cout << aver / a << endl;

    return 0;
}

문제 6. OX퀴즈

#include <iostream>

using namespace std;

int point(string str) {
    bool is_flag = false;
    int cnt = 1, sum = 0;

    for (int i = 0; i <= str.size(); i++) {
        if (str[i] == 'O') {
            if(is_flag) cnt++;
            is_flag = true;
            sum += cnt;
        }
        else {
            cnt = 1;
            is_flag = false;
        }
    }

    return sum;
}

int main() {
    int a;
    cin >> a;
    int* arr = new int[a];
    string* str_arr = new string[a];

    for (int i = 0; i < a; i++) {
        cin >> str_arr[i];
    }

    for (int i = 0; i < a; i++) {
        cout << point(str_arr[i]) << endl;
    }

    return 0;
}

문제 7. 평균은 넘겠지

#include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

int main() {
    int a, b, sum, cnt, all;
    double aver;
    cin >> a;
    vector<int *> vec;
    char str_tmp[100];
    
    for (int i = 0; i < a; i++) {
        cin >> b;
        int* arr = new int[b + 1];
        arr[0] = b;

        for (int j = 1; j <= b; j++) {
            cin >> arr[j];
        }

        vec.push_back(arr);
    }

    for (int i = 0; i < vec.size(); i++) {
        all = int(vec.at(i)[0]); 
        sum = 0;
        for (int j = 1; j <= all; j++) {
            sum += vec.at(i)[j];
        }
        aver = double(sum) / all;

        cnt = 0;
        for (int j = 1; j <= all; j++) {
            if (aver < vec.at(i)[j]) {
                cnt += 1;
            }
        }
        
        sprintf(str_tmp, "%.3f", double(cnt) / all * 100);
        cout << str_tmp << "%" << endl;
    }
    
    return 0;
}

결과

문제 1. A+B - 5

#include <iostream>

using namespace std;

int main() {
    int a, b;

    while (true) {
        cin >> a >> b;

        if (a + b == 0) {
            break;
        }

        cout << a + b << endl;
    }
    
    return 0;
}

문제 2. A+B - 4

#include <iostream>

using namespace std;

int main() {
    int a, b;

    while (cin >> a >> b) {
        cout << a + b << endl;
    }
    
    return 0;
}

문제 3. 더하기 사이클

#include <iostream>

using namespace std;

void func(int a, int *front, int *back) {
    if (a < 10) {
        if(front) *front = 0;
        if(back) *back = a;
    }
    else {
        if (front) *front = a / 10;
        if (back) *back = a % 10;
    }
}

int main() {
    int a, b, cycle = 0;
    int front_a, back_a, back_b;

    cin >> a;
    b = a;

    do {
        func(b, &front_a, &back_a);
        func(front_a + back_a, NULL, &back_b);
        
        b = back_a * 10 + back_b;
        
        cycle++;
    } while (a != b);

    cout << cycle;

    return 0;
}

결과

문제 1. 구구단

#include <iostream>

using namespace std;

int main() {
    int a;

    cin >> a;

    for (int i=1; i<10; i++) {
        cout << a << " * " << i << " = " << a * i << endl;
    }

    return 0;
}

문제 2. A+B - 3

#include <iostream>

using namespace std;

int main() {
    int cnt=0, a, b;

    cin >> cnt;
    int *arr = new int[cnt];

    for (int i = 0; i < cnt; i++) {
        cin >> a >> b;
        arr[i] = a + b;
    }

    for (int i = 0; i < cnt; i++) {
        cout << arr[i] << endl;
    }

    return 0;
}

문제 3. 합

#include <iostream>

using namespace std;

int main() {
    int a, sum=0;

    cin >> a;

    for (int i = 1; i <= a; i++) {
        sum += i;
    }

    cout << sum;

    return 0;
}

문제 4. 빠른 A+B

#include <iostream>

using namespace std;

int main() {
    int cnt = 0, a, b;

    cin.tie(NULL);
    cin.sync_with_stdio(false);

    cin >> cnt;
    int* arr = new int[cnt];

    for (int i = 0; i < cnt; i++) {
        cin >> a >> b;
        arr[i] = a + b;
    }

    for (int i = 0; i < cnt; i++) {
        cout << arr[i] << "\n";
    }

    return 0;
}

문제 5. N 찍기

#include <iostream>

using namespace std;

int main() {
    int cnt = 0;

    cin.tie(NULL);
    cin.sync_with_stdio(false);

    cin >> cnt;

    for (int i = 1; i <= cnt; i++) {
        cout << i << "\n";
    }

    return 0;
}

문제 6. 기찍 N

#include <iostream>

using namespace std;

int main() {
    int cnt = 0;

    cin.tie(NULL);
    cin.sync_with_stdio(false);

    cin >> cnt;

    for (int i = cnt; i > 0; i--) {
        cout << i << "\n";
    }

    return 0;
}

문제 7. A+B - 7

#include <iostream>

using namespace std;

int main() {
    int cnt = 0, a, b;

    cin >> cnt;
    int* arr = new int[cnt];

    for (int i = 0; i < cnt; i++) {
        cin >> a >> b;
        arr[i] = a + b;
    }

    for (int i = 0; i < cnt; i++) {
        cout << "Case #" << i+1 << ": "<< arr[i] << endl;
    }

    return 0;
}

문제 8. A+B - 8

#include <iostream>

using namespace std;

int main() {
    int cnt = 0;

    cin >> cnt;
    int* arr = new int[cnt];
    int* a = new int[cnt];
    int* b = new int[cnt];

    for (int i = 0; i < cnt; i++) {
        cin >> a[i] >> b[i];
        arr[i] = a[i] + b[i];
    }

    for (int i = 0; i < cnt; i++) {
        cout << "Case #" << i+1 << ": " << a[i] << " + " << b[i] << " = " << arr[i] << endl;
    }

    return 0;
}

문제 9. 별 찍기 - 1

#include <iostream>

using namespace std;

int main() {
    int cnt = 0;

    cin >> cnt;

    for (int i = 0; i < cnt; i++) {
        for (int j = 0; j <= i; j++) {
            cout << "*";
        }
        cout << "\n";
    }

    return 0;
}

문제 10. 별 찍기 - 2

#include <iostream>

using namespace std;

int main() {
    int cnt = 0;

    cin >> cnt;

    for (int i = 1; i <= cnt; i++) {
        for (int j = cnt; j >= 1; j--) {
            if (i < j) {
                cout << " ";
            }
            else {
                cout << "*";
            }
        }
        cout << "\n";
    }

    return 0;
}

문제 11. X보다 작은 수

#include <iostream>

using namespace std;

int main() {
    int n, x;
    cin >> n >> x;

    int* arr = new int[n];

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = 0; i < n; i++) {
        if (arr[i] < x) {
            cout << arr[i];
            if (i != n - 1) {
                cout << " ";
            }
        }
    }


    return 0;
}

결과

문제 1. 두 수 비교하기

#include <iostream>

using namespace std;

int main() {
    int a, b;

    cin >> a;
    cin >> b;

    if (a > b) {
        cout << ">";
    }
    else if (a < b) {
        cout << "<";
    }
    else {
        cout << "==";
    }

    return 0;
}

문제 2. 시험 성적

#include <iostream>

using namespace std;

int main() {
    int a;
    string b = "F";

    cin >> a;

    if (a >= 60) {
        b = "D";
    }
    if (a >= 70) {
        b = "C";
    }
    if (a >= 80) {
        b = "B";
    }
    if (a >= 90) {
        b = "A";
    }

    cout << b;

    return 0;
}

문제 3. 윤년

#include <iostream>

using namespace std;

int main() {
    int a, answer = 0;
    cin >> a;

    if(a % 4 == 0 && a % 100 != 0) {
        answer = 1;
    }
    if (a % 400 == 0) {
        answer = 1;
    }

    cout << answer;

    return 0;
}

문제 4. 사분면 고르기

#include <iostream>

using namespace std;

int main() {
    int x, y, answer = 0;
    cin >> x;
    cin >> y;

    if (x > 0 && y > 0) {
        answer = 1;
    }
    if (x < 0 && y > 0) {
        answer = 2;
    }
    if (x < 0 && y < 0) {
        answer = 3;
    }
    if (x > 0 && y < 0) {
        answer = 4;
    }

    cout << answer;

    return 0;
}

문제 5. 알람 시계

#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
    int h, m;
    char answer[30] = "";

    cin >> h;
    cin >> m;

    m -= 45;

    if (m >= 60) {
        m -= 60;
        h += 1;
    }
    if (m < 0) {
        m = 60 + m;
        h -= 1;
    }

    if (h >= 24) {
        h -= 24;
    }
    if (h < 0) {
        h = 24 + h;
    }

    snprintf(answer, 30, "%d %d", h, m);
    cout << answer;

    return 0;
}

추가 문제 6. 오븐 시계 (브론즈 4, 2022-02-16 확인)

#include<iostream>

using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;

	b = b + c;
	if (b < 0) {
		b = 0;
	}
	while (b >= 60) {
		b -= 60;
		a += 1;
	}

	if (a < 0) {
		a = 0;
	}
	while (a >= 24) {
		a -= 24;
	}

	cout << a << " " << b << "\n";
    
    return 0;
}

추가 문제 7. 주사위 세개(브론즈 4, 2022-02-16)

#include<iostream>
#include<map>

using namespace std;

int main() {
	map<int, int> m;
	int a, res=0, k_max = 0, v_max = 0;

	for (int i = 0; i < 3; i++) {
		cin >> a;
		m[a]++;
		if (k_max < a) k_max = a;
		if (v_max < m[a]) v_max = m[a];
	}

	for (auto v : m) {
		if (v_max != 1 && v_max == v.second) {
			k_max = v.first;
		}
	}

	if (v_max == 3) {
		res = 10000 + k_max * 1000;
	}
	if (v_max == 2) {
		res = 1000 + k_max * 100;
	}
	if (v_max == 1) {
		res = k_max * 100;
	}

	cout << res << "\n";
    
    return 0;
}

결과

문제 1. Hello World

#include <iostream>

int main(){
    std::cout << "Hello World!";
    
    return 0;
}

문제 2. We love krill

#include <iostream>

int main(){
    std::cout << "강한친구 대한육군";
    std::cout << "강한친구 대한육군";
    
    return 0;
}

문제 3. 고양이

#include <iostream>

using namespace std;

int main() {
    cout << "\\    /\\\n";
    cout << " )  ( ')\n";
    cout << "(  /  )\n";
    cout << " \\(__)|\n";
    
    return 0;
}

문제 4. 개

#include <iostream>
using namespace std;

int main(){
    cout << "|\\_/|\n";
    cout << "|q p|   /}\n";
    cout << "( 0 )\"\"\"\\\n";
    cout << "|\"^\"`    |\n";
    cout << "||_/=\\\\__|\n";
    
    return 0;
}

문제 5. A+B

int main(){
    int a, b;
    
    scanf("%d %d", &a, &b);
    printf("%d", a+b);
    
    return 0;
}

문제 6. A-B

int main(){
    int a, b;
    
    scanf("%d %d", &a, &b);
    printf("%d", a-b);
    
    return 0;
}

문제 7. A*B

#include <iostream>

int main(){
    int A, B;
    
    std::cin >> A >> B;
    std::cout << A * B;
    
    return 0;
}

문제 8. A/B

#include <iostream>

using namespace std;

int main() {
    double a, b;
    cin >> a >> b;
    
    printf("%.10f", a / b);

    return 0;
}

문제 9. 사칙연산

#include <iostream>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    
    cout << a + b << endl;
    cout << a - b << endl;
    cout << a * b << endl;
    cout << a / b << endl;
    cout << a % b << endl;

    return 0;
}

문제 10. 나머지

#include <iostream>

using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    
    cout << (a + b) % c << endl;
    cout << ((a%c) + (b%c))%c << endl;
    cout << (a * b)%c << endl;
    cout << ((a % c) * (b % c)) % c << endl;

    return 0;
}

문제 11. 곱셈

#include <iostream>

using namespace std;

int main() {
    int a, b, c;
    int b1, b2, b3;

    cin >> a;
    cin >> b;

    c = a * b;
    b3 = a * (b / 100);
    b %= 100;
    b2 = a * (b / 10);
    b %= 10;
    b1 = a * b; 

    cout << b1 << endl;
    cout << b2 << endl;
    cout << b3 << endl;
    cout << c << endl;

    return 0;
}

결과

1. 달팽이 배열

 - 외곽부터 정사각형을 채우고 대각선 아래로 이동하여 반복

2. 방법별 코드 정리

 2-1) 코드 

  - 외부부터 한바퀴씩 작성

  - 시계방향으로 회전하는 달팽이 배열을 이동 좌표를 미리 계산하는 방식으로 작성

# 범위내 좌표이동
def add_direction(x, y, arr_direction, int_direction, int_k):
    a, b = 0, 0
    
    # x 좌표 이동
    next_x = x + arr_direction[int_direction][0]
    if next_x >= 0 and next_x < int_k:
        a = next_x
    # y 좌표 이동
    next_y = y + arr_direction[int_direction][1]
    if next_y >= 0 and next_y < int_k:
        b = next_y
    
    return a, b

def snailArray_Generator(k):
    # k가 0보다 작거나 같으면 종료
    if k <= 0:
        return []

    # 이동할 좌표 구하기
    arr_Move = []
    # right, down, left, up
    arr_direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    # 최초 시작 좌표
    x, y = 0, 0

    # 루프 한번에 한 바퀴
    for n in range(k-1, 0, -2):
        # 각 방향으로
        for int_direction in range(4):
            # n개 씩 채우기
            for _ in range(n):
                arr_Move.append((x, y))
                # 좌표 이동
                x, y = add_direction(x, y, arr_direction, int_direction, k)
        
        # 다음 시작 좌표로 이동
        x, y = x+1, y+1

    # 마지막 이동한 위치가 array에 이미 있으면 추가 안함
    if not (x, y) in arr_Move:
        arr_Move.append((x, y))

    # 값 넣기
    arr_map = [[0 for _ in range(k)] for _ in range(k)]
    value = 0
    for move in arr_Move:
        value += 1
        arr_map[move[1]][move[0]] = value

    return arr_map


# map 출력
for map in snailArray_Generator(0):
    print(map)

 2-1) 결과

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/43163

2. 코드

def dfs(begin, target, words, visited):
    str_end = target
    str_start = begin
    int_depth = 0
    arr_stack = [str_start]
    
    while arr_stack:
        str_top = arr_stack.pop()
        print(str_top)
        
        if str_top == target:
            return int_depth
        
        for i in range(len(words)):
            if visited[i] or words[i] == str_top:
                continue
        
            for _ in range(len(words[i])):
                count_tmp = 0
                for j in range(len(words[i])):
                    if [ch for ch in words[i]][j] == [ch for ch in str_top][j]:
                        count_tmp+=1 
                
                if (len(words[i])-1) == count_tmp:
                    visited[i] = True
                    
                    if words[i] != str_end:
                        arr_stack.append(words[i])
                    else:
                        return int_depth+1
                    break
                    
        int_depth += 1
            
            
def solution(begin, target, words):
    if target not in words:
        return 0
    
    visited = [False] * (len(words))
    print(words)
    return dfs(begin, target, words, visited)

3. 결과

1. 문제
https://programmers.co.kr/learn/courses/30/lessons/42748

2. 코드

def solution(array, commands):
    answer = []
    
    for cmd in commands:
        answer.append((lambda i, j : sorted(array[i-1:j]))(cmd[0], cmd[1])[cmd[2]-1])
    
    return answer

3. 결과

1. 가설 적용 코드 (C++)

typedef unsigned long long ll;

/*
*  input : ll input (정수)
*  output : int (1 or 0)
*  unsigned long long 형태의 정수를 넣으면 해당 수가 소수인지 여부를 알려준다.
*  소수 판별 custom 버전
*/
int is_prime_number_custom(ll input)
{
    if (input < 2) {
        return 0;
    }

    for (ll j = 2; j <= (ll)(input / j); j++)
    {
        if (input % j == 0)
        {
            return 0;
        }
    }

    return 1;
}

2. 가설 적용 코드 (Python)

def func1(input):
    if input < 2:
    	return 0
    for j in range(2, int(input/j)+1):
        if input % j == 0:
            return 0
    return 1

3. 에라토스테네스의 체 (c++)

/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(int m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (int i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (int j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

4. 최소 공배수, 최대 공약수

int func_2609_gcd(int a, int b) {
    if (a % b == 0) {
        return b;
    }
    else {
        return func_2609_gcd(b, a % b);
    }
}

int func_2609_lcm(int a, int b) {
    return (a * b) / func_2609_gcd(a, b);
}

코드 1 - i(2 ~ N)를 j(2 ~ i)로 나누기

 N을 입력받고 i를 2~N까지 1씩 더한다.

j가 2부터 i에 도달할때까지 1씩 더하면서 i와 나누어 떨어지면 (1과 자기 자신을 제외한 인수가 있으므로) 소수가 아님.

위 연산을 반복해서 0~N 까지 소수의 개수를 하나하나 판단하여 카운팅한다.

각 범위를 계산하며 시간을 측정해본 결과는 아래 표와 같다.

#include<stdio.h>
#include<math.h>

int main() {
    int i, j, cnt=0, flag=1;
    unsigned int min, max;

	// 범위 입력
    printf("min : ");
    scanf_s("%d", &min);
    printf("max : ");
    scanf_s("%d", &max);

	// 2보다 작은 최소 범위가 입력되면 2로 고정
    if (min < 2) min = 2;
	
    printf("입력 받은 범위 내의 소수");
    // i가 입력받은 최소 범위부터 최대 범위까지 반복
    for (i = min; i < max; i++) 
    {
        flag = 1; // 현재수가 소수라고 가정하고 시작
        
    	// j는 2부터 현재의 i 전까지 증가
        for (j = 2; j < i; j++) 
        {
        	// i와 j를 나눈 나머지가 존재하면 소수가 아님
            if (i % j == 0) 
            {
                flag = 0; // flag가 0이면 현재 수(i)는 소수가 아님
                break; // 더 이상 j로 나누어 줄 필요가 없으므로 탈출
            }
        }
		
        // 위에서 판단된 결과가 소수이면(0이 아니면)
        if (flag) 
        {
            cnt++; // 개수를 증가시킴 (입력 받은 범위 내의 소수 개수)
            printf("%d\t", i); // 출력
            
            if (cnt % 5 == 0) 
            {
            	printf("\n"); // 5개 단위로 끊음
            }
        }
    }

    printf("\n%d ~ %d 사이의 소수 개수 : %d개\n", min, max, cnt);

    return 0;
}

코드 2 - i (2 ~ N)를 j (2 ~ i / j)로 나누기

#include<stdio.h>
#include<math.h>
#include<time.h>

void test(int min, int max) 
{
    clock_t start, end;
    float res;
    int i, j, cnt = 0, flag;

    start = clock();
    for (i = min; i < max; i++)
    {
        flag = 1;
		
        // 기존과 달라진 부분, j로 확인 하는 범위를 i와 현재 j의 나눈 몫까지로 줄였음
        for (j = 2; j <= (int)(i / j); j++)
        {
            if (i%j == 0)
            {
                flag = 0;
                break;
            }
        }

        if (flag)
        {
            cnt++;
        }
    }
    end = clock();

    res = (float)(end - start) / CLOCKS_PER_SEC;

    printf("%d~%d : %d개\t%.3fms\n", min, max, cnt, res);
}

int main() {
    int arr[] = {100, 1000, 10000, 100000, 1000000, 10000000, 1000000000};

    for (int i = 0; i < (int)(sizeof(arr) / sizeof(int)); i++)
    {
        test(2, arr[i]);
    }
    return 0;
}

#include <iostream>

using namespace std;

typedef unsigned long long ll;

/*
* input : int m
* output : 1부터 m까지의 소수 여부를 sizeof(bool) * (m+1)크기의 bool * 형태로 반환한다.
* 사용 시 반환된 bool array에 해당 자연수를 조회하면 소수 여부를 알 수 있다.
*/
bool *Sieve_of_Eratosthenes(ll m) {
    bool* arr = new bool[m + 1];

    memset(arr, 1, sizeof(bool) * (m+1));
    arr[0] = false;
    arr[0] = false;

    for (ll i = 2; i < m + 1; i++) {
        if (arr[i] == true) {
            for (ll j = i * 2; j < m + 1; j += i) {
                arr[j] = false;
            }
        }
    }

    return arr;
}

int main() {
    clock_t start, end;
    ll N, M;
    ll sum=0;

    start = clock();
    cin >> N >> M;
    bool* arr = Sieve_of_Eratosthenes(M);

    for (ll i = N; i <= M; i++) {
        if (arr[i]) {
            sum++;
        }
    }

    end = clock();
    float res = (float)(end - start) / CLOCKS_PER_SEC;
    cout << "" << N << " " << M << " " << sum << ", " << res << "ms" << endl;
    
    return 0;
}

#include "stdafx.h"
#include <ctype.h>
#include <math.h>

int gcd(int a, int b);
int RSA(int n, int m, int d); 

int main(){
    // 키 생성
    //int p = 13, q = 37;
    //int p = 11, q = 13;
    int p = 17, q = 13;

    int n, e, d, f;

    n = p * q;
    f = (p-1) * (q-1);

    // e 결정
    for (int i = 2; i < f; i++) {
        // 서로소 판단
        if (gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1) {
            e = i;
            break;
        } 
    }

    //d 결정
    for (int i = 1; i < n; i++) {
        if ((1 + f * i) % e == 0) {
            d = (1 + f * i) / e; 
            break;
        }
    }

    // 소수에 따라 자동 계산된 변수 값
    printf("p\tq\tn\te\td\tf\n");
    printf("%d\t%d\t%d\t%d\t%d\t%d\n\n", p, q, n, e, d, f);

    // 암호화
    int msg = 'b';
    printf("msg : %c\n", msg);

    int c = RSA(n, msg, e);
    printf("c : %c\n", c);

    // 복호화
    int msg2 = RSA(n, c, d);
    printf("msg : %c\n", msg2);

    return 0;
}

// 암복호화를 위한 모듈로 연산을 수행 (n, d는 공개키/ 개인키, m은 메시지)
int RSA(int n, int m, int d) {
    int bin1[10] = { 0, };
    int tmp, j = 1;
    unsigned long long x_tmp = 1; 
    int x[10]; // m^2^0~9 mod n

    // 거듭 제곱법 구현을 위한 값 미리 저장
    x[0] = (unsigned long long)pow(m, 1) % n;
    for (int i = 1; i < 10; i++) {
        x[i] = (x[i - 1] * x[i - 1]) % n;
    }

    // 지수를 이진수로 변환 (구현 편의성을 위해 그냥 역으로 넣음) 
    for (int i = 0; d > 0; i++) {
        tmp = d % 2;
        d /= 2;
        bin1[i] = tmp;
    }

    // 이진수가 1일 떄만 미리 계산된 값 곱셈
    for (int i = 0; i < 10; i++) {
        if (bin1[i] == 1) {
            x_tmp *= x[i];
        }
    }

    return x_tmp % n; // 곱셈 합을 모듈로해서 반환
}

// 최대 공약수
int gcd(int a, int b) {
    int tmp, n;

    if (a<b) {
        tmp = a;
        a = b;
        b = tmp;
    }

    while (b != 0) {
        n = a % b;
        a = b;
        b = n;
    }

    return a;
}

4. 참고 사항

 - 메르센 소수 같은 빅넘버를 처리하기엔 부적합함 (이 경우  OpenSSL 활용)

 - 거듭 제곱법 구현 함수 내 배열을 10으로 고정해두었으나 배열 크기 조정으로 어느정도 큰 소수

   (x_tmp 최대값, unsigned long long) 까지는 연산이 가능함.

- 문자를 하나씩 암호화 하면 같은 문자는 같은 값으로? 암호화됨. (블록 단위 암호화 필요)

  ex) testtest -> abcaabca 

- 자료형 크기 고려했을 때 문자를 대충 4바이트 단위까지 합쳐서 연산가능할 듯

  ex) asdf  -> 16진수변환 한번에 연산 등등

내용 수정

2024-01-21(일)

- 기존 코드에서 잘못된 부분을 확인하여 수정이 필요한 부분을 적어두었음

- e를 결정하는 부분에서 e와 f가 서로소인 부분이 확인 되어야 하기 때문에 기존 코드의 gcd(p - 1, i) == 1 && gcd(q - 1, i) == 1 부분이 제거 되고 아래처럼 수정되어야 함

f = (p-1) * (q-1);

// e 결정
for (int i = 2; i < f; i++) {
    if (gcd(i, f) == 1) {
        e = i;
        break;
    }
}