Swift Data Structure And Algorithm/Basic Loop 9

์ง์ˆ˜์˜ ํ•ฉ ๊ตฌํ•˜๊ธฐ

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ 1 ๋ถ€ํ„ฐ ์ฃผ์–ด์ง„ ์ˆซ์ž ์ค‘ 2๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋Š” ์ˆซ์ž๋“ค์˜ ํ•ฉ์„ ๊ตฌํ•จ. 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์ œ๊ณฑ๊ทผ ๊ตฌํ•˜๊ธฐ

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ 1๋ถ€ํ„ฐ ์ˆ˜๋ฅผ ์ฆ๊ฐ€ํ•˜๋ฉด์„œ ์ œ๊ณฑํ•œ ์ˆ˜๊ฐ€ N๋ณดํƒ€ ํฌ๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉด ๊ทธ ์ฆ‰์‹œ ๋ฉˆ์ถ”๊ณ  ๊ทธ ๋•Œ์˜ ์ˆ˜๊ฐ€ ์ œ๊ณฑ๊ทผ ์ค‘ ์ตœ์†Œ๊ฐ’ 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์•ฝ์ˆ˜ ๊ตฌํ•˜๊ธฐ

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์—ฌ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜๋„ ์žˆ์ง€๋งŒ, ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ํ•ด๊ฒฐํ•  ๊ฒฝ์šฐ 1 ์ˆซ์ž๋ฅผ ์ฆ๊ฐ€์‹œํ‚ค๋ฉด์„œ N์˜ ์•ฝ์ˆ˜์ธ์ง€ ํŒ๋ณ„ ํ›„ ์•ฝ์ˆ˜์ธ ๊ฒฝ์šฐ ์•ฝ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ ์ฆ๊ฐ€ ์‹œ์ผœ์ฃผ๊ณ , ๊ทธ ๊ฐœ์ˆ˜๊ฐ€ K์™€ ์ผ์น˜ ํ•˜๋Š” ์ˆœ๊ฐ„ ๊ทธ ๋•Œ์˜ ์ˆ˜๋ฅผ K๋ฒˆ์งธ ์•ฝ์ˆ˜๋กœ ๊ฒฐ์ •ํ•  ์ˆ˜ ์žˆ์Œ. ์ด ๋•Œ, ์•ฝ์ˆ˜์˜ ๊ฐœ์ˆ˜๊ฐ€ K๋ณด๋‹ค ์ž‘์„ ๊ฒฝ์šฐ๋Š” 0์„ ์ถœ๋ ฅํ•ด์•ผ ํ•จ. 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

์†Œ์ˆ˜ ํŒ๋ณ„

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ ์†Œ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์—ฌ๋Ÿฌ๊ฐ€์ง€๊ฐ€ ์žˆ์ง€๋งŒ, ํ•ด๋‹น ๋ฌธ์ œ๋Š” ํฌ๊ธฐ๊ฐ€ 20,000์ด๋ฏ€๋กœ O(N)์œผ๋กœ ํ•ด๊ฒฐํ•จ. 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋ฐฐ์ˆ˜์˜ ๊ฐœ์ˆ˜ ์„ธ๊ธฐ

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ A์™€ B์˜ ๋Œ€์†Œ ๊ด€๊ณ„๊ฐ€ ๋ฐ”๋€” ์ˆ˜ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— A๊ฐ€ ๋” ํด ๊ฒฝ์šฐ ๋‘ ์ˆ˜๋ฅผ ๊ตํ™˜ ํ›„ A๋ถ€ํ„ฐ B์ค‘ C์˜ ๋ฐฐ์ˆ˜๋ฅผ ์ฐพ์Œ. 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋ˆ ๋ชจ์œผ๊ธฐ

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ 1๋ถ€ํ„ฐ ์ˆซ์ž๋ฅผ ์ฆ๊ฐ€ํ•˜๋ฉด์„œ ๋ˆ„์ ํ•ฉ์„ ๊ธฐ๋กํ•จ, ๋ˆ„์ ํ•ฉ์ด M๊ณผ ๊ฐ™์•„์งˆ ๋•Œ ๊นŒ์ง€ ํ•„์š”ํ•œ ๋‚ ์งœ ์ˆ˜๋ฅผ ์ฆ๊ฐ€์‹œํ‚ด์œผ๋กœ์จ ํ•ด๋ฅผ ๊ตฌํ•จ. 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋”ํ•˜๊ธฐ ๋นผ๊ธฐ

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ 2๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋Š” ๊ฒฝ์šฐ ์ง์ˆ˜ ์ด๋ฏ€๋กœ ๋นผ๊ณ , ์•„๋‹Œ ๊ฒฝ์šฐ๋Š” ํ™€์ˆ˜ ์ด๋ฏ€๋กœ ๋”ํ•จ์œผ๋กœ์จ ํ•ด๋ฅผ ๊ตฌํ•จ. 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

N to M 2

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ N ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ์ถœ๋ ฅํ•˜๋Š” ์ˆ˜์˜ ๊ฐœ์ˆ˜๊ฐ€ 8๊ฐœ๊ฐ€ ๋˜๋ฉด "\n", ๊ฐœํ–‰ ๋ฌธ์ž๋ฅผ ์ถ”๊ฐ€ํ•˜์—ฌ ์ค„์„ ๋ฐ”๊ฟ” ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๊ณ  ์ด๋ฅผ M๊นŒ์ง€ ๋ฐ˜๋ณตํ•จ. 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

3์˜ ๋ฐฐ์ˆ˜

1. ๋ฌธ์ œ 2. ์ž…์ถœ๋ ฅ 3. ์ž…์ถœ๋ ฅ ์˜ˆ์‹œ 4. ๋ฌธ์ œ ์„ค๊ณ„ 3์œผ๋กœ ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋Š” ๊ฒฝ์šฐ 'X'๋ฅผ ์ถœ๋ ฅํ•จ 5. ์ „์ฒด ์ฝ”๋“œ ์ „์ฒด์ฝ”๋“œ๋Š” ์—ฌ๊ธฐ์—์„œ ํ™•์ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.