์ธ๋„ค์ผ 12. ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜ (Greatest Common Divisor, GCD) Codility Lesson ํ•œ๊ตญ์–ด ์ •๋ฆฌ๋ณธ (JavaScript ver.) ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(GCD)๋ž€?๋‘ ๊ฐœ์˜ ์ •์ˆ˜ a, b์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜(GCD)๋Š” ๋‘ ์ˆ˜๋ฅผ ๋™์‹œ์— ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ํฐ ์ •์ˆ˜ ๋ฅผ ์˜๋ฏธํ•œ๋‹ค.1. O(n) ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (๋บ„์…ˆ ๋ฐฉ์‹)JavaScript ์ฝ”๋“œ:function gcdSubtraction(a, b) { if (a === b) return a; return a > b ? gcdSubtraction(a - b, b) : gcdSubtraction(a, b - a);}2. O(log n) ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ์œ ํด๋ฆฌ๋“œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (๋‚˜๋จธ์ง€ ๋ฐฉ์‹)JavaScript ์ฝ”๋“œ:function gcd(a, b) { return a % b === 0 ? b : gcd(b, a % b);}์ด ๋ฐฉ๋ฒ•์€ ๋น ๋ฅด๊ณ , ๋Œ€๋ถ€๋ถ„์˜ ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์–ธ์–ด์—์„œ ๊ธฐ๋ณธ์ ์œผ๋กœ ์ œ๊ณต๋œ..
์ธ๋„ค์ผ 11. ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด (Sieve of Eratosthenes) Codility Lesson ํ•œ๊ตญ์–ด ์ •๋ฆฌ๋ณธ (JavaScript ver.) ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด๋ž€?์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด(Sieve of Eratosthenes) ๋Š” ์ฃผ์–ด์ง„ ๋ฒ”์œ„ ๋‚ด์—์„œ ๋ชจ๋“  ์†Œ์ˆ˜๋ฅผ ๋น ๋ฅด๊ฒŒ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ ์†Œ์ˆ˜๋ฅผ ๊ฑธ๋Ÿฌ๋‚ด๋Š” ๋ฐฉ์‹์œผ๋กœ ๋™์ž‘ํ•˜๋ฉฐ, O(n log log n) ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.1. O(n log log n) ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ์†Œ์ˆ˜ ํŒ๋ณ„JavaScript ์ฝ”๋“œ:function sieve(n) { let sieve = new Array(n + 1).fill(true); sieve[0] = sieve[1] = false; for (let i = 2; i * i ์ด ๋ฐฉ๋ฒ•์„ ํ†ตํ•ด n ์ดํ•˜์˜ ๋ชจ๋“  ์†Œ์ˆ˜๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค.2. ์†Œ์ธ์ˆ˜ ๋ถ„ํ•ด (Factorization)์†Œ์ธ์ˆ˜ ๋ถ„ํ•ด๋Š” ์ •์ˆ˜๋ฅผ ์†Œ์ˆ˜์˜ ๊ณฑ์œผ๋กœ ํ‘œํ˜„ํ•˜๋Š” ๊ณผ์ • ์ด๋‹ค.JavaSc..
์ธ๋„ค์ผ 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..
์ธ๋„ค์ผ 7. ์Šคํƒ๊ณผ ํ (Stacks and Queues) Codility Lesson ํ•œ๊ตญ์–ด ์ •๋ฆฌ๋ณธ (JavaScript ver.) ์Šคํƒ(Stack)๊ณผ ํ(Queue)๋ž€?์Šคํƒ๊ณผ ํ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๊ณ  ๊ด€๋ฆฌํ•˜๋Š” ๋Œ€ํ‘œ์ ์ธ ์ž๋ฃŒ๊ตฌ์กฐ์ด๋‹ค. ์ด๋“ค์€ push(์‚ฝ์ž…) ๋ฐ pop(์‚ญ์ œ) ์—ฐ์‚ฐ์„ ์ œ๊ณตํ•˜์ง€๋งŒ, ๋ฐ์ดํ„ฐ์˜ ์ž…์ถœ๋ ฅ ๋ฐฉ์‹์ด ๋‹ค๋ฅด๋‹ค.1. ์Šคํƒ(Stack)์Šคํƒ์€ LIFO(Last In, First Out) ๊ตฌ์กฐ๋ฅผ ๊ฐ€์ง€๋ฉฐ, ๊ฐ€์žฅ ์ตœ๊ทผ์— ์ถ”๊ฐ€๋œ ์š”์†Œ๊ฐ€ ๊ฐ€์žฅ ๋จผ์ € ์ œ๊ฑฐ๋œ๋‹ค. ๋งˆ์น˜ ์ ‘์‹œ๋ฅผ ์Œ“์•„์˜ฌ๋ฆฌ๊ณ  ์œ„์—์„œ๋ถ€ํ„ฐ ํ•˜๋‚˜์”ฉ ์ œ๊ฑฐํ•˜๋Š” ๋ฐฉ์‹๊ณผ ์œ ์‚ฌํ•˜๋‹ค.JavaScript ์ฝ”๋“œ:class Stack { constructor() { this.stack = []; } push(x) { this.stack.push(x); } pop() { if (this.isEmpty()) throw new ..
์ธ๋„ค์ผ 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..
์ธ๋„ค์ผ 5. ๋ˆ„์  ํ•ฉ (Prefix Sums) Codility Lesson ํ•œ๊ตญ์–ด ์ •๋ฆฌ๋ณธ (JavaScript ver.) ๋ˆ„์  ํ•ฉ(Prefix Sums)์ด๋ž€?๋ฐฐ์—ด์˜ ํŠน์ • ๊ตฌ๊ฐ„(์Šฌ๋ผ์ด์Šค)์˜ ํ•ฉ์„ ๋น ๋ฅด๊ฒŒ ๊ณ„์‚ฐํ•˜๋Š” ๊ฐ•๋ ฅํ•œ ๊ธฐ๋ฒ•์ด ๋ˆ„์  ํ•ฉ(Prefix Sums) ์ด๋‹ค. ์ด๋Š” ๋ฐฐ์—ด์˜ ์ฒ˜์Œ๋ถ€ํ„ฐ ํŠน์ • ์œ„์น˜๊นŒ์ง€์˜ ํ•ฉ์„ ๋ฏธ๋ฆฌ ๊ณ„์‚ฐํ•ด ์ €์žฅํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค.์˜ˆ๋ฅผ ๋“ค์–ด, ๋ฐฐ์—ด A๊ฐ€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค๊ณ  ํ•˜์ž.A = [aโ‚€, aโ‚, aโ‚‚, ..., aโ‚™โ‚‹โ‚]๊ทธ๋Ÿฌ๋ฉด ๋ˆ„์  ํ•ฉ ๋ฐฐ์—ด P๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์ด ์ •์˜๋œ๋‹ค.P[0] = 0P[1] = aโ‚€P[2] = aโ‚€ + aโ‚P[3] = aโ‚€ + aโ‚ + aโ‚‚...P[n] = aโ‚€ + aโ‚ + ... + aโ‚™โ‚‹โ‚์ด์ „ ๊ฐ’ P[k-1]์— ํ˜„์žฌ ๊ฐ’ A[k-1]์„ ๋”ํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ˆ„์  ํ•ฉ์„ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ „์ฒด ์—ฐ์‚ฐ์€ O(n) ์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง„๋‹ค.1. O(n) ์‹œ๊ฐ„ ๋ณต์žก๋„์˜ ๋ˆ„์  ํ•ฉ ๊ณ„์‚ฐJavaScript ์ฝ”๋“œ:funct..
์ธ๋„ค์ผ 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) ์‹œ๊ฐ„..