์๊ณ ๋ฆฌ์ฆ์ ์ํ์๊ฐ : 2๋ฒ
์์ง ๋๋ ์ ๋๋ก ์๋ ์ก๋๋ฐ ์์นจ๋ถํฐ ์ด ๋ฌธ์ ๋ณด๊ณ ์ดํด๋ฅผ ๋ชปํด์ ์์นจ๋ถํฐ ๊ธฐ๋ถ์ด ํ ์ํด๋ฒ๋ ธ๋ค.
๋จธ๋ฆฌ์ ๋ฌผ์ํ๋ง ๊ฐ๋...ํ๊ณ .... ์ฒซ์งธ์ค์ ์๊ฐ๋ณต์ก๋๋ฅผ ์๋ฏธํ๋๊ฑฐ๊ฐ์๋ฐ ๋์งธ์ค์ด ์ดํด๊ฐ ๋์ง ์์๋ค....๐
1. ์ํํ์=์๊ฐ๋ณต์ก๋
2. ์๊ฐ๋ณต์ก๋๋ฅผ ๋คํญ์์ผ๋ก ๋ํ๋ด๊ณ , ์ต๊ณ ์ฐจํญ์ ์ฐจ์
๐๐ป O(1) = 0(์์)
๐๐ป O(n) = 1
๐๐ป O(n^2) = 2
์ด๋ฅผ ์๋ฏธํ๋๊ฒ์ด์๋ค.....
๊ณ์๋ ์ฐจ์๋ ํท๊ฐ๋ ค์ ๊ทธ๊ฑธ ์ด๋ป๊ฒ ๊ตฌํ๋ผ๋๊ฑฐ์ผ ์ด๋ฌ๊ณ ์์๋ค.......
def MenOfPassion(A,n):
sum=0
for i in range(n):
sum+=A
return answer
์ด ์ฝ๋๋ for๋ฌธ์ด n๋งํผ ์ํํ๋ ๋ฐ๋ณต๋ฌธ์ด๋ฏ๋ก, O(n)์ด๋ค.
๐๐ป ์ฒซ์งธ์ค์ n์ ์ถ๋ ฅ
๐๐ป ๋์งธ์ค์ O(n)์ ์ต๊ณ ์ฐจํญ 1์ ์ถ๋ ฅํ๋ฉด ๋๋๊ฒ
โจ ์ ๋ต
# ์๊ฐ๋ณต์ก๋: O(n)
# ์ต๊ณ ์ฐจํญ์ผ๋ก ๋ํ๋ด๋ฉด 1
print(input())
print(1)
์๊ณ ๋ฆฌ์ฆ์ ์ํ์๊ฐ : 4๋ฒ
https://www.acmicpc.net/problem/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;
}
์ธ๋ถ for๋ฌธ i= 1๋ถํฐ~n-1๊น์ง
๋ด๋ถ for๋ฌธ j= i+1๋ถํฐ n๊น์ง
๐๐ป ์ด์ค for๋ฌธ์ O(n^2) ์ด๋ฏ๋ก, ์ต๊ณ ์ฐจํญ์ 2
n=7์ด๋ผ๊ณ ํ์๋,
i=1 , j=2~7 (6๋ฒ)
i=2, j=3~7 (5๋ฒ)
...
i=6, j=7 (1๋ฒ)
๐๐ป ์คํํ์๋ 1๋ถํฐ n-1๊น์ง ํฉ์ฐํ ๊ฐ์ด ๋๋ค.
โจ ์ ๋ต
n=int(input())
#1๋ถํฐ n-1๊น์ง sum
print(sum([i for i in range(1,n)]))
print(2)
์๊ณ ๋ฆฌ์ฆ์ ์ํ์๊ฐ : 6๋ฒ
https://www.acmicpc.net/problem/24267
total=0
n=7
for i in range(1, n-1):
for j in range(i+1, n):
for k in range(j+1, n+1):
print(i, j, k)
total += 1
print(total)
n=7
#i=1 -> 5+4+3+2+1
#i=2 -> 4+3+2+1
#i=3 -> 3+2+1
#i=4 -> 2+1
#i=5 -> 1
n=7์ผ๋, ์ด์ ๊ฐ์ ํจํด์ ๊ฐ์ง๊ณ ์๋ค.
โจ ์ ๋ต
n=int(input())
total=0
#i๋ 1๋ถํฐ n-2 ์ํ
for i in range(1,n-1):
total+=sum([x for x in range(1,i+1)])
print(total)
์ด ๋ฐฉ๋ฒ์ ์ญ์ ์๊ฐ์ด๊ณผ ๋ฐ์
n=int(input())
total=0
temp=0
#i=1 -> 5+4+3+2+1
#i=2 -> 4+3+2+1
#i=3 -> 3+2+1
#i=4 -> 2+1
#i=5 -> 1
for i in range(1,n-1):
temp=temp+i #1 3 6 10 15
total+=temp
print(total) #์ํ ํ์
print(3) #์ผ์ค for๋ฌธ O(n^3)
'๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค-Python] ์ฒด์คํ ๋ค์ ์น ํ๊ธฐ : 1018๋ฒ (0) | 2024.06.03 |
---|---|
[๋ฐฑ์ค-Python] ๋์ธ ์๋ฆฌ๋ฅผ ์ฐพ์๋ผ : 1652๋ฒ (0) | 2024.06.03 |
[๋ฐฑ์ค-Python] ์๋ก ๋ค๋ฅธ ๋ถ๋ถ ๋ฌธ์์ด์ ๊ฐ์ : 11478๋ฒ (0) | 2024.05.30 |
[๋ฐฑ์ค-Python] ๋จ์ด ๊ณต๋ถ : 1157๋ฒ (0) | 2024.05.30 |
[๋ฐฑ์ค-Python] ์ฌ๋ฆผํฝ : 8979๋ฒ (0) | 2024.05.29 |