๋ชฉ๋ก์ „์ฒด ๊ธ€ (1005)

๐Ÿ˜Ž ๊ณต๋ถ€ํ•˜๋Š” ์ง•์ง•์•ŒํŒŒ์นด๋Š” ์ฒ˜์Œ์ด์ง€?

[BAEKJOON C++] 2609_์ตœ๋Œ€๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜

์ตœ๋Œ€๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜์˜ ๊ณฑ์€ ๋‘ ์ˆ˜์˜ ๊ณฑ๊ณผ ๊ฐ™์Œ ๋‘ ๊ฐœ์˜ ์ž์—ฐ์ˆ˜๋ฅผ ์ž…๋ ฅ๋ฐ›์•„ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ๋‘ ๊ฐœ์˜ ์ž์—ฐ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ๋‘˜์€ 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋ฉฐ ์‚ฌ์ด์— ํ•œ ์นธ์˜ ๊ณต๋ฐฑ์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋‘ ์ˆ˜์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋ฅผ, ๋‘˜์งธ ์ค„์—๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋‘ ์ˆ˜์˜ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. // [2609] ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ๊ณต๋ฐฐ์ˆ˜ /* ๋‘ ๊ฐœ์˜ ์ž์—ฐ์ˆ˜๋ฅผ ์ž…๋ ฅ๋ฐ›์•„ ์ตœ๋Œ€ ๊ณต์•ฝ์ˆ˜์™€ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ๋‘ ๊ฐœ์˜ ์ž์—ฐ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด ๋‘˜์€ 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋ฉฐ ์‚ฌ์ด์— ํ•œ ์นธ์˜ ๊ณต๋ฐฑ์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋‘ ์ˆ˜์˜ ์ตœ๋Œ€๊ณต์•ฝ์ˆ˜๋ฅผ, ๋‘˜์งธ ์ค„์—๋Š” ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ๋‘ ์ˆ˜์˜ ์ตœ์†Œ ๊ณต๋ฐฐ์ˆ˜๋ฅผ ์ถœ๋ ฅ..

[Coding Interview University] ์Šคํƒ : ์ด๋ก  ๋ฐ ๊ตฌํ˜„

๐Ÿซง ์Šคํƒ : ๋ฐ์ดํ„ฐ๋ฅผ ์Œ“์•„ ์˜ฌ๋ฆฐ๋‹ค : LIFO (Last In First Out) ์— ๋”ฐ๋ผ ์ž๋ฃŒ๋ฅผ ๋ฐฐ์—ดํ•œ๋‹ค : ๊ฐ€์žฅ ์ตœ๊ทผ์— ์Šคํƒ์— ์ถ”๊ฐ€ํ•œ ํ•ญ๋ชฉ์ด ๊ฐ€์žฅ ๋จผ์ € ์ œ๊ฑฐ๋  ํ•ญ๋ชฉ : ๋ฐฐ์—ด๊ณผ ๋‹ฌ๋ฆฌ ์Šคํƒ์€ ์ƒ์ˆ˜ ์‹œ๊ฐ„์— i ๋ฒˆ์งธ ํ•ญ๋ชฉ์— ์ ‘๊ทผํ•  ์ˆ˜ ์—†์Œ : ์Šคํƒ์—์„œ ๋ฐ์ดํ„ฐ๋ฅผ ์ถ”๊ฐ€ํ•˜๊ฑฐ๋‚˜ ์‚ญ์ œํ•˜๋Š” ์—ฐ์‚ฐ์€ ์ƒ์ˆ˜ ์‹œ๊ฐ„์— ๊ฐ€๋Šฅํ•˜๋‹ค ๐Ÿซง ์Šคํƒ์ด ์œ ์šฉํ•  ๊ฒฝ์šฐ : ์žฌ๊ท€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•  ๋•Œ ์œ ์šฉํ•จ : ์žฌ๊ท€์ ์œผ๋กœ ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•ด์•ผ ํ•˜๋Š” ๊ฒฝ์šฐ์— ์ž„์‹œ ๋ฐ์ดํ„ฐ๋ฅผ ์Šคํƒ์— ๋„ฃ์–ด ์ฃผ๊ณ , ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ๋น ์ ธ ๋‚˜์™€ ํ‡ด๊ฐ ๊ฒ€์ƒ‰(backtrack) ํ•  ๋•Œ๋Š” ์Šคํƒ์— ๋„ฃ์–ด ์ฃผ์—ˆ๋˜ ์ž„์‹œ ๋ฐ์ดํ„ฐ๋ฅผ ๋นผ ์ค˜์•ผ ํ•œ๋‹ค : ์ผ๋ จ์˜ ํ–‰์œ„๋ฅผ ์ง๊ด€์ ์œผ๋กœ ๊ฐ€๋Šฅํ•˜๊ฒŒ ํ•ด ์ค€๋‹ค : ์žฌ๊ท€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋ฐ˜๋ณต์  ํ˜•ํƒœ (iterative) ๋ฅผ ํ†ตํ•ด์„œ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•จ ๐Ÿซง ์Šคํƒ ๊ตฌํ˜„ํ•˜๊ธฐ funct..

[BAEKJOON C++] 2441_๋ณ„ ์ฐ๊ธฐ - 4

์ฒซ์งธ ์ค„์—๋Š” ๋ณ„ N๊ฐœ, ๋‘˜์งธ ์ค„์—๋Š” ๋ณ„ N-1๊ฐœ, ..., N๋ฒˆ์งธ ์ค„์—๋Š” ๋ณ„ 1๊ฐœ๋ฅผ ์ฐ๋Š” ๋ฌธ์ œ ํ•˜์ง€๋งŒ, ์˜ค๋ฅธ์ชฝ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ ๋ณ„(์˜ˆ์ œ ์ฐธ๊ณ )์„ ์ถœ๋ ฅ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์ฐจ๋ก€๋Œ€๋กœ ๋ณ„์„ ์ถœ๋ ฅํ•œ๋‹ค. // [2441] ๋ณ„ ์ฐ๊ธฐ - 4 /* ์ฒซ์งธ ์ค„์—๋Š” ๋ณ„ N๊ฐœ, ๋‘˜์งธ ์ค„์—๋Š” ๋ณ„ N-1๊ฐœ, ..., N๋ฒˆ์งธ ์ค„์—๋Š” ๋ณ„ 1๊ฐœ๋ฅผ ์ฐ๋Š” ๋ฌธ์ œ ํ•˜์ง€๋งŒ, ์˜ค๋ฅธ์ชฝ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ ๋ณ„(์˜ˆ์ œ ์ฐธ๊ณ )์„ ์ถœ๋ ฅ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์ฐจ๋ก€๋Œ€๋กœ ๋ณ„์„ ์ถœ๋ ฅํ•œ๋‹ค. */ // ํ‘œ์ค€ ์ŠคํŠธ๋ฆผ์—์„œ ์ฝ๊ธฐ ๋ฐ ์“ฐ๊ธฐ๋ฅผ ์ œ์–ดํ•˜๋Š” ๊ฐœ์ฒด๋ฅผ ์„ ์–ธ #include using namespace std; int main() { i..

[BAEKJOON C++] 2440_๋ณ„ ์ฐ๊ธฐ - 3

์ฒซ์งธ ์ค„์—๋Š” ๋ณ„ N๊ฐœ, ๋‘˜์งธ ์ค„์—๋Š” ๋ณ„ N-1๊ฐœ, ..., N๋ฒˆ์งธ ์ค„์—๋Š” ๋ณ„ 1๊ฐœ๋ฅผ ์ฐ๋Š” ๋ฌธ์ œ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์ฐจ๋ก€๋Œ€๋กœ ๋ณ„์„ ์ถœ๋ ฅํ•œ๋‹ค. // [2440] ๋ณ„ ์ฐ๊ธฐ - 3 /* ์ฒซ์งธ ์ค„์—๋Š” ๋ณ„ N๊ฐœ, ๋‘˜์งธ ์ค„์—๋Š” ๋ณ„ N-1๊ฐœ, ..., N๋ฒˆ์งธ ์ค„์—๋Š” ๋ณ„ 1๊ฐœ๋ฅผ ์ฐ๋Š” ๋ฌธ์ œ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์ฐจ๋ก€๋Œ€๋กœ ๋ณ„์„ ์ถœ๋ ฅํ•œ๋‹ค. */ // ํ‘œ์ค€ ์ŠคํŠธ๋ฆผ์—์„œ ์ฝ๊ธฐ ๋ฐ ์“ฐ๊ธฐ๋ฅผ ์ œ์–ดํ•˜๋Š” ๊ฐœ์ฒด๋ฅผ ์„ ์–ธ #include using namespace std; int main() { int n = 0; cin >> n; for (int i = 0; i < n; i++) { for (int j = 0..

[BAEKJOON C++] 2439_๋ณ„ ์ฐ๊ธฐ - 2

์ฒซ์งธ ์ค„์—๋Š” ๋ณ„ 1๊ฐœ, ๋‘˜์งธ ์ค„์—๋Š” ๋ณ„ 2๊ฐœ, N๋ฒˆ์งธ ์ค„์—๋Š” ๋ณ„ N๊ฐœ๋ฅผ ์ฐ๋Š” ๋ฌธ์ œ ํ•˜์ง€๋งŒ, ์˜ค๋ฅธ์ชฝ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ ๋ณ„(์˜ˆ์ œ ์ฐธ๊ณ )์„ ์ถœ๋ ฅ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์ฐจ๋ก€๋Œ€๋กœ ๋ณ„์„ ์ถœ๋ ฅํ•œ๋‹ค. // [2439] ๋ณ„ ์ฐ๊ธฐ - 2 /* ์ฒซ์งธ ์ค„์—๋Š” ๋ณ„ 1๊ฐœ, ๋‘˜์งธ ์ค„์—๋Š” ๋ณ„ 2๊ฐœ, N๋ฒˆ์งธ ์ค„์—๋Š” ๋ณ„ N๊ฐœ๋ฅผ ์ฐ๋Š” ๋ฌธ์ œ ํ•˜์ง€๋งŒ, ์˜ค๋ฅธ์ชฝ์„ ๊ธฐ์ค€์œผ๋กœ ์ •๋ ฌํ•œ ๋ณ„(์˜ˆ์ œ ์ฐธ๊ณ )์„ ์ถœ๋ ฅ ์ž…๋ ฅ ์ฒซ์งธ ์ค„์— N(1 ≤ N ≤ 100)์ด ์ฃผ์–ด์ง„๋‹ค. ์ถœ๋ ฅ ์ฒซ์งธ ์ค„๋ถ€ํ„ฐ N๋ฒˆ์งธ ์ค„๊นŒ์ง€ ์ฐจ๋ก€๋Œ€๋กœ ๋ณ„์„ ์ถœ๋ ฅํ•œ๋‹ค. */ // ํ‘œ์ค€ ์ŠคํŠธ๋ฆผ์—์„œ ์ฝ๊ธฐ ๋ฐ ์“ฐ๊ธฐ๋ฅผ ์ œ์–ดํ•˜๋Š” ๊ฐœ์ฒด๋ฅผ ์„ ์–ธ #include using namespace std; int main() { int n = 0; cin ..