10. ์์์ ํฉ์ฑ์ (Prime and Composite Numbers) Codility Lesson ํ๊ตญ์ด ์ ๋ฆฌ๋ณธ (JavaScript ver.)
์์(Prime Number)์ ํฉ์ฑ์(Composite Number)์์(Prime Number) ๋ 1๋ณด๋ค ํฌ๊ณ , ์๊ธฐ ์์ ๊ณผ 1์ ์ ์ธํ ์ฝ์๊ฐ ์๋ ์ ๋ฅผ ์๋ฏธํ๋ค.ํฉ์ฑ์(Composite Number) ๋ 1๊ณผ ์๊ธฐ ์์ ์ด์ธ์๋ ๋ค๋ฅธ ์ฝ์๋ฅผ ๊ฐ์ง๋ ์ ๋ฅผ ์๋ฏธํ๋ค.์๋ฅผ ๋ค์ด, 2, 3, 5, 7, 11, 13 ๋ฑ์ ์์์ด๋ฉฐ, 4, 6, 8, 9, 10 ๋ฑ์ ํฉ์ฑ์์ด๋ค.1. O(√n) ์๊ฐ ๋ณต์ก๋์ ์ฝ์ ๊ฐ์ ๊ตฌํ๊ธฐn์ ์ฝ์๋ฅผ ์ฐพ๋ ๊ธฐ๋ณธ์ ์ธ ๋ฐฉ๋ฒ์ 1๋ถํฐ n๊น์ง ๋ชจ๋ ์๋ฅผ ํ์ธํ๋ ๊ฒ ์ด๋ค. ํ์ง๋ง n์ ์ฝ์๋ ๋์นญ์ฑ์ ๊ฐ์ง๋ฏ๋ก, √n ๊น์ง๋ง ํ์ํด๋ ์ ์ฒด ์ฝ์๋ฅผ ๊ตฌํ ์ ์๋ค.JavaScript ์ฝ๋:function countDivisors(n) { let count = 0; let..
9. ์ต๋ ์ฌ๋ผ์ด์ค ๋ฌธ์ (Maximum Slice Problem) Codility Lesson ํ๊ตญ์ด ์ ๋ฆฌ๋ณธ (JavaScript ver.)
์ต๋ ์ฌ๋ผ์ด์ค ๋ฌธ์ ๋?์ฃผ์ด์ง ์ ์ ๋ฐฐ์ด A = [aโ, aโ, ..., aโโโ] ์์ ์ฐ์๋ ๋ถ๋ถ ๋ฐฐ์ด(์ฌ๋ผ์ด์ค, Slice) ์ค ํฉ์ด ์ต๋๊ฐ ๋๋ ๊ตฌ๊ฐ์ ์ฐพ๋ ๋ฌธ์ ์ด๋ค. ์ฆ, ๋ ์ธ๋ฑ์ค p, q (p ≤ q)๋ฅผ ์ ํํ์ฌ A[p] + A[p+1] + ... + A[q] ๊ฐ์ด ์ต๋๊ฐ ๋๋ ๊ฒฝ์ฐ ๋ฅผ ์ฐพ๋๋ค.์๋ฅผ ๋ค์ด, ๋ค์๊ณผ ๊ฐ์ ๋ฐฐ์ด์ด ์์ ๋:A = [5, -7, 3, 5, -2, 4, -1];์ ๋ฐฐ์ด์์ ์ต๋ ํฉ์ ๊ฐ๋ ๋ถ๋ถ ๋ฐฐ์ด์ [3, 5, -2, 4]์ด๋ฉฐ, ํฉ์ 10์ด๋ค.1. O(n³) ์๊ฐ ๋ณต์ก๋์ ๋นํจ์จ์ ์ธ ๋ฐฉ๋ฒ๋ชจ๋ ๊ฐ๋ฅํ ์ฌ๋ผ์ด์ค๋ฅผ ํ์ํ์ฌ ์ต๋๊ฐ์ ์ฐพ๋ ๋ฐฉ๋ฒ์ด๋ค.JavaScript ์ฝ๋:function slowMaxSlice(A) { let n = A.length; let r..
8. ๋ฆฌ๋ (Leader) Codility Lesson ํ๊ตญ์ด ์ ๋ฆฌ๋ณธ (JavaScript ver.)
๋ฆฌ๋(Leader)๋?์ฃผ์ด์ง ์์ด A = [aโ, aโ, ..., aโโโ] ์์ ๋ฆฌ๋(Leader) ๋ ์์ด์ ์์ ์ค ์ ๋ฐ์ ์ด๊ณผํ์ฌ ๋ฑ์ฅํ๋ ์์ ๋ฅผ ์๋ฏธํ๋ค.์๋ฅผ ๋ค์ด, ๋ค์๊ณผ ๊ฐ์ ์์ด์ด ์์ ๋:A = [6, 8, 4, 6, 8, 6, 6];์ ์์ด์์ 6์ 4๋ฒ ๋ฑ์ฅํ์ฌ n/2 = 3.5 ๋ณด๋ค ๋ง์ด ๋ฑ์ฅํ๋ฏ๋ก ๋ฆฌ๋๊ฐ ๋๋ค. ๋ฆฌ๋๋ ์ต๋ ํ๋๋ง ์กด์ฌ ํ๋ค.1. O(n²) ์๊ฐ ๋ณต์ก๋์ ๋จ์ํ ๋ฐฉ๋ฒ๊ฐ ์์์ ๋ฑ์ฅ ํ์๋ฅผ ์ธ์ด ๋ฆฌ๋๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ด๋ค.JavaScript ์ฝ๋:function slowLeader(A) { let n = A.length; let leader = -1; for (let k = 0; k Math.floor(n / 2)) { lea..
6. ์ ๋ ฌ (Sorting) Codility Lesson ํ๊ตญ์ด ์ ๋ฆฌ๋ณธ (JavaScript ver.)
์ ๋ ฌ(Sorting)์ด๋?์ ๋ ฌ์ด๋ ๋ฐ์ดํฐ๋ฅผ ํน์ ํ ์์๋๋ก ๋ฐฐ์นํ๋ ๊ณผ์ ์ด๋ค. ์ผ๋ฐ์ ์ผ๋ก ์ซ์ ๋๋ ๋ฌธ์์ด์ ๊ฐ์ ๋ฐ๋ผ ์ ๋ ฌํ๋ค. ์๋ฅผ ๋ค์ด, ํ์์ ํค ์์๋๋ก ์ ๋ ฌํ๊ฑฐ๋, ๋์๋ฅผ ์ธ๊ตฌ์ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํ ์ ์๋ค.๋ค์๊ณผ ๊ฐ์ ๋ฐฐ์ด์ด ์๋ค๊ณ ๊ฐ์ ํ์.A = [5, 2, 8, 14, 1, 16];์ด๋ฅผ ์ซ์ ํฌ๊ธฐ ์์๋ก ์ ๋ ฌํ๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.A = [1, 2, 5, 8, 14, 16];์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋์ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋์ ๋ฐ๋ผ ์ฐจ์ด๊ฐ ์๋ค. ์ฌ๊ธฐ์๋ ๋ํ์ ์ธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ดํด๋ณธ๋ค.1. ์ ํ ์ ๋ ฌ (Selection Sort)์์ด๋์ด: ๋ฐฐ์ด์์ ๊ฐ์ฅ ์์ ์์๋ฅผ ์ฐพ์ ์ฒซ ๋ฒ์งธ ์์น์ ๊ตํํ๋ ์์
์ ๋ฐ๋ณตํ๋ค.JavaScript ์ฝ๋:function selectionSort(A) { let n..
4. ์์ ๊ฐ์ ์ธ๊ธฐ (Counting Elements) Codility Lesson ํ๊ตญ์ด ์ ๋ฆฌ๋ณธ (JavaScript ver.)
์์ ๊ฐ์ ์ธ๊ธฐ๋?๋ฐฐ์ด์ ํ์ฉํ์ฌ ์ซ์ ์ํ์ค๋ฅผ ์ ์ฅํ๋ ๋ฐฉ๋ฒ์๋ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์๋ค. ์ผ๋ฐ์ ์ผ๋ก ์ฐ์๋ ์ซ์ aโ, aโ, ..., aโโโ๋ฅผ ๋ฐฐ์ด์ ์ธ๋ฑ์ค์ ๋ง์ถฐ ์ ์ฅํ๋ค.์๋ฅผ ๋ค์ด:let A = [4, 2, 4, 5];// A[0] = 4, A[1] = 2, A[2] = 4, A[3] = 5๊ทธ๋ฌ๋ ์์๋ฅผ ์ง์ ์ ์ฅํ๋ ๋์ , ๊ฐ ์ซ์์ ๋ฑ์ฅ ํ์๋ฅผ ์ธ๋ ๋ฐฐ์ด ์ ๋ง๋ค ์๋ ์๋ค.์ด ๊ฒฝ์ฐ, ๋ฐฐ์ด count[] ๋ ํด๋น ๊ฐ์ด ๋ฑ์ฅํ ํ์๋ฅผ ์ ์ฅํ๋ค.count[2] = 1; // ์ซ์ 2๋ ํ ๋ฒ ๋ฑ์ฅcount[4] = 2; // ์ซ์ 4๋ ๋ ๋ฒ ๋ฑ์ฅcount[5] = 1; // ์ซ์ 5๋ ํ ๋ฒ ๋ฑ์ฅ์ด ๋ฐฉ๋ฒ์ ์ฌ์ฉํ๋ฉด ํน์ ์ซ์๊ฐ ๋ฑ์ฅํ ํ์๋ฅผ O(1) ์๊ฐ์ ํ์ธํ ์ ์๋ค.1. O(n + m) ์๊ฐ..