-
[๋ฐฑ์ค] 24265๋ฒ: ์๊ณ ๋ฆฌ์ฆ ์์ - ์๊ณ ๋ฆฌ์ฆ์ ์ํ ์๊ฐ 4 (Node.js)๐ ์๊ณ ๋ฆฌ์ฆ/๋ฐฑ์ค 2024. 9. 9. 17:35
์ ๊ทผ๋ฐฉ์
์ด๋ฒ ๋ฌธ์ ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ํ์๊ฐ3๊ณผ ๋น์ทํด๋ณด์ด์ง๋ง ๋ฐ๋ณต๋ฌธ์ ๋ฒ์๊ฐ ๋ค๋ฆ ๋๋ค.
๋ฐ๋ณต๋ฌธ์ ์ ๋ ฅ ํฌ๊ธฐ n์ ๋ํด ์ ํ์ ์ผ๋ก ์คํ๋๋๊ตฐ์.
MenOfPassion(A[], n) { sum <- 0; for i <- 1 to n for j <- 1 to n sum <- sum + A[i] × A[j]; # ์ฝ๋1 return sum; } --------------------------------------------------------- for(let i=0; i<n; i++) { for(let j=i+1; j<n; j++) { } }
์ฐ์ ๋ณด๊ธฐ ์ฝ๊ฒ javascript๋ก ๋ณํํด๋ณด์์ต๋๋ค.
์ธ๋ถ ๋ฐ๋ณต๋ฌธ๊ณผ ๋ด๋ถ ๋ฐ๋ณต๋ฌธ์ผ๋ก ๋๋ ์ ๋ณด๊ฒ ์ต๋๋ค.
์ธ๋ถ ๋ฐ๋ณต๋ฌธ
i๋ 0๋ถํฐ n-1๋ฒ๊น์ง ๋ฐ๋ณตํฉ๋๋ค.
์ด ๋ง์ ์ฆ, ์ฐ๋ฆฌ๊ฐ ์ ์๊ณ ์๋ฏ์ด n๋ฒ ๋ฐ๋ณต์ ์๋ฏธํฉ๋๋ค.
๋ด๋ถ ๋ฐ๋ณต๋ฌธ
j๋ i+1๋ถํฐ n-1๋ฒ๊น์ง ๋ฐ๋ณตํฉ๋๋ค.
i = 0 ์ผ ๋, j๋ 1๋ถํฐ n-1๋ฒ ๋ฐ๋ณตํฉ๋๋ค.
i = 1 ์ผ ๋, j๋ 2๋ถํฐ n-1๋ฒ ๋ฐ๋ณตํฉ๋๋ค.
i = n-1 ์ผ ๋๋ j = n ์ด๋ฏ๋ก n < n ์ด ์ฑ๋ฆฝ๋์ง ์์ ๋ฐ๋ณตํ์ง ๋ชปํฉ๋๋ค.
i = n-2 ์ผ ๋๋ j = n-1 ์ด๋ฏ๋ก ๋ฑ 1๋ฒ ์คํ๋ฉ๋๋ค.
๊ทธ๋ผ j ๋ฃจํ์์ ๋ฐ๋ณต๋๋ ํ์๋ ๋ฑ์ฐจ์์ด์ ํฉ์ ์ํด
ํญ์ ์ด๊ฐฏ์(์ฒซํญ + ๋ง์ง๋งํญ) / 2 ๋ฅผ ํด์ฃผ๊ฒ ๋๋ฉด
n ( n - 1 ) / 2 ๊ฐ ๋๋ฏ๋ก ์๊ฐ ๋ณต์ก๋๋ O(n^2)๊ฐ ๋ฉ๋๋ค.
ํน์ ๋ชจ๋ฅผ ์ฐธ์กฐ๊ธ์ ๋จ๊ฒจ๋๊ณ ํ์ด๋ฅผ ์งํํ๊ฒ ์ต๋๋ค.
์ฐธ์กฐ ๐ฌ
์ ์ธ๋ถ๋ ๊ณ์ฐํ์ง ์๊ณ ๋ด๋ถ๋ง ๊ณ์ฐํ์ฌ ํธ๋์ง?
์ธ๋ถ์ ๋ด๋ถ๋ฅผ ๊ฐ๊ฐ ๋ฐ๋ก ๊ณ์ฐํ๋ ๊ฒ์ด ์๋, ์ ์ฒด ๋ฐ๋ณต ํ์๋ฅผ ๊ณ์ฐํ ๋์๋
์ธ๋ถ ๋ฐ๋ณต๋ฌธ๊ณผ ๋ด๋ถ ๋ฐ๋ณต๋ฌธ์ ํจ๊ป ๊ณ ๋ คํ๋ ๊ฒ์ ๋๋ค.
๋ค๋ง, ์ธ๋ถ ๋ฐ๋ณต๋ฌธ์ ํญ์ n๋ฒ ๋ฐ๋ณต๋๋ ๊ณ ์ ๋ ๋ถ๋ถ์ด๊ธฐ ๋๋ฌธ์, ์ฃผ๋ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฒฐ์ ํ๋ ๊ฒ์
๋ด๋ถ ๋ฐ๋ณต๋ฌธ์ด ์ผ๋ง๋ ์์ฃผ ์คํ๋๋์ง์ ๋๋ค.
์ธ๋ถ ๋ฐ๋ณต๋ฌธ : for(let i=0; i<n; i++) ์ผ๋ก ํญ์ n๋ฒ ๋ฐ๋ณต๋ฉ๋๋ค.
๋ด๋ถ ๋ฐ๋ณต๋ฌธ : for(let j=i+1; i<n; j++) ์ผ๋ก ๊ฐ i์ ๋ํด ๋ฐ๋ณต ํ์๊ฐ ๋ฌ์ง๋ฉด์ ์์ ๊ณ์ฐํ๋ฏ์ด
n ( n - 1 ) / 2 ๋ฒ ๋ฐ๋ณต๋ฉ๋๋ค.
์ธ๋ถ ๋ฐ๋ณต๋ฌธ ์์ฒด๋ n๋ฒ ๋ฐ๋ณต๋์ง๋ง, ๋ด๋ถ ๋ฐ๋ณต์ ๊ฐ i๋ง๋ค ๋ค๋ฅธ ํ์๋ก ์คํํ๊ธฐ ๋๋ฌธ์
์ฃผ๋ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฒฐ์ ํ ๊ฒ์ ๋ด๋ถ ๋ฐ๋ณต๋ฌธ์ด ์ผ๋ง๋ ์์ฃผ ์คํ๋๋์ง ์ ๋๋ค.
ํ์ด โฐ
const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); let input = []; rl.on("line", function (line) { input.push(line); }).on("close", function () { // MenOfPassion(A[], n) { // sum <- 0; // for i <- 1 to n // for j <- 1 to n // sum <- sum + A[i] × A[j]; # ์ฝ๋1 // return sum; // } let n = Number(input[0]); n = (n * (n - 1)) / 2; console.log(n); console.log(2); });
๋ฐฑ์ค 24265๋ฒ ๋งํฌ
'๐ ์๊ณ ๋ฆฌ์ฆ > ๋ฐฑ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ