BOJ_14697 방 배정하기 -Python3

문제분석

1. 관찰
- 가능한지 안한지만 출력하면된다.
- A,B,C는 서로 다른 수 이고, 배수이거나 배수가 아닌 경우로 구분할 수 있다. => 시간복잡도를 줄이기 위해서 분기처리 해보았다.
- 다른 숫자에대해서 나올 수 있는 조합을 구한다. => for문
- DP(top-down, botto-up)풀이. 참조: https://skeo131.tistory.com/91

2. 복잡도
- 서로 다른 경우: O(n*n*n) = 300*300*300 보다 작으므로 가능

3. 자료구조
- int

해결코드

import sys
si = sys.stdin.readline

A,B,C,N = map(int, si().split())
flag = False 

if A==1:
    print(1)
else:
    if C%A==0 and B%A==0: # B,C는 A의 배수
        if N%A==0:
            print(1)
        else:
            print(0)
    else:
        if C%B==0: # A,B 조합
            for i in range((N//A)+1):
                for j in range((N//B)+1):
                    if A*i + B*j == N:
                        flag = True
            if flag:
                print(1)
            else:
                print(0)
        else: # A,B,C 조합
            for i in range((N//A)+1):
                for j in range((N//B)+1):
                    for k in range((N//C)+1):
                        if A*i + B*j + C*k == N:
                            flag = True
            if flag:
                print(1)
            else:
                print(0)

BOJ_3040 백설 공주와 일곱 난쟁이 -Python3

문제분석

1. 관찰
- 서로 다른 9개중 7개를 만들어야 하므로 2개를 제외하고 합을 구해 100이 되면 출력한다.

2. 복잡도
- O(9C2) = 9!/(2!7!) >> 36 가능

3. 자료구조
- 난쟁이 : int[]

해결코드

import sys
si = sys.stdin.readline

dwarves = list( int(si()) for _ in range(9))
s = sum(dwarves)

for i in range(9):
    for j in range(i+1,9):
        if s-dwarves[i]-dwarves[j] == 100:
            for k in range(9):
                if k == i or k == j:
                    continue
                else: 
                    print(dwarves[k])

BOJ_1977 완전제곱수 -Python3

문제분석

1. 관찰
- M이상 N이하의 자연수 중 완전제곱수인 것을 모두 골라 그 합과 그 중 최소값을 찾는다.
- 완전제곱수를 찾는 것이므로 i의 제곱근 범위까지만 탐색한다.

2. 복잡도
- O((N-M+1)*(N**(1/2))) = 1000000*100 >> 100만 가능

3. 자료구조
- 완전제곱수 : int[]

해결코드

import sys
si = sys.stdin.readline

M = int(si())
N = int(si())
nums = []

for i in range(M,N+1):
    for j in range(1,int(i**(1/2))+1):
        if i == j*j:
            nums.append(i)

if nums:
    print(sum(nums))
    print(min(nums))
else:
    print(-1)

BOJ_10419 지각 -Python3

문제분석

1. 관찰
- 교수님이 t시간 만큼 지각으로 하시면, s = t**2 만큼 일찍 끝내주신다.
- 수업시간 = t + t**2 인 경우 수업이 바로 끝날 수 있다.


2. 복잡도
- O(t*c) T*C = 100*10000 >> 가능

3. 자료구조
- 테스트케이스, 수업시간 : int

해결코드

import sys
si = sys.stdin.readline

T = int(si())
for _ in range(T):
    c = int(si()) # 수업시간
    t = 0
    while True:
        t+=1
        if t+t**2 <= c:
            continue
        else:
            print(t-1)
            break

BOJ_17173 배수들의 합 -Python3

문제분석

1. 관찰
- 서로다른 M개의 정수 K가 오름차순으로 주어진다.
- 1이상 N 이하인 수의 합을 구해라
=> k의 배수들을 중복없이 모두 찾아 더한다.

2. 복잡도
- O(N*M) = 1000*1000 >> 가능

3. 자료구조
- 배수들 : int[]

해결코드

import sys 
si = sys.stdin.readline

N, M = map(int, si().split())
nums = list(map(int, si().split()))
ans = []

for i in range(1,N+1):
    for j in range(M):
        if i%nums[j] == 0 and i not in ans:
            ans.append(i)
print(sum(ans))

모듈이란?

소프트웨어 설계에서 기능단위로 분해하고 추상화되어 재사용 및 공유 가능한 수준으로 만들어진 단위
즉, 기능단위로 분해되어있고 추상화되어 재사용 및 공유가 가능하도록 구현된 것

그럼 모듈화는 뭔가?

소프트웨어의 성능을 향상시키거나 시스템의 디버깅, 시험, 통합 및 수정을 용이하도록 하는 소프트웨어 설계 기법

모듈화를 했을 때의 장점이 뭔가? 

1. 프로그램의 효율적인 관리 및 성능 향상
2. 전체적인 소프트웨어 이해의 용이성 증대 및 복잡성 감소
3. 소프트웨어 시험, 통합, 수정 시 용이성 제공
4. 기능의 분리가 가능하고 인터페이스가 단순
5. 오류의 파급 효과를 최소화
6. 모듈의 재사용 가능으로 개발과 유지보수가 용이

정리해서 말하자면, 기능단위로 분리되어 코드의 복잡도가 감소된다. 따라서, 코드를 이해하기에 용이하고 재사용 및 유지보수에도 좋다.

모듈화의 목표는 무엇인가?

- 모듈 간 결합도의 최소화(Lose Coupling)
- 모듈 내 요소들간의 응집도 최대화(Strong Sohension)