코테 스터디 22번째 TIL : 시간복잡도 , 완전탐색 문제 풀이

코테 스터디 N번째 TIL : 문제 풀이

• 문제

https://www.acmicpc.net/problem/24262

 

 

 

• 코드

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

 

 

• 설명 및 개념

 

주어진 알고리즘 MenOfPassion(A[], n)에서 수행하는 코드1의 수행 횟수는 항상 1회입니다. 이유는 주어진 n에 상관없이 배열 A의 중간에 해당하는 인덱스의 값을 반환하기 때문입니다.

문제를 분석하면:

 

1. 수행 횟수: 코드1이 호출되는 횟수는 n과 상관없이 항상 1번입니다. 즉, n의 값이 무엇이든 상관없이 한 번만 수행됩니다.
2. 다항식의 최고차항 차수: 수행 횟수는 입력 n에 비례하지 않는 상수 시간(즉, O(1))입니다. 이는 다항식으로 나타내면 최고차항의 차수가 0이 된다는 의미입니다.

 

 

 

 

---

 

 

• 문제

https://www.acmicpc.net/problem/2231

 

 

 

• 코드

n=int(input())
ssj=[]

for i in range(n):
    if n==sum(map(int,list(str(i))))+i:
        ssj.append(i)

if ssj:        
    print(min(ssj))
else:
    print(0)

 

 

• 설명 및 개념

 

💡 a=sum(map(int,list(str(number))))

• 다음을 통해서 number가 숫자이면 그 숫자의 각 자릿수의 합을 구할 수 있다 

 

---

 

 

• 문제 - 완전탐색

https://www.acmicpc.net/problem/1018

 

 

• 코드

n,m=map(int,input().split())
board=[list(input().strip()) for _ in range(n)]
##공백을 제외하고 입력받기 

pattern1 = [
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW"
]

pattern2 = [
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB",
    "BWBWBWBW",
    "WBWBWBWB"
]
def countch(board,x,y,pattern):
    count=0
    for i in range(8):
        for j in range(8):
            if board[x+i][y+j] != pattern[i][j]:
                count+=1
    return count

minch=217000000
for i in range(n-7):
    for j in range(m-7):
        ch1= countch(board,i,j,pattern1)
        ch2=countch(board,i,j,pattern2)
        minch=min(minch,ch1,ch2)
   
print(minch)

 

 

---

 

 

 

• 문제 - 완전탐색

https://www.acmicpc.net/problem/2839

 

• 코드

 

n=int(input())
cnt=0
while n >=0:
    if n%5==0:
        cnt+=n//5
        print(cnt)
        break
    n=n-3
    cnt+=1
    
else:
    print(-1)

 

 

 

• 설명

💡 while else 구문: while 루프가 정상적으로 종료될 때 즉, break 문 없이 종료 될때 else 구문이 실행된다.