t1mmyt1m

알고리즘 수업 - 알고리즘의 수행 시간 1 - 24262

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

위 코드 1을 보면 수행횟수는 1임. n의 입력값과 상관없이 항상 1이기 때문에 최고차항의 차수는 항상 0.

print(1)
print(0)

알고리즘 수업 - 알고리즘의 수행 시간 2 - 24263

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

n의 입력값만큼 코드 1이 수행됨

import sys

n = int(sys.stdin.readline().rstrip())
print(n)
print(1)

알고리즘 수업 - 알고리즘의 수행 시간 3 - 24264

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

2중 for문이기 때문에 코드 1은 $n^2$만큼 수행됨

import sys

n = int(sys.stdin.readline().rstrip())
print(n**2)
print(2)

알고리즘 수업 - 알고리즘의 수행 시간 4 - 24265

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

코드를 보면 다음과 같이 수행됨

i=1, j=2,3,4,5,6,7
i=2, j=3,4,5,6,7
i=3, j=4,5,6,7
i=4, j=5,6,7
i=5, j=6,7
i=6, j=7

전 문제와 동일하게 2중 for문이기 때문에 최고차항의 차수도 2임

import sys

n = int(sys.stdin.readline().rstrip())

print(n*(n-1)//2)
# 처음에 print((n-1)*(n-1)//3)으로 했다가 틀렸음
print(2)

알고리즘 수업 - 알고리즘의 수행 시간 5 - 24266

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

3중 for문, 코드 1은 $n^3$만큼 수행됨

import sys

n = int(sys.stdin.readline().rstrip())
print(n**3)
print(3)

알고리즘 수업 - 알고리즘의 수행 시간 6 - 24267

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

24265 문제와 비슷한 형식임

import sys

n = int(sys.stdin.readline().rstrip())

print(n*(n-1)*(n-2)//6)
# 처음에 print(n*(n-2)*(n-4)//3)으로 제출했다가 틀림
print(3)

알고리즘 수업 - 점근적 표기 1 - 24313

처음 코드를 제출할 때 if문에 다음과 같이 입력했더니 틀려서 다시 한번 생각해봄

(a1*n0)+a2 <= n0*c

문제에 나와있는 빅오의 정의는 다음과 같음

O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다}

입력 범위는 다음과 같다

첫째 줄에 함수 f(n)을 나타내는 정수 a1, a0가 주어진다. (0 ≤ |ai| ≤ 100)

다음 줄에 양의 정수 c가 주어진다. (1 ≤ c ≤ 100)

다음 줄에 양의 정수 n0가 주어진다. (1 ≤ n0 ≤ 100)

$a_i$는 음수도 입력이 가능함

a0, a1이 각각 양수, 음수일 때로 구분하고 c보다 작을 때, 같을 때, 클 때 3가지 경우로 나눠서 다음과 같이 생각해봄

a0이 음수
7*10-7 < 10*8
8*10-7 < 10*8
9*10-7 > 10*8

7*10-7 < 10*8
7*10-8 < 10*8
7*10-9 < 10*8

a1이 음수
-7*10+7 < 10*8
-8*10+7 < 10*8
-9*10+7 < 10*8

-7*10+7 < 10*8
-7*10+8 < 10*8
-7*10+9 < 10*8

둘 다 양수
7*10+7 < 10*8
8*10+7 > 10*8
9*10+7 > 10*8

7*10+7 < 10*8
7*10+8 > 10*8
7*10+9 > 10*8

둘 다 음수
-7*10-7 < 10*8
-8*10-7 < 10*8
-9*10-7 < 10*8

-7*10-7 < 10*8
-7*10-8 < 10*8
-7*10-9 < 10*8

위 예시처럼 a1이 c보다 크면 조건이 성립하지 않는다는걸 알 수 있음

import sys

a1, a2 = map(int, sys.stdin.readline().rstrip().split())
c = int(sys.stdin.readline().rstrip())
n0 = int(sys.stdin.readline().rstrip())

if (a1*n0)+a2 <= n0*c and a1<=c:
    print(1)
else:
    print(0)

예에전에 푼 문제 정리

배수와 약수 - 5086

while True:
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break
    elif b%a == 0:
        print("factor")
    elif a%b == 0:
        print("multiple")
    elif a%b != 0 or b%a != 0:
        print("neither")

약수 구하기 - 2501

N의 약수를 구하고 리스트를 만들어서 오름차순으로 정렬 후 K번째 수를 출력하면됨. 약수가 없으면 0출력

import sys

n, k = map(int, sys.stdin.readline().rstrip().split())
li = []

for i in range(1, int(n**(1/2))+1):
    if n%i == 0:
        li.append(i)
        if i**2!=n:
            li.append(n//i)
    
li.sort()

if len(li) < k:
    print(0)
else:
    print(li[k-1])

제곱근까지만 계산을 해서 시간복잡도를 줄임

시간 복잡도 : O(N^(1/2))

약수들의 합 - 9506

for문 안에 리스트 l을 넣어서 초기화시켜줘야함

a = []

while True:
    n = int(input())
    if n == -1:
        break
    a.append(n)


for n in a:
    l = []
    for i in range(1, n):
        if n%i == 0:
            l.append(i) 

    if sum(l) == n:
        print(n , "=" , " + ".join(str(i) for i in l))
    else:
        print(n , "is NOT perfect.")

소수 찾기 - 1978

n = int(input())
sec_n = list(map(int, input().split()))

count = 0
for n in sec_n:
    if n != 1:
        for i in range(2, n):
            if n % i == 0:
                break
        else:
            count+=1

print(count)

소수 - 2581

m = int(input())
n = int(input())
prime = [ ]

for i in range(m, n+1): #m부터 n까지
    if i > 1: #1보다 큰 수
        for j in range(2, i):
            if (i % j) == 0:
                break
        else:
            prime.append(i)

if len(prime) > 0:
    print(sum(prime))
    print(min(prime))
else:
    print(-1)

소인수분해 - 11653

import math

n = int(input())
i = 2

while i <= math.sqrt(n):
    if n % i != 0:
        i += 1
    else:
        print(i)
        n //= i

if n > 1:
    print(n)

첫번째로 입력받은 문자열과 다음 문자열을 비교해가며 다르면 ?로 바꾸는 식으로 코드 작성

import sys

N = int(sys.stdin.readline())
input = [list(sys.stdin.readline().rstrip()) for _ in range(N)]

for i in range(len(input[0])):
    for j in range(len(input)):
        if input[0][i] != input[j][i]:
            input[0][i] = '?'
            break
print(''.join(input[0]))

python3로 푼 문제입니다

진법 변환 - 2745

$ABC_{36} = A36^2+B36+C*36^0$

원래 ord를 사용하면 알파벳의 경우 A부터 1씩 더해짐,

원래 순서 = 알파벳 - ord(A)

10진법 넘어가는 진법에서 값 = 알파벳 - ord(A) + 10

→ A가 10이기 때문에 10을 더해줌

이때 중요한건 알파벳 말고도 숫자가 쓰일수도 있기때문에 숫자인지 알파벳인지 구분을 해줘야함

python에서는 다음과 같다고 함

isalpha : 알파벳인지 확인
isdigit : 숫자인지 확인
isalnum : 알파벳 or 숫자인지 확인

num, formation = input().split()
ans = 0

for i in range(len(num)):
    if num[i].isalpha():
        ans += (ord(num[i]) - ord('A') + 10)*pow(int(formation), len(num)-i-1)
    else:
        ans += int(num[i])*pow(int(formation), len(num)-i-1)

print(ans)

진법 변환2 - 11005

a = 60466175
b = 36

while True:
    if a == 0:
        break
    else:
        print(a, a % b)
        a = a // b

나머지값을 구한 후 차례대로 해당 진법으로 바꾸면 됨

이때 첫번째 나머지를 구하고 N//B를 한 값으로 다음 나머지를 구하면됨

10이 넘으면 알파벳 대문자로 표현하고 아니면 숫자 그대로 출력되게하며 while문의 순서 그대로하면 순서가 반대로 되어서 나오기 때문에 거꾸로 출력되게 해줌

num, formation = input().split()
num, formation = int(num), int(formation)
ans = ''

while True:
    if num == 0:
        break
    else:
        c = num % formation
        if c >= 10:
            ans += chr(c + 55)
        else:
            ans += str(c)
        num = num // formation

print(ans[::-1]

세탁소 사장 동혁 - 2720

주어진 테스트케이스만큼 for문을 돌려서 가장 큰 단위부터 차례로 나머지연산을 해주면 동전의 개수를 최소로 할 수 있음

case = int(input())
for _ in range(case):
    money = int(input())
    coin = [25, 10, 5, 1]
    for i in coin:
        print(money // i, end=' ')
        money %= i

중앙 이동 알고리즘 - 2903

점의 개수와 그림을 보면 한줄에 있는 점의 개수와 가로줄의 수가 같아 총 점의 개수를 n*n로 나타낼 수 있음

예시를 보면

$2^2=4 \\ 3^3 = 9 \\ 5^5=25$ 이와 같은데 3번 케이스를 살펴보면 다음과 같을 것

$9^9=81$

이런식으로 2→3→5→9 바뀜

점의 개수는 기존 점의 사이에 추가되기 때문에 $n+(n-1)=2n-1$ 이와같이 표현 가능

import sys

m = int(sys.stdin.readline().rstrip())
n = 2

for i in range(m):
    n = 2*n - 1

print(n**2)

벌집 - 2292

그림을 보고 정리해보면 아래와 같음

a = [2,3,4,5,6,7]
b = [8,9,10,11,12,13,14,15,16,17,18,19]
c = [20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37]
d = [38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61]
e = [62,63,64,65,66,67,68,69,70,...]

정육각형 모양으로 각 겹마다 나누면 다음과 같은데 이때 크기가 늘어날수록 숫자의 개수가 6개씩 더해짐

$c=2+6n \\ d=6n$ 이때 i는 리스트의 첫번째 수, d는 리스트 안의 숫자 개수

위를 이용해서 코드 짬

이때 2,8,20,38 등 2+6n이 되는 수가 리스트의 첫번째 요소이므로 입력받은 수가 2+6n 이상일 때 횟수를 1씩 더해줘야 올바르게 나옴

import sys

n = int(sys.stdin.readline().rstrip())
a = 2
i = 0

while n>=a:
    i += 1
    a += 6*i
    print(a)

print(i+1)

분수찾기 - 1193

지그재그 순서로 순서를 부여하기 때문에 대각선으로 따졌을 때 해당 줄이 짝수인지 홀수인지만 따지면 됨

왜나면 배열이 1부터 해당 줄의 숫자개수만큼 늘어나고 거꾸로 줄어드는 형태이기 때문. 그리고 지그재로 움직이기 때문에 대각선 줄이 짝수일 때와 홀수일 때 두가지로 구분해야함. 이때 각 줄의 숫자 개수는 대각선 몇번째 줄인지와 동일

(다음줄은 ->로 구분, 같은줄에서 다음순서를 나타낼 때는 -로함)
분수: 1/1 -> 1/2 - 2/1 -> 3/1 - 2/2 - 1/3 -> …
분자: 1-> 1 - 2 -> 3 - 2 - 1 ->...
분모: 1-> 2 - 1 -> 1 - 2 - 3 ->...

그럼 주어진 수 X를 가지고 몇번째 줄인지를 알면됨

import sys

x = int(sys.stdin.readline().rstrip())
line, cmp = 0, 0

while x>cmp:
    line += 1
    cmp += line

if line%2==0:
    nume = line-(cmp-x)
    deno = cmp-x+1
else:
    nume = cmp-x+1
    deno = line-(cmp-x)
    
print(nume ,'/', deno, sep="")

달팽이는 올라가고 싶다 - 2869

문제에서 범위가 다음과 같다고 나옴

1 ≤ B < A ≤ V ≤ 1,000,000,000

1. A와 V가 같을 때
2. A가 V보다 작을 때

위 두 케이스로 나눠서 코드를 다시 짬

import sys
import math

a, b, v = map(int, sys.stdin.readline().rstrip().split())

if a == v and a//b==0:
    print(math.ceil((v-b)/(a-b)+1))
else:
    print(math.ceil((v-b)/(a-b)))

math.ceil(number)은 숫자 number를 소수점 1자리에서 올림한다고 함

풀이

정사각형의 한변의 길이를 10으로 지정하고 주어진 (왼쪽지점+10)과 (아래지점+10)으로 색종이가 붙여진 영역을 구함

count = int(input())
square = [[0] * 100 for _ in range(100)]
for _ in range(count):
    left, down = map(int, input().split())

    for i in range(left, left + 10):
        for j in range(down, down + 10):
            square [i][j] = 1


print(sum(sum(square, [])))

sum

sum에서 두번째 인자값은 시작지점을 의미함

이때 2차원 리스트인 square를 1차원 리스트로 만들어주기 위해 []를 넣어줌

-> 2차원 리스트의 모든 원소들이 1차원 리스트로 들어가게됨

sum(square, []) : 1차원 리스트로 만들어줌

sum(sum(square, [])) : 1차원 리스트의 모든 원소들의 합을 구함

9/5

1000

#include <stdio.h>

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

2557

#include <stdio.h>

int main() {
    printf("Hello World!\n");
}

1001

#include <stdio.h>

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

1008

#include <stdio.h>

int main() {
    double a;
    double b;
    scanf("%lf %lf", &a, &b);
    printf("%.9f\n", a/b);
    // printf("%.9f\n", a/b);도 맞음

    return 0;
}

2739

#include <stdio.h>

int main() {
    int j, num;
    scanf("%d", &num);
    for(j=1; j<10; j++) {
      printf("%d * %d = %d\n", num, j, num*j);
    }

    return 0;
}

10869

#include <stdio.h>

int main() {
    int i,j;
    scanf("%d %d", &i,&j);
    printf("%d\n", i+j);
    printf("%d\n", i-j);
    printf("%d\n", i*j);
    printf("%d\n", i/j);
    printf("%d\n", i%j);

    return 0;
}

2741

#include <stdio.h>

int main() {
    int i;
    scanf("%d", &i);
    for(int n=1; n<=i; n++){
        printf("%d\n", n);
    }

    return 0;
}

10998

#include <stdio.h>

int main() {
    int i, j;
    scanf("%d %d", &i,&j);
    printf("%d\n", i*j);

    return 0;
}

10430

#include <stdio.h>

int main() {
    int a,b,c;
    scanf("%d %d %d", &a,&b,&c);
    printf("%d\n", (a+b)%c);
    printf("%d\n", ((a%c)+(b%c))%c);
    printf("%d\n", (a*b)%c);
    printf("%d\n", ((a%c)*(b%c))%c);

    return 0;
}

2438

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            printf("*");
        }
        printf("\n");
    }

    return 0;
}

2742

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    for(int i=n; i>=1; i--){
        printf("%d\n", i);
    }

    return 0;
}

9/7

10817

버블 솔트 알고리즘 사용

https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html

#include <stdio.h>

int main() {
    int a,b,c,temp;
    scanf("%d %d %d", &a,&b,&c);
    int arr[3] = {a, b, c};
    
    for(int i=0; i<3-1; i++){
        for(int j=0; j<3-1-i; j++){
            if(arr[j]>arr[j+1]){
                temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    printf("%d\n", arr[1]);
    
}

1929

#include <stdio.h>
# include <stdbool.h>

int main() {
    int m, n;
    scanf("%d %d", &m, &n);

    if (m < 2) {
        m = 2; // 2 이하는 소수가 아니므로 2부터 시작
    }

    for (int i = m; i <= n; i++) {
        bool isPrime = true;

        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            printf("%d\n", i);
        }
    }

    return 0;
}

1237

#include <stdio.h>

int main() {
    printf("문제의 정답");
}

8393

#include <stdio.h>

int main() {
    int n,i;
    int sum=0;
    scanf("%d", &n);

    for(i=1; i<=n; i++){
        sum += i;
    }
    printf("%d\n", sum);
}

11942

#include <stdio.h>

int main() {
    printf("고려대학교");
}

9498

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    if(90<=n && n<=100) printf("A\n");
    if(80<=n && n<=89) printf("B\n");
    if(70<=n && n<=79) printf("C\n");
    if(60<=n && n<=69) printf("D\n");
    if(60>n) printf("F\n");
}

10871

#include <stdio.h>

int main() {
    int n,x;
    scanf("%d %d", &n, &x);

    int arr[n];
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
    }

    for(int j=0; j<n; j++){
        if(arr[j]<x) printf("%d ", arr[j]);
    }

    return 0;

}

10818

속도가 좀 느림

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    int arr[n];
    for(int i=0; i<n; i++){
        scanf("%d", &arr[i]);
    }
    int max=arr[0];
    int min=arr[0];
    for(int j=1; j<n; j++){
        if(max<arr[j]) max=arr[j];
        if(min>arr[j]) min=arr[j];
    }
    printf("%d %d\n", min, max);

    return 0;
}

9/9

2752

#include <stdio.h>

int main() {
    int arr[3];

    for(int i=0; i<3; i++){
        scanf("%d", &arr[i]);
    }
    for(int i=0; i<3; i++){
        for(int j=0; j<3; j++){
            if(arr[j]>arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    for(int j=0; j<3; j++){
        printf("%d ", arr[j]);
    }

    return 0;
}

2490

0 또는 1을 입력하기 때문에 1의 합을 통해 구분함

A (도: 3
B (개: 2
C (걸: 1
D (윷: 0
E (모: 4

#include <stdio.h>

int main() {
    int a;
    for(int i=0; i<3; i++){
        int sum=0;
        for(int j=0; j<4; j++){
            scanf("%d", &a);
            sum += a;
        }
        switch (sum)
            {
            case 1:
                printf("C\n");
                break;
            case 2:
                printf("B\n");
                break;
            case 3:
                printf("A\n");
                break;
            case 4:
                printf("E\n");
                break;
            default:
                printf("D\n");
                break;
            }
        
    }

    return 0;
}

9/10

2576

#include <stdio.h>

int main() {
    int n;
    int least=100;
    int sum=0;
    for(int i=0; i<7; i++){
        scanf("%d\n", &n);
        if(n%2!=0){
            sum+=n;
            if(least>n) least=n;
        }
    }
    if(sum==0) {
        least=-1; 
        printf("%d\n", least);
    }
    else printf("%d\n%d\n", sum, least); 

    return 0;
}

2587

#include <stdio.h>

int main(){
    int arr[5];
    int temp=0;
    int sum=0;
    for(int i=0; i<5; i++){
        scanf("%d", &arr[i]);
        sum+=arr[i];
        for(int j=0; j<5-i; j++){ //5-i보다 작아야 하는 이유는 이미 정렬된 값은 비교할 필요가 없기 때문
            if(arr[j]>arr[j+1]){
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    printf("%d\n%d\n", sum/5, arr[2]);
    return 0;
}

위와 같이 버블솔트로 했는데 시간초과 뜸

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b){
        int num1=*(int *)a;
        int num2=*(int *)b;
        if(num1<num2) return -1;
        if(num1>num2) return 1;
        return 0;
}

int main(){
    int arr[5];
    int temp=0;
    int sum=0;
    for(int i=0; i<5; i++){
        scanf("%d", &arr[i]);
        sum+=arr[i];
    }
    qsort(arr, 5, sizeof(int), compare);
    printf("%d\n%d\n", sum/5, arr[2]);
    return 0;
}

chall.py

#!/usr/bin/python3
from Crypto.Util.number import getPrime, long_to_bytes, inverse
flag = open('flag.txt', 'r').read().strip().encode()

class RSA:
    def __init__(self):
        self.p = getPrime(512)
        self.q = getPrime(512)
        self.e = 3
        self.n = self.p * self.q
        self.d = inverse(self.e, (self.p-1)*(self.q-1))
    def encrypt(self, data: bytes) -> bytes:
        pt = int(data.hex(), 16)
        ct = pow(pt, self.e, self.n)
        return long_to_bytes(ct)
    def decrypt(self, data: bytes) -> bytes:
        ct = int(data.hex(), 16)
        pt = pow(ct, self.d, self.n)
        return long_to_bytes(pt)

def main():
    crypto = RSA()
    print ('Flag:', crypto.encrypt(flag).hex())

if __name__ == '__main__':
    main()

output.txt

Flag: 05c61636499a82088bf4388203a93e67bf046f8c49f62857681ec9aaaa40b4772933e0abc83e938c84ff8e67e5ad85bd6eca167585b0cc03eb1333b1b1462d9d7c25f44e53bcb568f0f05219c0147f7dc3cbad45dec2f34f03bcadcbba866dd0c566035c8122d68255ada7d18954ad604965

주어진 두 코드를 보면 ct와 e가 주어진 RSA 문제라는 것을 알 수 있다

n 또한 주어지지 않았기 때문에 ct와 매우 작은 e를 사용하여 낮은지수 공격을 수행하면 될 것 같다

sol.py

from gmpy2 import *
from Crypto.Util.number import long_to_bytes

c = int('05c61636499a82088bf4388203a93e67bf046f8c49f62857681ec9aaaa40b4772933e0abc83e938c84ff8e67e5ad85bd6eca167585b0cc03eb1333b1b1462d9d7c25f44e53bcb568f0f05219c0147f7dc3cbad45dec2f34f03bcadcbba866dd0c566035c8122d68255ada7d18954ad604965', 16)
e = 3
 
with local_context() as ctx:
    ctx.precision=3000
    m=iroot(c,e)[0]
 
    print(long_to_bytes(m))