์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- programmers
- ์๊ณ ๋ฆฌ์ฆ
- ์ฝ๋ํธ๋ฆฌ
- ๊ตฌํ
- ์ด์งํ์
- ํ๋ก๊ทธ๋๋จธ์ค
- ํ์ด์ฌ
- ์ผ์ฑsw์ญํ
- Algorithm
- sort
- JS
- ์๋ฐ์คํฌ๋ฆฝํธ
- ์ฐ์ จ์์
- DP
- BFS
- DART
- ๋ชป๊ทธ๋ฆฌ์ง๋ง
- ์๋ฃ๊ตฌ์กฐ
- ๋ฐฑ์ค
- ์ฝ๋ฉํ ์คํธ
- Flutter
- c#
- ๊ทธ๋ํ ํ์
- ์นด์นด์ค
- ๋์ ํ๋ก๊ทธ๋๋ฐ
- ๋ฌธ์์ด ํ์ฑ
- JavaScript
- ์คํฐ๋
- Java
- BAEKJOON
- Today
- Total
๋ชฉ๋ก๐ Computer Science/Algorithms (4)
Algo ์ฐ์
์ต๋๊ณต์ฝ์ def GCD(num1, num2) : if num2 == 0: return num1 else : return GCD(num2, num1 % num2) ์ต์ ๊ณต๋ฐฐ์(LCM) LCM = (a * b) / GCD(a, b) ์ต๋๊ณต์ฝ์ ์ต์๊ณต๋ฐฐ์ ๊ตฌํ๊ธฐ ์์ a, b = map(int, input().split()) def GCD(num1, num2) : if num2 == 0: return num1 else : return GCD(num2, num1 % num2) print(GCD(a, b)) print((a * b) // GCD(a,b))
์๋ฐฉํฅ ๊ฑฐํ์ ๋ ฌ (bidirectional bubble sort)๋ผ๊ณ ๋ ๋ถ๋ฆฌ๋ฉฐ ๋ฒ๋ธ์ ๋ ฌ์ ๋ณํ์ด๋ค. ํ๋ฒ์ ๋ฃจํด๋ง๋ค ๋ฐฉํฅ์ ๋ฐ๊ฟ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ๋ฒ๋ธ์ ๋ ฌ๊ณผ ํฌ๊ฒ ๋ค๋ฅด์ง๋ ์์ง๋ง ๋ฒ๋ธ ์ ๋ ฌ๋ณด๋ค ๋น ๋ฅด๋ค. ํ์ด์ฌ ์์ ์ฝ๋ def cocktail(arr, a, b): swapped = True while swapped == True: swapped = False for i in range(a, b): if arr[i] > arr[i+1]: arr[i], arr[i+1] = arr[i+1], arr[i] if swapped == False: break swapped = False b = b - 1 for i in range(b-1, a-1, -1): if arr[i] > arr[i+1]: arr[i], ..
Bubble Sort(๋ฒ๋ธ ์ ๋ ฌ)์ ๋ ์ธ์ ํ ์์๋ฅผ ๊ฒ์ฌํ์ฌ ์ ๋ ฌํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค. ์๊ฐ๋ณต์ก๋๋ O(n^2) ์ผ๋ก ์๋นํ ๋๋ฆฌ์ง๋ง, ์ฝ๋์์ฒด๊ฐ ๋จ์ํด์ ์์ฃผ ์ฌ์ฉ๋๋ค. ์ด๋ ๊ฐ์ ๋ฐฉ์์ผ๋ก ์๋ฐฉํฅ ์ ๋ ฌ์ ํ๊ฒ๋๋ฉด ์นตํ ์ผ ์ ๋ ฌ์ด ๋๋ค. ํ์ด์ฌ ์์ ์ฝ๋ def bubbleSort(x): length = len(x)-1 for i in range(length): for j in range(length-i): if x[j] > x[j+1]: x[j], x[j+1] = x[j+1], x[j] return x
์ ๋ ฌ๋ ๋ฆฌ์คํธ์ ๋ฒ์๋ฅผ ๋ฐ์ฉ ๋๋์ด ํ์์ ์งํํ๋ ๋ฐฉ๋ฒ ์ ๋ ฌ๋ ๋ฆฌ์คํธ์์๋ง ์ฌ์ฉ๊ฐ๋ฅ ์๋๊ฐ ๋น ๋ฆ ์ํฉ ์๋ ์ต์ O(1) ๋ณดํต O(logn) ์ต์ O(logn) ๋์ ๋ฐฐ์ด์ ์ค๊ฐ๊ฐ ์ค์ ์ค๊ฐ๊ฐ๊ณผ ๊ฒ์๊ฐ ๋น๊ต ๊ฒ์๊ฐ๊ณผ ๊ฐ์ ๊ฒฝ์ฐ - ํ์์๋ฃ ๊ฒ์๊ฐ์ด ์ค๊ฐ๊ฐ๋ณด๋ค ํฐ ๊ฒฝ์ฐ - low๋ฅผ ์ค๊ฐ๊ฐ+1 ๋ก ์กฐ์ ๊ฒ์๊ฐ์ด ์ค๊ฐ๊ฐ๋ณด๋ค ์์ ๊ฒฝ์ฐ - high๋ฅผ ์ค๊ฐ๊ฐ-1 ๋ก ์กฐ์ low๊ฐ high๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์๊ฒฝ์ฐ๊น์ง ๋ฐ๋ณต(๊ฐ์ ์ฐพ์ ๊ฒฝ์ฐ๊ฐ ์๋๋ผ๋ฉด) ์ด์งํ์ ๊ตฌํ def binarySearch(data, num): low = 0 high = len(data) - 1 while(low data[mid]: low = mid + 1 else : high = mid - 1 return False ์ด์งํ์ ์ฌ์ฉ ์์ ์ฝ๋ n..