TIL 코딩공장

20240120 백준 C언어 공부
9498번 시험 성적

1. 문제
시험 점수를 입력받아 90 ~ 100점은 A, 80 ~ 89점은 B, 70 ~ 79점은 C, 60 ~ 69점은 D, 나머지 점수는 F를 출력하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 시험 점수가 주어진다. 시험 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

3. 출력
시험 성적을 출력한다.

>>>코드

# include <stdio.h>
int main(void){
    int score;
    scanf("%d", &score);
    if (score >= 90)
        printf("A");
    else if (score >= 80)
        printf("B");
    else if (score >= 70)
        printf("C");
    else if (score >= 60)
        printf("D");
    else
        printf("F");
}

>>>문제 링크
https://www.acmicpc.net/problem/9498

20240320 백준 파이썬 공부
24267번 알고리즘 수업 - 알고리즘의 수행 시간 6

1. 문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 
아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.
>>> MenOfPassion 알고리즘 코드

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;
}

2. 입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

3. 출력
첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 
단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

>>>코드

n = int(input())
print((n*(n-1)*(n-2))//6)
print(3)

>>>해설
이전과 동일하게 시간 복잡도에 관한 문제이다

해당 코드를 보면
입력된 n에 따라 i가 1 ~ n-2까지 n-3회(i), 
그리고 그 i에 따라 j가 i+1 ~ n-1까지 n-2-i회(j),
마지막으로 그 j에 따라 k가 j+1 ~ n 까지 n-1-j회(k) 반복하는 코드이다.

하니씩 풀어보면
>>n 입력
>> i 가 1~n-1 까지 일떄 더하기
>> i = 1인 경우
> j = 2일때 k = 3~n까지 i * j * k>> 시행 횟수(항의 개수) n-2
> j = 3일때 k = 4~n까지 i * j * k>> 시행 횟수(항의 개수) n-3
...
> j = n-1일때 k = n까지 i * j * k>> 시행 횟수(항의 개수) 1

>> i = 2인 경우
> j = 3일때 k = 4~n까지 i * j * k>> 시행 횟수(항의 개수) n-3
> j = 4일때 k = 5~n까지 i * j * k>> 시행 횟수(항의 개수) n-4
...
> j = n-1일때 k = n까지 i * j * k>> 시행 횟수(항의 개수) 1

>> i = 3인 경우
>> i = 4인 경우
... ...
>> i = n-2 인 경우
까지

따라서 총 시행횟수는 
1부터 n-2까지의 합 + 1부터 n-3까지의 합 + ... + 1 
= (n-2)(n-1) / 2 + (n-3)(n-2) / 2 + ... 1
= n*(n-1)*(n-2) / 6 이다.
그리고 수행횟수는 n의 세제곱에 비례하고, 최고차항의 차수는 3 이다.

>>>문제링크
https://www.acmicpc.net/problem/24267

20240319 백준 파이썬 공부
24266번 알고리즘 수업 - 알고리즘의 수행 시간 5

1. 문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 
아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.
>>>MenOfPassion 알고리즘 코드

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;
}

2. 입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

3. 출력
첫째 줄에 코드1 의 수행 횟수를 출력한다.

>>> 코드

n = int(input())
print(n**3)
print(3)

>>> 해설
이전 시리즈와 동일하게 시간 복잡도에 관한 문제이다

해당 코드는 3중 중첩 반복문을 포함하고 있으며, 반복의 범위가 1~n으로 동일하므로,
수행 횟수는 n * n * n으로 n의 세제곱으로 볼 수 있다.
따라서 수행횟수는 n의 세제곱에 비례하며, 최고차항의 차수는 3이다.

>>> 문제링크
https://www.acmicpc.net/problem/24266

20240116 백준 C언어 공부
2588번 곱셈

1. 문제
(세 자리 수) × (세 자리 수)는 다음과 같은 과정을 통하여 이루어진다.

<그림>
       472 ......(1)
     X385 .......(2)
-----------
     2360 .......(3)
   3776   .......(4)
 1416     .......(5)
-----------
 181720  .......(6)

(1)과 (2)위치에 들어갈 세 자리 자연수가 주어질 때 
(3), (4), (5), (6)위치에 들어갈 값을 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 (1)의 위치에 들어갈 세 자리 자연수가, 둘째 줄에 (2)의 위치에 들어갈 세자리 자연수가 주어진다.

3. 출력
첫째 줄부터 넷째 줄까지 차례대로 (3), (4), (5), (6)에 들어갈 값을 출력한다.

>>>코드

# include <stdio.h>
int main(void){
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);
    printf("%d\n%d\n%d\n%d\n", n*(m%10) , n*((m%100)/10), n*(m/100), n*m);
    return 0;
}

>>>문제링크
https://www.acmicpc.net/problem/2588

20240317 백준 파이썬 공부
24264번 알고리즘 수업 - 알고리즘의 수행 시간 3

1. 문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 
아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.
>>> MenOfPassion 알고리즘 코드

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. 입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

3. 출력
첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 
단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

>>>코드

n = int(input())
print(n*n)
print(2)

>>> 해설
코드에 이중 반복문(중첩 반복문)이 포함되어 있기 때문에 n의 2제곱 만큼 코드가 시행된다.
따라서 코드는 n의 제곱에 비례하며, 최고차항의 차수는 2이다.

>>>문제 링크
https://www.acmicpc.net/problem/24264

20240316 백준 파이썬 공부
24263번 알고리즘 수업 - 알고리즘의 수행 시간 2

1. 문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 
아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.
>>> MenOfPassion 알고리즘 코드

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

2. 입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

3. 출력
첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 
단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

>>>코드

n = int(input())
print(n)
print(1)

>>> 해설
for 반복문에 따라 알고리즘의 수행 시간이 n에 비례한다.
따라서 최고차항의 차수가 1이다.

>>>문제 링크
https://www.acmicpc.net/problem/24263

20240315 백준 파이썬 공부
264262번 알고리즘 수업 - 알고리즘의 수행 시간 1

1. 문제
오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 
아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.
>>> MenOfPassion 알고리즘코드
MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

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

2. 입력
첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

3. 출력
첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 
단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

>>>코드

n = int(input())
print(1)
print(0)

>>>해설
처음 보고 당황했지만 이 문제는 코딩 문제라기보다는 "시간 복잡도"라는 코딩 개념에 대한 주관식 문제라고 생각하는 것이 올바르다.

시간 복잡도.
코드를 짜게 되면 코드가 실행되는데 걸리는 시간을 의미하는데
시간 복잡도는 코드에 따라 굉장히 다양한 경우가 나타난다.
- 입력 숫자에 관계없이 항상 걸리는 시간이 일정한 경우
- 입력 숫자의 비례하여 시간이 느는 경우
- 입력 숫자의 거듭제곱에 비례하여 시간이 급격하게 느는 경우

그리고 이것은 코드의 실행 횟수와 관련이 있으며, 
따라서 이 문제는 주어진 코드에 n을 입력했을때 n과 관련하여 시행횟수가 어떻게 변하는지 다항식을 만들고, 입력한 숫자를 해당 다항식에 대입했을 때의 결과값과 다항식의 최고차향의 계수를 물어보는 문제인 것이다.

그러나 해당 코드를 보았을 때, n에 어떠한 숫자를 넣던간에 시행횟수는 1로 고정이며, 따라서 시행횟수 다항식도 O = 1로 최고차항의 계수가 0이다.

따라서 코드가 위와 같이 나온다.

>>>시간 복잡도 관련 자료 사이트
https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

>>> 문제 링크
https://www.acmicpc.net/problem/24262

20240311 백준 파이썬 공부
10870번 피보나치 수 5

1. 문제
피보나치 수는 0과 1로 시작한다. 
0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 
그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

3. 출력
첫째 줄에 n번째 피보나치 수를 출력한다.

>>>코드

n = int(input()) # n 입력받기
calculate = [0, 1] # 0번째와 1번째 피보나치 수를 저장한 리스트
if n != 0: # n이 0이 아닌 경우
    for i in range(n-1):
        calculate.append(sum(calculate)) # 그 전의 두 수를 더해서 다음 피보나치 수 구하기
        calculate.pop(0) # 가장 앞에 있는 것은 삭제
    print(calculate[-1]) # 마지막 피보나치 수 출력
else: # n 이 0인 경우
    print(0) # 0 출력