ํ‹ฐ์Šคํ† ๋ฆฌ

๐Ÿ’ซ Vivid Tech Blog ๐Ÿง‘‍๐Ÿ’ป
๊ฒ€์ƒ‰ํ•˜๊ธฐ

๋ธ”๋กœ๊ทธ ํ™ˆ

๐Ÿ’ซ Vivid Tech Blog ๐Ÿง‘‍๐Ÿ’ป

vividswan.tistory.com/m

์›น ๊ฐœ๋ฐœ์ž๐Ÿ’Ž

๊ตฌ๋…์ž
14
๋ฐฉ๋ช…๋ก ๋ฐฉ๋ฌธํ•˜๊ธฐ
๊ณต์ง€ ๋ธ”๋กœ๊ทธ ์ด์ „ ์™„๋ฃŒ ๋ชจ๋‘๋ณด๊ธฐ

์ฃผ์š” ๊ธ€ ๋ชฉ๋ก

  • [BOJ] ๋ณด์„ ์ค๊ธฐ(2001) [๋ฐฑ์ค€(BOJ)] 2001_๋ณด์„ ์ค๊ธฐ JAVA ๋ฌธ์ œ : BOJ_2001๋ฒˆ ๋ณด์„ ์ค๊ธฐ ๋ฌธ์ œ ์„ค๋ช… ์ตœ๋Œ€ 100๊ฐœ์˜ ์„ฌ์ด ์žˆ๊ณ  ๊ฐ ์„ฌ๋งˆ๋‹ค ์ตœ๋Œ€ ํ•œ ๊ฐ€์ง€์˜ ์–‘๋ฐฉํ–ฅ ๋‹ค๋ฆฌ๋กœ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฐ ์„ฌ๋งˆ๋‹ค ๋ณด์„์ด ์žˆ๋Š” ์„ฌ๊ณผ ์—†๋Š” ์„ฌ์ด ์žˆ๊ณ , ๋‹ค๋ฆฌ๋งˆ๋‹ค ๋ณด์„์„ ๊ฒฌ๋”œ ์ˆ˜ ์žˆ๋Š” ์ˆ˜๊ฐ€ ์ •ํ•ด์ ธ์žˆ์Šต๋‹ˆ๋‹ค. 1๋ฒˆ ์„ฌ์—์„œ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ 1๋ฒˆ ์„ฌ์œผ๋กœ ๋‹ค์‹œ ๋Œ์•„์™€์•ผ ํ•˜๋Š”๋ฐ, ์ด๋•Œ ์ตœ๋Œ€ํ•œ ๋ชจ์„ ์ˆ˜ ์žˆ๋Š” ๋ณด์„์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋ฐฉ๋ฌธํ–ˆ๋˜ ๋‹ค๋ฆฌ์™€ ์„ฌ์€ ๋‹ค์‹œ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ๊ณ  ์„ฌ์— ์žˆ๋Š” ๋ณด์„์„ ๊ฐ€์ ธ๊ฐ€๊ฑฐ๋‚˜ ๊ฐ€์ ธ๊ฐ€์ง€ ์•Š์„ ์ˆ˜๋„ ์žˆ์Šต๋‹ˆ๋‹ค. Solution ๋น„ํŠธ ๋งˆ์Šคํ‚น & bfs ๊ฐ ์„ฌ์„ ์ง€๋‚˜๊ฐˆ ๋•Œ ๋ช‡ ๊ฐœ์˜ ๋ณด์„์„ ๋“ค๊ณ  ์žˆ์–ด์•ผ ํ•˜๋Š”์ง€, ๋˜ ํ•ด๋‹น ์„ฌ์—์„œ ๋ณด์„์„ ๊ฐ€์ ธ๊ฐ€๋Š” ๊ฒŒ ์œ ๋ฆฌํ•œ์ง€ ์•„๋‹Œ์ง€๋ฅผ ์•Œ ์ˆ˜ ์—†๊ธฐ ๋•Œ๋ฌธ์— ๋ชจ๋“  ํƒ์ƒ‰์ด ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ์œ„ํ•ด ๋น„ํŠธ ๋งˆ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 17.
  • [BOJ] LCS 2(9252) [๋ฐฑ์ค€(BOJ)] 9252_LCS 2 JAVA ๋ฌธ์ œ : BOJ_9252๋ฒˆ LCS 2 ๋ฌธ์ œ ์„ค๋ช… ๋‘ ๊ฐœ์˜ ๋ฌธ์ž์—ด์ด ์žˆ๊ณ , ๊ทธ ๋ฌธ์ž์—ด์˜ ๊ณตํ†ต๋ถ€๋ถ„ ์ˆ˜์—ด ์ค‘ ๊ฐ€์žฅ ๊ธด ์ˆ˜์—ด์„ ์ฐพ๋Š” ๊ฒƒ์ด๋‹ค. ๊ธฐ์กด์˜ LCS ๋ฌธ์ œ์™€ ๋‹ค๋ฅธ ์ ์€ ์ˆ˜์—ด์˜ ๊ธธ์ด๋ฟ๋งŒ ์•„๋‹ˆ๋ผ ์ˆ˜์—ด์ด ์–ด๋–ค ๋ฌธ์ž์—ด์ธ์ง€ ์ถœ๋ ฅํ•ด์•ผ ํ•œ๋‹ค. Solution DP dp[i][j] = ์ฒซ ๋ฒˆ์งธ ๋ฌธ์ž์—ด์˜ ์ธ๋ฑ์Šค๊ฐ€ i, ๋‘ ๋ฒˆ์งธ ๋ฌธ์ž์—ด์˜ ์ธ๋ฑ์Šค๊ฐ€ j ์ผ ๋•Œ ๊ณตํ†ต๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ์ตœ๋Œ“๊ฐ’ ์ด๋ผ๊ณ  ์ •์˜ํ•˜์ž. ์ฒซ ๋ฒˆ์งธ ๋ฌธ์ž์—ด์˜ i ๋ฒˆ์งธ ๋ฌธ์ž์™€ ๋‘ ๋ฒˆ์งธ ๋ฌธ์ž์—ด์˜ j ๋ฒˆ์งธ ๋ฌธ์ž๊ฐ€ ๊ฐ™๋‹ค๋ฉด, dp[i][j] = dp[i-1][j-1] + 1๋กœ dp ๊ฐ’์„ ํ• ๋‹นํ•œ๋‹ค. i์™€ j์˜ ์ด์ „ ํ•˜๋‚˜ ์ด์ „ ์ธ๋ฑ์Šค์˜ dp ๊ฐ’์—์„œ ๋‘ ๋ฌธ์ž๊ฐ€ ๊ฐ™๋‹ค๋ฉด ๊ณตํ†ต๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ๊ธธ์ด๊ฐ€ ๋Š˜์–ด๋‚˜๋ฏ€๋กœ 1์„ ๋”ํ•ด์ฃผ๋Š” ์‹์ด๋‹ค. ์ฒซ ๋ฒˆ์งธ ๋ฌธ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 16.
  • [Programmers] ์ง€ํ˜• ์ด๋™ [Programmers] ์ง€ํ˜• ์ด๋™ JAVA ๋ฌธ์ œ : ์ง€ํ˜• ์ด๋™ ๋ฌธ์ œ ์„ค๋ช… N * N ํฌ๊ธฐ์˜ ์ง€ํ˜•์ด ์žˆ๊ณ  ์ง€ํ˜•๋งˆ๋‹ค ๊ฐ๊ฐ์˜ ๋†’์ด๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ง€ํ˜•์˜ ๋†’์ด์ฐจ๊ฐ€ ์ •ํ•ด์ง„ ๊ฐ’ ์ดํ•˜์ด๋ฉด ์ž์œ ๋กญ๊ฒŒ ์ด๋™ํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ์ •ํ•ด์ง„ ๊ฐ’ ๋ณด๋‹ค ์ฐจ์ด๊ฐ€ ๋†’์œผ๋ฉด ์‚ฌ๋‹ค๋ฆฌ๋ฅผ ์„ค์น˜ํ•ด์•ผ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ์‚ฌ๋‹ค๋ฆฌ์˜ ๋†’์ด๋Š” ์ธ์ ‘ํ•œ ์ง€ํ˜•์˜ ๋†’์ด ์ฐจ์ด๊ณ , ์‚ฌ๋‹ค๋ฆฌ์˜ ์ˆ˜๋Š” ์ œํ•œ์ด ์—†์ง€๋งŒ ์‚ฌ๋‹ค๋ฆฌ๋“ค์˜ ๋†’์ดํ•ฉ์ด ์ตœ์†Œํ•œ์ด ๋˜๋„๋ก ์„ค์น˜ํ•˜์—ฌ ๋ชจ๋“  ์ง€ํ˜•๋ผ๋ฆฌ ์—ฐ๊ฒฐ๋˜๊ฒŒ ํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution bfs, ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์šฐ์„  bfs๋กœ ์„œ๋กœ ์‚ฌ๋‹ค๋ฆฌ ์—†์ด ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์ง€ํ˜•๋“ค์„ ๊ตฌ๋ณ„ํ•ด ์ฃผ๊ณ  ๊ฐ๊ฐ ๋ฒˆํ˜ธ(์‚ฌ๋‹ค๋ฆฌ ์—†์ด ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์ง€์—ญ๋ณ„ ๋ฒˆํ˜ธ)๋ฅผ ํ• ๋‹นํ•ด ์ค๋‹ˆ๋‹ค. ์ด๋•Œ ์ธ์ ‘ํ•œ ์ง€ํ˜•์˜ ๋†’์ด์ฐจ๊ฐ€ ์ฃผ์–ด์ง„ ๊ฐ’ ๋ณด๋‹ค ์ปค์„œ ์ด๋™์„ ๋ชปํ•˜๋Š” ์ง€ํ˜•์—์„œ๋Š” ํฌ๋ฃจ์Šค์นผ .. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 16.
  • [Programmers] ๋ธ”๋ก ์ด๋™ํ•˜๊ธฐ(2020 KAKAO BLIND RECRUITMENT) [Programmers] ๋ธ”๋ก ์ด๋™ํ•˜๊ธฐ(2020 KAKAO BLIND RECRUITMENT) JAVA ๋ฌธ์ œ : ๋ธ”๋ก ์ด๋™ํ•˜๊ธฐ(2020 KAKAO BLIND RECRUITMENT) ๋ฌธ์ œ ์„ค๋ช… 1*2 ํฌ๊ธฐ์˜ ๋“œ๋ก (2*1๋กœ ํšŒ์ „์ด ๊ฐ€๋Šฅํ•˜๋‹ค.)์ด ์ง€๋„์—์„œ ๋ง‰ํžˆ์ง€ ์•Š์€ ๊ณณ์„ ํ†ตํ•ด ์›€์ง์ผ ๋•Œ, n*n ์นธ(์˜ค๋ฅธ์ชฝ ์•„๋ž˜ ๋งˆ์ง€๋ง‰ ์นธ)์œผ๋กœ ๊ฐ€๋Š” ์ตœ์†Œํ•œ์˜ ์›€์ง์ž„์„ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋“œ๋ก ์€ ์ƒ, ํ•˜, ์ขŒ, ์šฐ๋กœ ์›€์ง์ผ ์ˆ˜ ์žˆ๊ณ  ๊ฐ€๋กœ์—์„œ ์„ธ๋กœ๋กœ, ์„ธ๋กœ์—์„œ ๊ฐ€๋กœ๋กœ ํšŒ์ „ํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ, ํšŒ์ „ํ•  ๋•Œ ๋‹ฟ๋Š” ์ง€๋„๊ฐ€ ๋ง‰ํ˜€์žˆ์œผ๋ฉด ํšŒ์ „์ด ์•ˆ ๋ฉ๋‹ˆ๋‹ค.(์ž์„ธํ•œ ๊ฑด ๊ทธ๋ฆผ์œผ๋กœ ๋‚˜์™€์žˆ์Šต๋‹ˆ๋‹ค.) Solution bfs bfs๋กœ ๋“œ๋ก ์ด ํ•œ ์นธ์”ฉ ์›€์ง์ผ ๋•Œ๋งˆ๋‹ค ๋ฐฉ๋ฌธํ•œ ๊ฑฐ๋ฆฌ๋ฅผ 1์”ฉ ๋”ํ•ด์ฃผ๋ฉฐ ์ตœ์ข… n*n์— ๋‹ฟ์•˜์„ ๋•Œ ์ตœ์ข… ๊ฐ’์„ ์ถœ๋ ฅํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. ๋‹ค๋งŒ ๋‹จ์ˆœํ•˜.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 16.
  • [BOJ] ๊ฒฝ์Ÿ์  ์ „์—ผ(18405) [๋ฐฑ์ค€(BOJ)] 18405_๊ฒฝ์Ÿ์  ์ „์—ผ JAVA ๋ฌธ์ œ : BOJ_18405๋ฒˆ ๊ฒฝ์Ÿ์  ์ „์—ผ ๋ฌธ์ œ ์„ค๋ช… NxN ํฌ๊ธฐ์˜ ์‹œํ—˜๊ด€์—์„œ ๋ฐ”์ด๋Ÿฌ์Šค๊ฐ€ ๋งค์ดˆ ์ƒํ•˜์ขŒ์šฐ๋กœ ์ฆ์‹ํ•œ๋‹ค. ์ด๋•Œ ๋ฐ”์ด๋Ÿฌ์Šค๋Š” ๊ธฐ์กด์˜ ๋ฐ”์ด๋Ÿฌ์Šค๊ฐ€ ์žˆ๋Š” ์ž๋ฆฌ์—” ์ฆ์‹ํ•  ์ˆ˜ ์—†์œผ๋ฉฐ ๋ฐ”์ด๋Ÿฌ์Šค๋งˆ๋‹ค ์ฆ์‹ํ•˜๋Š” ์šฐ์„ ์ˆœ์œ„ ๋ฒˆํ˜ธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ฃผ์–ด์ง€๋Š” ์‹œ๊ฐ„(s)์— ์ฃผ์–ด์ง€๋Š” ์žฅ์†Œ(x,y)์— ์–ด๋–ค ๋ฐ”์ด๋Ÿฌ์Šค๊ฐ€ ์žˆ๋Š”์ง€ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ด๋‹ค. Solution bfs bfs๋ฅผ ์ด์šฉํ•ด์„œ ๋ฐ”์ด๋Ÿฌ์Šค๊ฐ€ ์ƒํ•˜์ขŒ์šฐ๋กœ ์ฆ์‹ํ•  ๋•Œ ์ž๋ฃŒ๊ตฌ์กฐ์— ๋„ฃ์–ด์ง€๋Š” ์‹์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ๋‹ค. ๋‹ค๋งŒ, ๋ฐ”์ด๋Ÿฌ์Šค๊ฐ€ ์ฆ์‹ํ•˜๋Š” ์šฐ์„ ์ˆœ์œ„ ๋ฒˆํ˜ธ๊ฐ€ ์žˆ๊ธฐ ๋•Œ๋ฌธ์— ๋‹จ์ˆœํ•œ queue ๊ตฌ์กฐ๋กœ๋Š” ํ•ด๊ฒฐํ•  ์ˆ˜ ์—†๋‹ค. ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์ด ์žˆ์ง€๋งŒ temp list๋ฅผ ์„ ์–ธํ•ด์„œ ์ƒˆ๋กœ ์ƒ์„ฑ๋˜๋Š” ๋ฐ”์ด๋Ÿฌ์Šค๋“ค์„ ๋„ฃ์–ด์ค€ ๋’ค, ํ•œ ๋ฒˆ์˜ ๋ฐ”์ด๋Ÿฌ์Šค ์ฆ์‹์ด ๋๋‚œ ๋’ค์— ๊ธฐ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 16.
  • [BOJ] ์น˜ํ‚จ ๋ฐฐ๋‹ฌ(15686) [๋ฐฑ์ค€(BOJ)] 15686_์น˜ํ‚จ ๋ฐฐ๋‹ฌ JAVA ๋ฌธ์ œ : BOJ_15686๋ฒˆ ์น˜ํ‚จ ๋ฐฐ๋‹ฌ ๋ฌธ์ œ ์„ค๋ช… N*N ํฌ๊ธฐ์˜ map์—์„œ ์ง‘๊ณผ ์น˜ํ‚จ์ง‘์ด ์ฃผ์–ด์ง„๋‹ค. ์ตœ๋Œ€ m ๊ฐœ์˜ ์น˜ํ‚จ์ง‘์„ ์ œ์™ธํ•œ ๋‚˜๋จธ์ง€ ์น˜ํ‚จ์ง‘์„ ๋‹ค ์—†์• ์•ผ ํ•œ๋‹ค. ์ด๋•Œ ์ง‘๊ณผ ์น˜ํ‚จ์ง‘๊ณผ์˜ ์ตœ์†Œ ๊ฑฐ๋ฆฌ(์ˆ˜์ง๊ฑฐ๋ฆฌ์˜ ์ฐจ + ์ˆ˜ํ‰๊ฑฐ๋ฆฌ์˜ ์ฐจ)์˜ ํ•ฉ์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•ด์•ผ ํ•œ๋‹ค. Solution ์™„์ „ ํƒ์ƒ‰(์กฐํ•ฉ) N์˜ ์ตœ๋Œ€ ํฌ๊ธฐ๋Š” 50, M์˜ ์ตœ๋Œ€ ํฌ๊ธฐ๋Š” 13์ด๋‹ค. 13๊ฐœ์˜ ์น˜ํ‚จ์ง‘์—์„œ 7๊ฐœ์˜ ์น˜ํ‚จ์ง‘์„ ์„ ํƒํ•˜๋Š” ์กฐํ•ฉ์˜ ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ํฌ๋ฏ€๋กœ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ณ„์‚ฐํ•ด๋ณด๋ฉด, 50 * 50(๋„์‹œ์˜ ์ตœ๋Œ€ ํฌ๊ธฐ) * 13C7 * 7(๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋งˆ๋‹ค 7๊ฐœ์˜ ์น˜ํ‚จ์ง‘๊ณผ ๊ฑฐ๋ฆฌ๋ฅผ ํ™•์ธํ•ด๋ด„) == 30,030,000 ์ด๋ฏ€๋กœ ์กฐํ•ฉ์„ ์ด์šฉํ•œ ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ•ด๊ฒฐ์ด ๊ฐ€๋Šฅํ•˜๋‹ค. Description ์กฐํ•ฉ์€ rec.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 16.
  • [BOJ] ์•„๊ธฐ ์ƒ์–ด(16236) [๋ฐฑ์ค€(BOJ)] 16236_์•„๊ธฐ ์ƒ์–ด JAVA ๋ฌธ์ œ : BOJ_16236๋ฒˆ ์•„๊ธฐ ์ƒ์–ด ๋ฌธ์ œ ์„ค๋ช… ์•„๊ธฐ ์ƒ์–ด๊ฐ€ ์ƒํ•˜์ขŒ์šฐ๋กœ ์›€์ง์ด๋ฉด์„œ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ๋ฌผ๊ณ ๊ธฐ๋Š” ์•„๊ธฐ ์ƒ์–ด์˜ ํฌ๊ธฐ๋ณด๋‹ค ์ž‘์€ ๋ฌผ๊ณ ๊ธฐ๋งŒ ๋จน์„ ์ˆ˜ ์žˆ๊ณ , ์ƒ์–ด์˜ ํฌ๊ธฐ๋ณด๋‹ค ํฐ ๋ฌผ๊ณ ๊ธฐ๊ฐ€ ์žˆ๋Š” ๊ณณ์€ ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๊ฑฐ๋ฆฌ์— ์žˆ๋Š” ๋จน์„ ์ˆ˜ ์žˆ๋Š” ๋ฌผ๊ณ ๊ธฐ๋ถ€ํ„ฐ ๋จน๋Š”๋ฐ, ๊ฐ™์€ ๊ฑฐ๋ฆฌ์— ์žˆ๋Š” ๋ฌผ๊ณ ๊ธฐ๊ฐ€ ์—ฌ๋Ÿฌ ๋ฌผ๊ณ ๊ธฐ๋ผ๋ฉด ์œ„ ๋‹ค์Œ ์™ผ์ชฝ์— ์žˆ๋Š” ๋ฌผ๊ณ ๊ธฐ๋ถ€ํ„ฐ ๋จน์Šต๋‹ˆ๋‹ค. ๋˜ ํ•œ ์ž๊ธฐ์˜ ๋ชธ ํฌ๊ธฐ ์ˆ˜๋งŒํผ์˜ ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน์œผ๋ฉด ๋ชธ์˜ ํฌ๊ธฐ๊ฐ€ 1 ์ฆ๊ฐ€ํ•ฉ๋‹ˆ๋‹ค. ์ด๋Ÿฌํ•œ ์กฐ๊ฑด์—์„œ ๋ฌผ๊ณ ๊ธฐ๊ฐ€ ํ•œ ๋ฒˆ ์ด๋™ํ•˜๋Š” ์‹œ๊ฐ„์„ 1์ดˆ๋ผ๊ณ  ํ•  ๋•Œ ๋ฌผ๊ณ ๊ธฐ๊ฐ€ ๋จน์„ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๋ฌผ๊ณ ๊ธฐ๋ฅผ ๋จน๋Š”๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„์„ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution bfs, ์™„์ „ ํƒ์ƒ‰ ์šฐ์„  bfs๋กœ ์ƒ์–ด์˜ ์œ„์น˜๋ถ€ํ„ฐ ์‹œ์ž‘.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 15.
  • [BOJ] ํ–‰์„ฑ ํ„ฐ๋„(2887) [๋ฐฑ์ค€(BOJ)] 2887_ํ–‰์„ฑ ํ„ฐ๋„ JAVA ๋ฌธ์ œ : BOJ_2887๋ฒˆ ํ–‰์„ฑ ํ„ฐ๋„ ๋ฌธ์ œ ์„ค๋ช… 3๊ฐœ์˜ ์ขŒํ‘œ (x,y,z)๋กœ ๋œ N ๊ฐœ์˜ ํ–‰์„ฑ์ด ์žˆ์Šต๋‹ˆ๋‹ค. ๋‘ ํ–‰์„ฑ์„ ์—ฐ๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ๋น„์šฉ์€ ํ–‰์„ฑ์˜ ๊ฐ ์ขŒํ‘œ์˜ ์ฐจ ์ค‘ ์ตœ์†Ÿ๊ฐ’์ด๋ผ๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ๋ชจ๋“  ํ–‰์„ฑ์„ ํ„ฐ๋„๋กœ ์—ฐ๊ฒฐํ•  ๋•Œ ์ตœ์†Œ ๋น„์šฉ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ์—ฐ๊ฒฐํ•˜๋Š” ์ตœ์†Œ ๋น„์šฉ์˜ ํ„ฐ๋„์„ ๊ตฌํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ฃผ์–ด์ง„ ํ„ฐ๋„์ด ์—†๊ธฐ ๋•Œ๋ฌธ์— ํ„ฐ๋„๋“ค์„ ๋น„๊ตํ•˜๋ฉด์„œ ์ตœ์†Ÿ๊ฐ’์˜ ํ„ฐ๋„์„ ์ฐพ์•„์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ํ–‰์„ฑ์˜ ๊ฐœ์ˆ˜๋Š” ์ตœ๋Œ€ 100,000์ด ์ฃผ์–ด์ง€๋ฏ€๋กœ, ๋ชจ๋“  ํ–‰์„ฑ์„ ์„œ๋กœ ๋น„๊ตํ•ด ์ค€๋‹ค๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•ฉ๋‹ˆ๋‹ค. ์ž˜ ์ƒ๊ฐํ•ด ๋ณด๋ฉด ํ–‰์„ฑ ๊ฐ„์˜ ์ตœ์†Ÿ๊ฐ’์€ ํ•ญ์ƒ x, y, z ๊ฐ’์˜ ์ฐจ์˜ ์ตœ์†Ÿ๊ฐ’ ์ค‘ ํ•˜๋‚˜์ด๊ธฐ ๋•Œ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 15.
  • [Programmers] ์ž๋ฌผ์‡ ์™€ ์—ด์‡ (2020 KAKAO BLIND RECRUITMENT) [Programmers] ๊ธฐ๋‘ฅ๊ณผ ๋ณด ์„ค์น˜(2020 KAKAO BLIND RECRUITMENT) JAVA ๋ฌธ์ œ : ๊ธฐ๋‘ฅ๊ณผ ๋ณด ์„ค์น˜(2020 KAKAO BLIND RECRUITMENT) ๋ฌธ์ œ ์„ค๋ช… N*N์˜ ๋ฒฝ๋ฉด์ด ์ฃผ์–ด์ง€๊ณ  ์ด ๋ฒฝ๋ฉด์— ๊ธฐ๋‘ฅ๊ณผ ๋ณด๋ฅผ ์„ค์น˜, ์‚ญ์ œํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๊ธฐ๋‘ฅ์€ ๋‹ค๋ฅธ ๊ธฐ๋‘ฅ์˜ ์œ„, ํ˜น์€ ๋ณด์˜ ์–‘ ๋ ์ชฝ์— ์„ค์น˜๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ณด๋Š” ์–‘ ๋ ์  ์ค‘ ํ•œ์ ์— ๊ธฐ๋‘ฅ์ด ์žˆ๊ฑฐ๋‚˜, ์–‘ ๋ ์ ์— ๋ณด๊ฐ€ ์„ค์น˜๋˜์–ด ์žˆ์„ ์‹œ ์„ค์น˜๋  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ž…๋ ฅ์œผ๋กœ ์›ํ•˜๋Š” ๊ธฐ๋‘ฅ๊ณผ ๋ณด์˜ ์„ค์น˜, ์‚ญ์ œ ์œ ๋ฌด์™€ ์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ์ถœ๋ ฅ์œผ๋กœ ์„ค์น˜, ์‚ญ์ œ๊ฐ€ ๊ฐ€๋Šฅํ•  ๋•Œ ์‹คํ–‰ํ•œ ๋’ค์˜ ์ตœ์ข… ๊ฒฐ๊ณผ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๊ฒƒ์ด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ๊ตฌํ˜„, ์™„์ „ ํƒ์ƒ‰ ์ž…๋ ฅ๊ฐ’์„ ๋ฐ›์€ ๋’ค, ์ด ์ž…๋ ฅ๊ฐ’์„ ์ตœ์ข… ๋ฐฐ์—ด์— ์‚ฝ์ž…ํ•ฉ๋‹ˆ๋‹ค. ๊ทธ ํ›„ ์‚ฝ์ž…ํ•œ ๊ฒฐ๊ณผ(์‚ญ์ œ๋‚˜ ์„ค.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 15.
  • [BOJ] ๋ฑ€(3190) [๋ฐฑ์ค€(BOJ)] 3190_๋ฑ€ JAVA ๋ฌธ์ œ : BOJ_3190๋ฒˆ ๋ฑ€ ๋ฌธ์ œ ์„ค๋ช… ๋งค์ดˆ ์›€์ง์ด๋ฉด์„œ ๊ผฌ๋ฆฌ๋ฅผ ๋Š˜๋ ค๊ฐ€๋Š” ๋ฑ€ ๊ฒŒ์ž„์„ ๊ตฌํ˜„ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. N*N ํฌ๊ธฐ์˜ ๋งต์ด ์ฃผ์–ด์ง€๊ณ , ์‚ฌ๊ณผ๊ฐ€ ์žˆ๋Š” ๊ฐ๊ฐ์˜ ์œ„์น˜์™€ ๋ฑ€์ด ๋ฐฉํ–ฅ์„ ๋ฐ”๊พธ๋Š” ์ˆœ๊ฐ„์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์ด๋•Œ ๋ฑ€์ด ์›€์ง์ธ ๋ฐฉํ–ฅ์— ์‚ฌ๊ณผ๊ฐ€ ์žˆ๋‹ค๋ฉด ์‚ฌ๊ณผ๋ฅผ ๋จน๊ณ  ๊ผฌ๋ฆฌ๊ฐ€ ๋Š˜์–ด๋‚˜์ง€๋งŒ, ์‚ฌ๊ณผ๊ฐ€ ์—†๋‹ค๋ฉด ๊ธฐ์กด์˜ ๊ผฌ๋ฆฌ ๋ถ€๋ถ„์ด ์‚ฌ๋ผ์ง€๊ณ  ๋ฑ€์˜ ๋จธ๋ฆฌ ๋ถ€๋ถ„์ด ๋Š˜์–ด๋‚ฉ๋‹ˆ๋‹ค. ๋˜ํ•œ ๋ฐฉํ–ฅ์€ ์ตœ์ดˆ์— ์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ด๋™ํ•˜๋ฉฐ ์ด๋™๋ฐฉํ–ฅ์„ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฅธ์ชฝ์ด๋‚˜ ์™ผ์ชฝ์œผ๋กœ 90๋„ ํšŒ์ „ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. Solution ๊ตฌํ˜„ ๋ฌธ์ œ์—์„œ ์ฃผ์–ด์ง„ ๋Œ€๋กœ ๊ตฌํ˜„์„ ํ•˜๋ฉด ๋ฉ๋‹ˆ๋‹ค. ๋ฑ€์˜ ํ˜„์žฌ ๋จธ๋ฆฌ ์œ„์น˜์™€ ๊ผฌ๋ฆฌ ์œ„์น˜๋ฅผ ๊ณ„์† ๊ธฐ๋กํ•ด ์ฃผ๋ฉด์„œ, ์ด๋™ํ•œ ๊ณณ์— ์‚ฌ๊ณผ๊ฐ€ ์žˆ์œผ๋ฉด ๋จธ๋ฆฌ ์œ„์น˜๋งŒ ์ˆ˜์ •ํ•ด ์ฃผ๊ณ , ์‚ฌ๊ณผ๊ฐ€ ์—†์„ ์‹œ์—” ๊ผฌ๋ฆฌ ์œ„์น˜๋„ ํ•จ๊ป˜ ์ˆ˜์ •ํ•ด .. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 15.
  • [Programmers] ์ž๋ฌผ์‡ ์™€ ์—ด์‡ (2020 KAKAO BLIND RECRUITMENT) [Programmers] ์ž๋ฌผ์‡ ์™€ ์—ด์‡ (2020 KAKAO BLIND RECRUITMENT) JAVA ๋ฌธ์ œ : ์ž๋ฌผ์‡ ์™€ ์—ด์‡ (2020 KAKAO BLIND RECRUITMENT) ๋ฌธ์ œ ์„ค๋ช… ํฌ๊ธฐ๊ฐ€ N*N์ธ ์ž๋ฌผ์‡ ์™€ ํฌ๊ธฐ๊ฐ€ M*M์ธ ์—ด์‡ ๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์ž๋ฌผ์‡ ์™€ ์—ด์‡ ๋Š” ๊ฐ๊ฐ ํ™ˆ์ธ ๋ถ€๋ถ„๊ณผ ๋Œ๊ธฐ์ธ ๋ถ€๋ถ„์ด ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ์ž๋ฌผ์‡ ๋ณด๋‹ค ํฌ๊ธฐ๊ฐ€ ํ•ญ์ƒ ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์—ด์‡ ๋ฅผ 90๋„์”ฉ ํšŒ์ „ํ•˜๊ฑฐ๋‚˜ ์ด๋™์‹œ์ผœ์„œ ์ž๋ฌผ์‡ ์™€ ์—ด์‡  ์„œ๋กœ์˜ ํ™ˆ๊ณผ ๋Œ๊ธฐ ๋ถ€๋ถ„์„ ๋งž์ถ”๋Š” ๊ฒƒ์ด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. solution ๋ฉ”์„œ๋“œ์—์„œ ๋งž์ถœ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ์žˆ๋‹ค๋ฉด true, ๋งž์ถœ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š”๋‹ค๋ฉด false๋ฅผ return ํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution ์™„์ „ ํƒ์ƒ‰ ๋งŒ์•ฝ ์–ด๋– ํ•œ ๋ฐฉ๋ฒ•์„ ์จ๋„ ๋งž์ถœ ์ˆ˜ ์—†๋‹ค๋ฉด false๋ฅผ returnํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 15.
  • [BOJ] ์˜์›…์ด๋Š” 2์˜ ๊ฑฐ๋“ญ ์ œ๊ณฑ์„ ์ข‹์•„ํ•ด! ์˜์›…์ด๋Š” 2์˜ ๊ฑฐ๋“ญ ์ œ๊ณฑ์„ ์ข‹์•„ํ•ด!(20153) [๋ฐฑ์ค€(BOJ)] 20153_์˜์›…์ด๋Š” 2์˜ ๊ฑฐ๋“ญ ์ œ๊ณฑ์„ ์ข‹์•„ํ•ด! ์˜์›…์ด๋Š” 2์˜ ๊ฑฐ๋“ญ ์ œ๊ณฑ์„ ์ข‹์•„ํ•ด! C++ ๋ฌธ์ œ : BOJ_20153๋ฒˆ ์˜์›…์ด๋Š” 2์˜ ๊ฑฐ๋“ญ ์ œ๊ณฑ์„ ์ข‹์•„ํ•ด! ์˜์›…์ด๋Š” 2์˜ ๊ฑฐ๋“ญ ์ œ๊ณฑ์„ ์ข‹์•„ํ•ด! ๋ฌธ์ œ ์„ค๋ช… ์šฐ์„  n ๊ฐœ์˜ ์ž์—ฐ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์ด n ๊ฐœ์˜ ์ˆ˜๋ฅผ ๋ชจ๋‘ ์ด์ง„์ˆ˜๋กœ ๋ฐ”๊พธ๊ณ  ๊ฐ ์ž๋ฆฌ์˜ 1์˜ ๊ฐœ์ˆ˜๋ฅผ ์กฐํšŒํ•ฉ๋‹ˆ๋‹ค. ๊ฐ ์ž๋ฆฌ์ˆ˜์˜ 1์˜ ๊ฐœ์ˆ˜๊ฐ€ ํ™€์ˆ˜์ด๋ฉด ์ตœ์ข… ๊ฒฐ๊ด๊ฐ’์— (2^์ž๋ฆฌ์ˆ˜)๋ฅผ ๋”ํ•ด์ฃผ๊ณ , ์ง์ˆ˜์ด๋ฉด ๋”ํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ์ตœ์ข… ๊ฒฐ๊ด๊ฐ’์ด ์ตœ๋Œ€๊ฐ€ ๋  ์ˆ˜ ์žˆ๋„๋ก n ๊ฐœ์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์ตœ๋Œ€ ํ•˜๋‚˜์˜ ์ž์—ฐ์ˆ˜๋ฅผ ์ œ์™ธํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ ๊ฒฐ๊ด๊ฐ’์„ ๋„์–ด์“ฐ๊ธฐ ์—†์ด ๋‘ ๋ฒˆ ์ถœ๋ ฅํ•˜๋ฉด ์ •๋‹ต์ž…๋‹ˆ๋‹ค. Solution ์™„์ „ ํƒ์ƒ‰, ์ˆ˜ํ•™ ์ฃผ์–ด์งˆ ์ˆ˜ ์žˆ๋Š” ์ˆ˜์˜ ์ตœ๊ณ ๊ฐ’์ด 2222222์ด๋ฏ€๋กœ, ๊ทธ์— ๋งž๊ฒŒ 2222222์˜ ์ˆซ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 15.
  • [AOJ] BOARDCOVER [ALGOSPOT Online Judge(AOJ)] BOARDCOVER C++ ๋ฌธ์ œ : AOJ BOARDCOVER ๋ฌธ์ œ ์„ค๋ช… ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋งˆ๋‹ค H*W ํฌ๊ธฐ์˜ ๊ฒŒ์ž„ํŒ์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๊ฒŒ์ž„ํŒ์˜ ๊ฐ ์ž๋ผ๋‹ˆ๋Š” ๊ฒ€์€ ์นธ์ด๋‚˜ ํฐ ์นธ์œผ๋กœ ๋˜์–ด์žˆ๋Š”๋ฐ, L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์œผ๋กœ ํฐ ์นธ์ด ์•ˆ ๋‚จ๋„๋ก ์ฑ„์›Œ์•ผ ํ•ฉ๋‹ˆ๋‹ค. L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์„ ์ž์œ ๋กญ๊ฒŒ ํšŒ์ „ํ•  ์ˆ˜ ์žˆ์ง€๋งŒ, ๋ธ”๋ก๋ผ๋ฆฌ ๊ฒน์น˜๊ฑฐ๋‚˜ ๊ฒ€์€ ์นธ์„ ๋ฎ์œผ๋ฉด ์•ˆ ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์œผ๋กœ ๋ชจ๋“  ํฐ ์นธ์„ ์ฑ„์šธ ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ์™„์ „ ํƒ์ƒ‰ ๊ฒŒ์ž„ํŒ์˜ ๊ฐ€์žฅ ์œ„์ชฝ, ์™ผ์ชฝ์˜ ํŒ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ์˜ค๋ฅธ์ชฝ, ์•„๋ž˜์ชฝ์œผ๋กœ ๋‚ด๋ ค๊ฐ€๋ฉฐ ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ•ด๊ฒฐํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๊ฒŒ์ž„ํŒ์˜ ํ•œ ์นธ์„ ๊ธฐ์ค€ ์‚ผ์•„ ์ˆœํšŒํ•˜๋ฉด์„œ L์ž ๋ชจ์–‘์˜ ๋ธ”๋ก์ด ๊ทธ ์นธ์„ ๊ธฐ์ค€์œผ๋กœ ํšŒ์ „ํ•  ์ˆ˜ ์žˆ๋Š” ๋„ค ๊ฐ€์ง€ .. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 14.
  • [AOJ] PICNIC [ALGOSPOT Online Judge(AOJ)] PICNIC C++ ๋ฌธ์ œ : AOJ PICNIC ๋ฌธ์ œ ์„ค๋ช… n ๋ช…์˜ ํ•™์ƒ์ด ์ฃผ์–ด์ง€๊ณ , m ๊ฐœ์˜ ๊ฐ€๋Šฅํ•œ ์ง์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. m ๊ฐœ๋กœ ์ฃผ์–ด์ง„ ์กฐ๊ฑด์— ๋งž๊ฒŒ ์ง์„ ์ง€์„ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๊ฐ€๋Šฅํ•˜๋‹ค๊ณ  ์ฃผ์–ด์ง€์ง€ ์•Š์€ ํ•™์ƒ๋“ค ๋ผ๋ฆฐ ์ง์ด ๋  ์ˆ˜ ์—†๊ณ , ๋ชจ๋“  ํ•™์ƒ๋“ค์€ ๊ฐ์ž์˜ ์ง์ด ์žˆ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution ์™„์ „ ํƒ์ƒ‰ ํ•™์ƒ์˜ ์ˆ˜๊ฐ€ ์ตœ๋Œ€ 10๋ช…์œผ๋กœ ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ํ™•์ธํ•˜์—ฌ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ตœ์•…์˜ ๊ฒฝ์šฐ ์ตœ๋Œ€ ํ•™์ƒ ์ˆ˜ 10๋ช…์ด ์ž์‹ ์„ ์ œ์™ธํ•œ 9๋ช…๊ณผ ๋ชจ๋‘ ์ง์ด ๋  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์ธ๋ฐ, ์ด ๊ฒฝ์šฐ๋Š” 9*7*5*3*1์ด๋ฏ€๋กœ ์‹œ๊ฐ„์ œํ•œ ์•ˆ์— ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•ด๋‹น ํ•™์ƒ์ด ์ง์„ ์ฐพ์•˜๋Š”์ง€์˜ ์œ ๋ฌด์ธ isFind ๋ฐฐ์—ด์„ ๋งŒ๋“ค์–ด ์ด ๋ฐฐ์—ด๋กœ .. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 14.
  • [BOJ] ์†Œ๋ฌธ๋‚œ ์น ๊ณต์ฃผ(1941) [๋ฐฑ์ค€(BOJ)] 1941_์†Œ๋ฌธ๋‚œ ์น ๊ณต์ฃผ C++ ๋ฌธ์ œ : BOJ_1941๋ฒˆ ์†Œ๋ฌธ๋‚œ ์น ๊ณต์ฃผ ๋ฌธ์ œ ์„ค๋ช… 5 * 5์˜ map์ด ์ฃผ์–ด์ง€๊ณ , ๊ฐ ์ž๋ฆฌ๋Š” 'Y' ํ˜น์€ 'S'๋กœ ํ‘œํ˜„๋˜์–ด ์žˆ์Šต๋‹ˆ๋‹ค. ์œ„, ์•„๋ž˜, ์ขŒ, ์šฐ์— ์„œ๋กœ ์ธ์ ‘ํ•œ 7๊ฐœ์˜ ์ž๋ฆฌ์—์„œ 'S' ๊ฐ€ ์ตœ์†Œ 4๊ฐœ ์ด์ƒ ์žˆ๋Š” 7 ์ž๋ฆฌ์˜ ์ˆ˜๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ์™„์ „ ํƒ์ƒ‰, bfs ๊ฐ ์ž๋ฆฌ์— ๋Œ€ํ•œ ์ •๋ณด๋ฅผ ๋ฒกํ„ฐ์— ์ €์žฅํ•ด ์ค๋‹ˆ๋‹ค. ์ €์žฅํ•  ์ •๋ณด๋Š” ๊ฐ ์ž๋ฆฌ์˜ ์œ„์น˜, 'S'์ธ์ง€์˜ ์—ฌ๋ถ€์ž…๋‹ˆ๋‹ค. ์ €์žฅ๋œ ์ƒํƒœ์—์„œ 7๊ฐœ์˜ ์ž๋ฆฌ๋ฅผ check ํ•ด์ฃผ๊ณ  ์ด 7๊ฐœ์˜ ์ž๋ฆฌ์—์„œ 'S'๊ฐ€ 4๊ฐœ ์ด์ƒ์ธ ๊ฒฝ์šฐ bfs๋ฅผ ๋Œ๋ ค์ค๋‹ˆ๋‹ค. bfs์—์„œ ๋‹ค์Œ์„ ํ™•์ธํ•˜๋ฉฐ ์ˆœํšŒํ•ด ์ค๋‹ˆ๋‹ค. ์ฃผ์–ด์ง„ ํฌ๊ธฐ ์•ˆ์— ์žˆ๋Š” map์˜ ์ž๋ฆฌ์ธ์ง€ ์ขŒ, ์šฐ, ์ƒ, ํ•˜๋กœ ์ธ์ ‘๋ผ์žˆ๋Š”์ง€ ์•ž์„  ์™„์ „ ํƒ์ƒ‰์—์„œ check ๋˜์–ด .. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 14.
  • [์•Œ๊ณ ๋ฆฌ์ฆ˜] lower_bound, upper_bound lower_bound, upper_bound lower_bound, upper_bound๋ฅผ int ํƒ€์ž…๊ณผ pair์—์„œ๋„ ์‚ฌ์šฉํ•ด๋ด…์‹œ๋‹ค. algorithm ํ—ค๋” lower_bound, upper_bound๋ฅผ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•ด์„  algorithm ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ํ•„์š”ํ•ฉ๋‹ˆ๋‹ค. #include ์„ ์–ธ lower_bound(์‹œ์ž‘ ์ดํ„ฐ๋ ˆ์ดํ„ฐ, ๋ ์ดํ„ฐ๋ ˆ์ดํ„ฐ, ์ง€์ • ๊ฐ’) upper_bound(์‹œ์ž‘ ์ดํ„ฐ๋ ˆ์ดํ„ฐ, ๋ ์ดํ„ฐ๋ ˆ์ดํ„ฐ, ์ง€์ • ๊ฐ’) ๋ฆฌํ„ด ๊ฐ’ vector์—์„œ lower_bound, upper_bound๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ์˜ ๋ฆฌ ๊ฐ’์„ ์•Œ์•„๋ด…์‹œ๋‹ค. lower_bound lower_bound๋Š” vector์˜ ์‹œ์ž‘ ์ดํ„ฐ๋ ˆ์ดํ„ฐ์™€ ๋ ์ดํ„ฐ๋ ˆ์ดํ„ฐ ์‚ฌ์ด์—์„œ ์ง€์ •ํ•œ ๊ฐ’ ์ด์ƒ์„ ๊ฐ€์ง€๋Š” ์ตœ์ดˆ์˜ ์ดํ„ฐ๋ ˆ์ดํ„ฐ๋ฅผ ๋ฐ˜ํ™˜ํ•ฉ๋‹ˆ๋‹ค. upper_bound upper_.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 14.
  • [BOJ] ์‚ฌ์ดํด ๊ฒŒ์ž„(20040) [๋ฐฑ์ค€(BOJ)] 20040_์‚ฌ์ดํด ๊ฒŒ์ž„ C++ ๋ฌธ์ œ : BOJ_20040๋ฒˆ ์‚ฌ์ดํด ๊ฒŒ์ž„ ๋ฌธ์ œ ์„ค๋ช… n ๊ฐœ์˜ ๋…ธ๋“œ๊ฐ€ ์ฃผ์–ด์ง€๊ณ , m ๊ฐœ์˜ ์–‘๋ฐฉํ–ฅ ์„ ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ตœ์ดˆ๋กœ ์‚ฌ์ดํด์ด ์™„์„ฑ๋˜๋Š” m ๋ฒˆ ์งธ๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋ชจ๋“  m์„ ์ˆœํšŒํ•ด๋„ ์‚ฌ์ดํด์ด ์ƒ๊ธฐ์ง€ ์•Š์•˜๋‹ค๋ฉด, 0์„ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ n์ด ์ตœ๋Œ€ 500,000์ด๋ฏ€๋กœ O(n) ๋งŒ์— ๋‹ต์„ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์œ ๋‹ˆ์˜จ ํŒŒ์ธ๋“œ๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด์–ด์ง€๋Š” ๋‘ ์ ์„ merge ํ•˜๋ฉด์„œ ์ง„ํ–‰ํ•ฉ๋‹ˆ๋‹ค. merge ํ•˜๊ธฐ ์ „์— ์ฃผ์–ด์ง„ ๋‘ ์ ์ด ๊ฐ™์€ ์กฐ์ƒ์ด๋ผ๋ฉด, ๊ฐ™์€ ์กฐ์ƒ์„ ๊ฐ–๊ณ  ์žˆ๋Š” ๋…ธ๋“œ๋ผ๋ฆฌ ์ด์–ด์ง€๋ฏ€๋กœ ์‚ฌ์ดํด์ด ๋ฉ๋‹ˆ๋‹ค. ์ด๋•Œ์˜ m์„ ์ถœ๋ ฅํ•ด ์ค˜์•ผ ํ•ฉ๋‹ˆ๋‹ค. Description vector๋ฅผ ์ด์šฉํ•ด n๊ณผ m์— ๊ฐ’์— ๋งž๋Š” ๋ฐฐ์—ด์„ ๋™์ ํ• ๋‹นํ–ˆ์Šต๋‹ˆ๋‹ค. .. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 14.
  • [BOJ] ํ•˜๋…ธ์ด ํƒ‘ ์ด๋™ ์ˆœ์„œ(11729) [๋ฐฑ์ค€(BOJ)] 11729_ํ•˜๋…ธ์ด ํƒ‘ ์ด๋™ ์ˆœ์„œ C++ ๋ฌธ์ œ : BOJ_11729๋ฒˆ ํ•˜๋…ธ์ด ํƒ‘ ์ด๋™ ์ˆœ์„œ ๋ฌธ์ œ ์„ค๋ช… ์žฌ๊ท€ ์žฌ๊ท€ ๋ฌธ์ œ๋กœ ์œ ๋ช…ํ•œ ํ•˜๋…ธ์ด ํƒ‘ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. n์„ ์ž…๋ ฅ๋ฐ›์œผ๋ฉด ์„ธ ๊ฐœ์˜ ์žฅ๋Œ€ ์ค‘ ์ฒซ ๋ฒˆ์งธ ์žฅ๋Œ€์— n ๊ฐœ์˜ ํƒ‘์ด ์Œ“์ด๋Š” ๊ฒƒ์œผ๋กœ ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. n ๊ฐœ์˜ ํƒ‘์€ ๊ฐ€์žฅ ์œ„์— ์žˆ๋Š” ์›ํŒ์ด ๊ฐ€์žฅ ๊ฐ€๋ณ๊ณ  ์•„๋ž˜๋กœ ๊ฐˆ์ˆ˜๋ก ๋ฌด๊ฑฐ์šด ์›ํŒ์ด๋ฉฐ, ๊ฐ€๋ฒผ์šด ์›ํŒ ์œ„์— ๋ฌด๊ฑฐ์šด ์›ํŒ์ด ์˜ฌ๋ผ๊ฐˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๊ฐ ์žฅ๋Œ€ ์ค‘ ๊ฐ€์žฅ ์œ„์— ์žˆ๋Š” ์›ํŒ์„ ํ•˜๋‚˜ ์˜ฎ๊ธฐ๋Š” ๊ฒƒ์„ 1ํšŒ๋กœ ํ•  ๋•Œ, ์ตœ์ดˆ์— ์ฒซ ๋ฒˆ์งธ ์žฅ๋Œ€์— ์žˆ์—ˆ๋˜ ์›ํŒ์„ ๋ชจ๋‘ ์„ธ ๋ฒˆ์งธ ์›ํŒ์œผ๋กœ ์˜ฎ๊ธฐ๋Š” ์ตœ์†Œ ์ด๋™ ํšŒ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ํ˜„์žฌ ์žฅ๋Œ€์˜ ์œ„์น˜๋ฅผ st, ์ด๋™ํ•ด์•ผ ํ•˜๋Š” ์žฅ๋Œ€์˜ ์œ„์น˜๋ฅผ ed, ๋‚˜๋จธ์ง€ ์žฅ๋Œ€๋ฅผ mid๋ผ๊ณ  ํ•ฉ์‹œ๋‹ค. ์ฒ˜์Œ์— n์„ 3์ด๋ผ๊ณ  ์ž…๋ ฅ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 13.
  • [BOJ] ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด(11054) [๋ฐฑ์ค€(BOJ)] ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด(11054) C++ ๋ฌธ์ œ : BOJ_11054๋ฒˆ ๊ฐ€์žฅ ๊ธด ๋ฐ”์ดํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด ๋ฌธ์ œ ์„ค๋ช… DP ๊ธฐ์กด์˜ ์ฆ๊ฐ€ํ•˜๋Š” ์ˆ˜์—ด, ๊ฐ์†Œํ•˜๋Š” ์ˆ˜์—ด์ด ํ•ฉ์ณ์ง„ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ˆ˜์—ด์ด ์ฆ๊ฐ€ํ•˜๋‹ค๊ฐ€ ๊ฐ์†Œ๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ, ์ˆ˜์—ด์ด ๊ณ„์† ์ฆ๊ฐ€ํ•˜๋Š” ๊ฒฝ์šฐ, ์ˆ˜์—ด์ด ๊ณ„์† ๊ฐ์†Œํ•˜๋Š” ๊ฒฝ์šฐ๊ฐ€ ๋ชจ๋‘ ๋ฐ”์ด ํ† ๋‹‰ ๋ถ€๋ถ„ ์ˆ˜์—ด์ž…๋‹ˆ๋‹ค. ์ˆ˜์—ด์ด ๊ฐ์†Œํ•˜๋‹ค๊ฐ€ ์ฆ๊ฐ€ํ•˜๋Š” ๊ฒฝ์šฐ๋Š” ํ•ด๋‹น๋˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. DP๋ฅผ ํ™œ์šฉํ•ด ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ์Šต๋‹ˆ๋‹ค. Solution ์•ž์„œ ์–ธ๊ธ‰ํ•œ ์„ธ ๊ฐ€์ง€ ๊ฒฝ์šฐ๋กœ ๋‚˜๋ˆ„์–ด์„œ DP ๋ฐฐ์—ด์— ๊ฐฑ์‹ ํ•ด ์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ˆ˜์—ด์ด ๊ณ„์† ์ฆ๊ฐ€ํ•˜๋Š” ๊ฒฝ์šฐ -> dp[0][ํ˜„์žฌ ์ธ๋ฑ์Šค] ์ˆ˜์—ด์ด ์ฆ๊ฐ€ํ•˜๋‹ค๊ฐ€ ๊ฐ์†Œ๊ฐ€ ๋˜๋Š” ๊ฒฝ์šฐ -> dp[1][ํ˜„์žฌ ์ธ๋ฑ์Šค] ์ˆ˜์—ด์ด ๊ณ„์† ๊ฐ์†Œํ•˜๋Š” ๊ฒฝ์šฐ -> dp[2][ํ˜„์žฌ ์ธ๋ฑ์Šค] ๋กœ ๋งŒ๋“ค์–ด ๊ฐ’์„ ๊ณ„์† ๋น„.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 13.
  • [BOJ] Thread Knots(17976) [๋ฐฑ์ค€(BOJ)] Thread Knots(17976) C++ ๋ฌธ์ œ : BOJ_17976๋ฒˆ Thread Knots ๋ฌธ์ œ ์„ค๋ช… ์ด๋ถ„ํƒ์ƒ‰ n ๊ฐœ์˜ thread๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ์ด thread ํ•˜๋‚˜ํ•˜๋‚˜๋งˆ๋‹ค ์ ์„ ์ฐ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ์ ์˜ x์ขŒํ‘œ์˜ ๊ฐ„๊ฒฉ์˜ ์ตœ์†Ÿ๊ฐ’์ด ์ตœ๋Œ€๊ฐ€ ๋˜๋Š” ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋Š” ๊ฒƒ์ด ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ ์˜ ๋ฒ”์œ„๊ฐ€ 0๋ถ€ํ„ฐ 1000000000์ด๊ธฐ ๋•Œ๋ฌธ์— ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ์ ์˜ ๊ฐ„๊ฒฉ์„ ํŒŒ์•…ํ•˜๊ธฐ๋Š” ์–ด๋ ค์šฐ๋ฏ€๋กœ, ์ด๋ถ„ ํƒ์ƒ‰์„ ์ด์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution ์šฐ์„  thread์˜ ๋ฒ”์œ„๋ฅผ ๋ฒกํ„ฐ๋กœ ์ž…๋ ฅ๋ฐ›์€ ๋’ค, ๋ฒกํ„ฐ๋ฅผ ์ •๋ ฌํ•ฉ๋‹ˆ๋‹ค. ์ˆœ์„œ๋Œ€๋กœ ์ •๋ ฌํ•œ ๊ฐ’์„ ์ˆœํšŒํ•˜๋ฉด์„œ ํ˜„์žฌ ์ด๋ถ„ ํƒ์ƒ‰์˜ mid ๊ฐ’์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ตœ์†Ÿ๊ฐ’์œผ๋กœ ๊ฐ thread๋งˆ๋‹ค ์ ์„ ์ฐ์„ ์ˆ˜ ์žˆ๋Š”์ง€ ํ™•์ธํ•ฉ๋‹ˆ๋‹ค. ํ™•์ธ์„ ์œ„ํ•ด์„  ์šฐ์„  ์ฒซ ๋ฒˆ์งธ thread์˜ ์‹œ์ž‘์ ์— ์ฒซ ๋ฒˆ์งธ ์ ์„ .. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 13.
  • [BOJ] LCS(9251) [๋ฐฑ์ค€(BOJ)] LCS(9251) C++ ๋ฌธ์ œ : BOJ_9251๋ฒˆ LCS ๋ฌธ์ œ ์„ค๋ช… DP ์ตœ๋Œ€ 1000 ๊ธ€์ž์˜ ๋‘ ๋‹จ์–ด๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ๋‘ ๋‹จ์–ด์—์„œ ๊ณตํ†ต๋œ ๋ถ€๋ถ„ ์ˆ˜์—ด ์ค‘ ๊ฐ€์žฅ ๊ธด ์ˆ˜์—ด์„ ์ฐพ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋ฌธ์ œ ์ž์ฒด๋Š” ๊ฐ„๋‹จํ•˜์ง€๋งŒ, ์™„์ „ ํƒ์ƒ‰์„ ์ด์šฉํ•˜๋ฉด ์‹œ๊ฐ„ ์ดˆ๊ณผ๊ฐ€ ๋‚˜๊ธฐ ๋•Œ๋ฌธ์— DP๋ฅผ ํ™œ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ์œ„ ํ‘œ๋ฅผ ์ฐธ๊ณ ํ•ด์„œ DP ์‹์„ ์งœ์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋‘ ๋ฌธ์ž์—ด์˜ ๊ธธ์ด๋งŒํผ 2์ค‘ for ๋ฌธ์„ ์ˆœํšŒํ•˜๋ฉด์„œ ๋ฌธ์ž๊ฐ€ ๊ฐ™์„ ๋•Œ์™€ ๋‹ค๋ฅผ ๋•Œ ๋‘ ์กฐ๊ฑด์œผ๋กœ dp ์‹์„ ์„ธ์›Œ์ค๋‹ˆ๋‹ค. ๋‘ ๋ฌธ์ž์—ด์ด ๊ฐ™๋‹ค๋ฉด, dp[i][j] = dp[i-1][j-1]+1 ์ฆ‰, ์œ„ ํ‘œ์—์„œ ๋Œ€๊ฐ์„ ์˜ dp ๊ฐ’ + 1์ž…๋‹ˆ๋‹ค. ๋‘ ๋ฌธ์ž์—ด์ด ๋‹ค๋ฅด๋‹ค๋ฉด, dp[i][j] = max(dp[i][j-1], dp[i-1][j]) ์ฆ‰, ์œ„ ํ‘œ์—.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 12.
  • [BOJ] ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ(2579) [๋ฐฑ์ค€(BOJ)] ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ(2579) C++ ๋ฌธ์ œ : BOJ_2579๋ฒˆ ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ ๋ฌธ์ œ ์„ค๋ช… DP ๊ฐ ๊ณ„๋‹จ๋งˆ๋‹ค ์ ์ˆ˜๊ฐ€ ์žˆ๊ณ , ๋„์ฐฉ ์ง€์ ๊นŒ์ง€ ๊ณ„๋‹จ์„ ์˜ค๋ฅด๋ฉฐ ์ ์ˆ˜๋ฅผ ๋”ํ•ด์„œ ์ตœ๋Œ“๊ฐ’์ด ๋‚˜์™€์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ๊ณ„๋‹จ์€ ํ•œ ๋ฒˆ์— ํ•œ ๊ณ„๋‹จ์ด๋‚˜ ๋‘ ๊ณ„๋‹จ์”ฉ ์˜ค๋ฅผ ์ˆ˜ ์žˆ๊ณ , ์„ธ ๊ฐœ์˜ ๊ณ„๋‹จ์„ ์—ฐ์†ํ•ด์„œ ๋ฐŸ์„ ์ˆ˜๋Š” ์—†์Šต๋‹ˆ๋‹ค. ๊ทธ๋ฆฌ๊ณ  ๋งˆ์ง€๋ง‰ ๋„์ฐฉ ์ง€์ ์˜ ๊ณ„๋‹จ์€ ๋ฐ˜๋“œ์‹œ ๋ฐŸ์•„์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution dp๋ฅผ ํ™œ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•˜์˜€์Šต๋‹ˆ๋‹ค. dp[ํ˜„์žฌ ๊ณ„๋‹จ ์ธ๋ฑ์Šค][์ด์ „ ๊ณ„๋‹จ๊ณผ ์—ฐ์†ํ•ด์„œ ๋ฐŸ์•˜๋Š”์ง€์˜ ์œ ๋ฌด] = ํ˜„์žฌ ๊ณ„๋‹จ๊นŒ์ง€์˜ ์ตœ๋Œ“๊ฐ’์œผ๋กœ dp ์‹์„ ์งœ๋ดค์Šต๋‹ˆ๋‹ค. ํ˜„์žฌ ๊ณ„๋‹จ์—์„œ ์ด์ „ ๊ณ„๋‹จ๊ณผ ์—ฐ์†ํ•ด์„œ ๋ฐŸ์ง€ ์•Š์•˜๋‹ค๋ฉด, ํ˜„์žฌ ๊ณ„๋‹จ ์ธ๋ฑ์Šค-2์˜ ๊ณ„๋‹จ์—์„œ์˜ ์ตœ๋Œ“๊ฐ’์„ ๊ฐฑ์‹ ํ•ด ์ฃผ์–ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ํ˜„์žฌ๋ณด๋‹ค 2๊ฐ€ ๋‚ฎ์€ ์ธ๋ฑ์Šค์˜ ๊ณ„๋‹จ์€ ์ด์ „ ๊ณ„๋‹จ๊ณผ ์—ฐ์†ํ•ด์„œ ๋ฐŸ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 12.
  • [BOJ] ์ด์ง„ ํŠธ๋ฆฌ(13325) [๋ฐฑ์ค€(BOJ)] ์ด์ง„ ํŠธ๋ฆฌ(13325) C++ ๋ฌธ์ œ : BOJ_13325๋ฒˆ ์ด์ง„ ํŠธ๋ฆฌ ๋ฌธ์ œ ์„ค๋ช… ํŠธ๋ฆฌ ์ˆœํšŒ ํฌํ™”์ด์ง„ ํŠธ๋ฆฌ๋ฅผ ๋‹ค๋ฃจ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ํŠธ๋ฆฌ์˜ ๋†’์ด k๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ๋ณดํ†ต์˜ ํŠธ๋ฆฌ ๋ฌธ์ œ์™€๋Š” ๋‹ค๋ฅด๊ฒŒ ๋…ธ๋“œ์˜ ๊ฐ’์ด ์•„๋‹Œ ๊ฐ„์„ ์˜ ๊ฐ’์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ๋ฆฌํ”„ ๋…ธ๋“œ๋กœ ๊ฐ€๋Š” ๊ฑฐ๋ฆฌ ์ค‘ ์ตœ๋Œ“๊ฐ’์„ x๋ผ๊ณ  ํ•œ๋‹ค๋ฉด, ๊ฐ๊ฐ์˜ ๊ฐ„์„ ์— ์ตœ์†Ÿ๊ฐ’์„ ๋”ํ•˜์—ฌ ๋ฃจํŠธ ๋…ธ๋“œ์—์„œ ๋ฆฌํ”„ ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ฐ๊ฐ์˜ ๋ชจ๋“  ๊ฑฐ๋ฆฌ๋ฅผ x๋ฅผ ๋งž์ถฐ์ค˜์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ๊ฑฐ๋ฆฌ๋ฅผ ๋งž์ถœ ๋•Œ ์ƒ์œ„ ๋…ธ๋“œ์˜ ๊ฐ„์„ ์—์„œ ๊ฐ’์„ ์ตœ๋Œ“๊ฐ’์œผ๋กœ ๋”ํ•ด์ค„์ˆ˜๋ก ์ตœ์ข… ๊ฑฐ๋ฆฌ๋“ค์˜ ๊ฐ’์ด ์ค„์–ด๋“ญ๋‹ˆ๋‹ค. ์žฌ๊ท€์˜ ๋ฐฉ์‹์„ ์ด์šฉํ–ˆ์Šต๋‹ˆ๋‹ค. ์šฐ์„  dfs๋ฅผ ์ˆœํšŒํ•˜์—ฌ ๊ฐ€์žฅ ๋จผ ๋ฆฌํ”„ ๋…ธ๋“œ์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•ฉ๋‹ˆ๋‹ค ๊ทธ๋ฆฌ๊ณ  ๋‹ค์‹œ ๋ฆฌํ”„ ๋…ธ๋“œ๋ฅผ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, ๋ฆฌํ”„ ๋…ธ๋“œ๊นŒ์ง€์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ™๊ฒŒ ๋งž์ถ”๊ธฐ ์œ„ํ•ด .. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 12.
  • [BOJ] ํ‡ด์‚ฌ(14501) [๋ฐฑ์ค€(BOJ)] ํ‡ด์‚ฌ(14501) C++ ๋ฌธ์ œ : BOJ_14501๋ฒˆ ํ‡ด์‚ฌ ๋ฌธ์ œ ์„ค๋ช… ์™„์ „ ํƒ์ƒ‰ n ๊ฐœ์˜ ๋‚ ์ด ์žˆ๊ณ , n+1์ผ์งธ ํ‡ด์‚ฌ๋ฅผ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ๊ฐ ์š”์ผ๋งˆ๋‹ค ํ•  ์ˆ˜ ์žˆ๋Š” ์ผ์— ํ•„์š”ํ•œ ๊ธฐ๊ฐ„๊ณผ ๊ทธ์— ๋Œ€ํ•œ ๋ณด์ƒ์ด ๊ฐ๊ฐ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. n+1 ์งธ๋Š” ํ‡ด์‚ฌํ•˜๋ฏ€๋กœ ์ผํ•  ์ˆ˜ ์—†๊ณ , n ์ผ ์•ˆ์— ์ฒ˜๋ฆฌํ•  ์ˆ˜ ์žˆ๋Š” ์ผ๋“ค ์ค‘์—์„œ ์ตœ๋Œ€ํ•œ์˜ ๋ณด์ƒ์„ ๋ฐ›์„ ์ˆ˜ ์žˆ๊ฒŒ ํ•  ์ผ์„ ๊ณจ๋ผ์•ผ ํ•ฉ๋‹ˆ๋‹ค. n์ด ์ตœ๋Œ€ 15์ž„์œผ๋กœ ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.(O(2^n)) Solution ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค๊ณ , ํ•ด๋‹น ์ผ์„ ์„ ํƒํ•˜๋Š” ๊ฒฝ์šฐ์™€ ์„ ํƒํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ๋กœ ๋งˆ์ง€๋ง‰ ์ผ๊นŒ์ง€ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ, expired๋ฅผ ๋งŒ๋“ค์–ด์„œ ์ด์ „ ์š”์ผ์—์„œ ์„ ํƒํ•œ ์ผ์— ๋Œ€ํ•œ ์ผ์„ ํ•˜๋Š” ์ค‘์ด ์•„๋‹Œ ๊ฒฝ์šฐ ํ˜„์žฌ ์ผ์„ ์„ ํƒํ•˜๋Š” ๊ฒฝ์šฐ๋กœ ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. Desc.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 12.
  • [BOJ] ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ(12865) [๋ฐฑ์ค€(BOJ)] ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ(12865) C++ ๋ฌธ์ œ : BOJ_12865๋ฒˆ ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ ๋ฌธ์ œ ์„ค๋ช… DP(๋ƒ…์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜) DP ๋ฌธ์ œ ์ค‘ ์œ ๋ช…ํ•œ ๋ฌธ์ œ์ธ ํ‰๋ฒ”ํ•œ ๋ฐฐ๋‚ญ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋ฌผํ’ˆ์˜ ์ˆ˜์™€ ๋ฐฐ๋‚ญ์— ๋‹ด์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋ฌด๊ฒŒ๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์ด์–ด์„œ ๊ฐ๊ฐ ๋ฌผํ’ˆ์˜ ๋ฌด๊ฒŒ์™€ ๊ฐ€์น˜๊ฐ€ ์ฃผ์–ด์ง€๋ฉฐ, ๊ฐ€๋ฐฉ ์•ˆ์— ์ตœ๋Œ€ ๋ฌด๊ฒŒ๋ฅผ ์ดˆ๊ณผํ•˜์ง€ ์•Š๊ฒŒ ๋„ฃ์—ˆ์„ ๋•Œ ์ตœ๋Œ€ ๊ฐ€์น˜๋ฅผ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ด๋•Œ ์ฃผ์˜ํ•  ๊ฒƒ์€ ๊ฐ๊ฐ์˜ ๋ฌผํ’ˆ์€ ํ•˜๋‚˜๋งŒ ๋“ค์–ด๊ฐˆ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ, ํ•˜๋‚˜์˜ ๋ฌผํ’ˆ์ด ์ค‘๋ณต๋˜๊ฒŒ ๋“ค์–ด๊ฐ€๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋Š” ํ”ผํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution dp๋ฅผ ์ด์šฉํ•œ ํ’€์ด๋ฅผ ํ•ด๋ดค์Šต๋‹ˆ๋‹ค. 2์ฐจ์› dp๋ฅผ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๋งŒ๋“ค์—ˆ์Šต๋‹ˆ๋‹ค. dp[i ๋ฒˆ์งธ๊นŒ์ง€ ๋ฌผ๊ฑด์„ ์‚ฌ์šฉํ–ˆ์„ ๋•Œ][๋ฌด๊ฒŒ๊ฐ€ j ์ผ ๋•Œ] = ์ตœ๋Œ“๊ฐ’ 1~n๊นŒ์ง€์˜ ๋ฌผ๊ฑด์—์„œ ํ˜„์žฌ ์ตœ๋Œ“๊ฐ’์„ ์•Œ๊ณ ์ž ํ•˜๋Š” ๋ฌด๊ฒŒ๊ฐ€ j๋ผ๊ณ  ํ–ˆ์„.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 12.
  • [BOJ] ์™ธํŒ์› ์ˆœํšŒ(2098) [๋ฐฑ์ค€(BOJ)] ์™ธํŒ์› ์ˆœํšŒ(2098) C++ ๋ฌธ์ œ : BOJ_2098๋ฒˆ ์™ธํŒ์› ์ˆœํšŒ ๋ฌธ์ œ ์„ค๋ช… ๋น„ํŠธ๋งˆ์Šคํ‚น n ๊ฐœ์˜ ์—ฌํ–‰์ง€๊ฐ€ ์žˆ์„ ๋•Œ, ๊ฐ ์—ฌํ–‰์ง€์—์„œ ๋‹ค๋ฅธ ์—ฌํ–‰์ง€๋กœ ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋น„์šฉ์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์ด๋•Œ ๋น„์šฉ์„ ์ตœ์†Œํ•œ์œผ๋กœ ํ•ด์„œ ์ถœ๋ฐœํ•œ ์—ฌํ–‰์ง€์—์„œ ๋ชจ๋“  ์—ฌํ–‰์ง€๋ฅผ ๋ฐฉ๋ฌธํ•œ ๋’ค ๋‹ค์‹œ ์ถœ๋ฐœํ•œ ์—ฌํ–‰์ง€๋กœ ๋Œ์•„์˜ค๋Š” ๋น„์šฉ์„ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ด๋•Œ ํ•œ ๋ฒˆ ๋ฐฉ๋ฌธํ–ˆ๋˜ ์—ฌํ–‰์ง€๋Š” ๋‹ค์‹œ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค. ๋น„ํŠธ ๋งˆ์Šคํ‚น ์™ธ์—๋„ ์—ฌ๋Ÿฌ ๊ฐ€์ง€ ๋ฐฉ๋ฒ•์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ์œ ๋ช…ํ•œ ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์—ฌํ–‰์ง€์˜ ์ˆ˜๊ฐ€ ์ตœ๋Œ€ 16์ด๊ธฐ ๋•Œ๋ฌธ์— 16๊ฐœ์˜ ์ž๋ฆฌ์ˆ˜๋ฅผ ๋งŒ๋“ค๊ณ  ๋น„ํŠธ ์—ฐ์‚ฐ์œผ๋กœ ๋ฐฉ๋ฌธํ•œ ์—ฌํ–‰์ง€๋ฅผ ์ฒดํฌํ•˜๋Š” ๋ฐฉ์‹์œผ๋กœ ๋น„ํŠธ ๋งˆ์Šคํ‚น์œผ๋กœ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. Solution recursion ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค์–ด ์ค๋‹ˆ๋‹ค. ์ด๋•Œ, ํ•จ์ˆ˜์˜ ๋‚ด์šฉ์€ recursion(ํ˜„์žฌ ๋„์‹œ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 11.
  • [BOJ] ์Šค๋„์ฟ (2580) [๋ฐฑ์ค€(BOJ)] ์Šค๋„์ฟ (2580) C++ ๋ฌธ์ œ : BOJ_2580๋ฒˆ ์Šค๋„์ฟ  ์ž…์ถœ๋ ฅ ํ˜•์‹๋งŒ ์‚ด์ง ๋‹ค๋ฅธ ๊ฐ™์€ ๋ฌธ์ œ๋กœ BOJ_2239๋ฒˆ ์Šค๋„์ฟ ๋„ ์žˆ์Šต๋‹ˆ๋‹ค. ๋ฌธ์ œ ์„ค๋ช… ๋ฐฑํŠธ๋ž˜ํ‚น, dfs ์™„์„ฑ๋˜์ง€ ์•Š์€ ์Šค๋„์ฟ ๊ฐ€ ์ฃผ์–ด์ง€๊ณ , ์ด๋ฅผ ์™„์„ฑํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์Šค๋„์ฟ ์˜ ์ˆ˜๊ฐ€ ํ™•์ •๋˜์ง€ ์•Š์€ ๊ณณ์€ 0์œผ๋กœ ์ž…๋ ฅ๋˜์–ด ์žˆ๊ณ , ์ด 0๋“ค์„ ์ „๋ถ€ ์ฑ„์šด ์Šค๋„์ฟ ํŒ์„ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. ๋ฌธ์ œ๋Š” ์ŠคํŽ˜์…œ ์ €์ง€์ด๋ฏ€๋กœ, ํ•˜๋‚˜์˜ ๊ฒฝ์šฐ๊ฐ€ ์•„๋‹Œ ์—ฌ๋Ÿฌ ๊ฒฝ์šฐ๊ฐ€ ๋‹ต์ด ๋  ์ˆ˜ ์žˆ๋Š” ์Šค๋„์ฟ ๋Š” ๊ทธ์ค‘ ํ•˜๋‚˜๋ฅผ ์ถœ๋ ฅํ•˜๋ฉด ์ •๋‹ต ์ฒ˜๋ฆฌ๊ฐ€ ๋ฉ๋‹ˆ๋‹ค. dfs์™€ ๋ฐฑํŠธ๋ž˜ํ‚น์„ ์ด์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค. Solution ์ž…๋ ฅ ๋ฒˆํ˜ธ๊ฐ€ 0์ธ ๊ณณ์˜ ์ขŒํ‘œ๋“ค์„ ํ•˜๋‚˜ํ•˜๋‚˜ ์ €์žฅํ•ฉ๋‹ˆ๋‹ค. ์ €์žฅ๋œ ์ขŒํ‘œ๋ฅผ ํ•˜๋‚˜์”ฉ dfs๋กœ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค. ์ด๋•Œ ํ˜„์žฌ ์ˆœํšŒ ์ค‘์ธ ๊ณณ์— ๋งž๋Š” ๋ฒˆํ˜ธ๊ฐ€ ์žˆ์œผ๋ฉด ๋‹ค์Œ ์ˆœํšŒ๋กœ ์ง„ํ–‰ํ•˜๊ณ , 1~9 ๋ชจ๋“  ๋ฒˆ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 10.
  • [BOJ] ๋ฐฑ์กฐ์˜ ํ˜ธ์ˆ˜(3197) [๋ฐฑ์ค€(BOJ)] ๋ฐฑ์กฐ์˜ ํ˜ธ์ˆ˜(3197) C++ ๋ฌธ์ œ : BOJ_3197๋ฒˆ ๋ฐฑ์กฐ์˜ ํ˜ธ์ˆ˜ ๋ฌธ์ œ ์„ค๋ช… ์ด๋ถ„ํƒ์ƒ‰, bfs ๋ฌผ ๊ณต๊ฐ„๊ณผ ๋น™ํŒ ๊ณต๊ฐ„์ด ์žˆ๋Š” ์ง€๋„๊ฐ€ ์ฃผ์–ด์ง€๊ณ , L์— ๋‘ ๋ฐฑ์กฐ์˜ ์œ„์น˜๊ฐ€ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ๋ฌผ ๊ณต๊ฐ„๊ณผ ๊ฐ€๋กœ, ์„ธ๋กœ๋กœ ์ ‘ํ•œ ๋น™ํŒ ๋ถ€๋ถ„์ด ํ•˜๋ฃจ์— ํ•œ ๋ฒˆ์”ฉ ๋…น๋Š”๋ฐ, ์ด๋•Œ ๋‘ ๋ฐฑ์กฐ๊ฐ€ ๋งŒ๋‚  ์ˆ˜ ์žˆ๋Š” ์ตœ์†Œ์˜ ๋‚ ์„ ๊ณ„์‚ฐํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ์ด ๋ฌธ์ œ๋Š” ํ•˜๋ฃจ์— ํ•œ ๋ฒˆ์”ฉ ๋…น๋Š” ๋น™ํŒ ๋ถ€๋ถ„๋„ ๊ณ ๋ คํ•ด์•ผ ํ•˜๊ณ , ๋˜ ๋น™ํŒ์ด ๋…น์•˜์„ ๋•Œ ๋งŒ๋‚  ์ˆ˜ ์žˆ๋Š” ์ตœ์†Œ์˜ ๋‚ ๋„ ๊ตฌํ•ด์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์— bfs์™€ ์ด๋ถ„ ํƒ์ƒ‰ ๋‘ ๊ฐ€์ง€๊ฐ€ ์“ฐ์ด๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ์ฒ˜์Œ์— bfs๋ฅผ ์ด์šฉํ•˜์—ฌ ๋น™ํŒ์ด ๋ชจ๋‘ ๋…น๋Š” ์ตœ๋Œ€ ๋‚ ์„ ์ด๋ถ„ ํƒ์ƒ‰์˜ max ๊ฐ’์œผ๋กœ ์ง€์ •ํ•ด ์ฃผ๊ณ  ์ด๋ถ„ ํƒ์ƒ‰์„ ์‹คํ–‰ํ•ฉ๋‹ˆ๋‹ค. ์ตœ์†Ÿ๊ฐ’๊ณผ ์ตœ๋Œ“๊ฐ’์˜ ์ค‘๊ฐ„๊ฐ’์œผ๋กœ bfs๋ฅผ ๋Œ๋ฆฌ๋ฉฐ ์ค‘๊ฐ„๊ฐ’์˜ ๋‚ ์ด ๋˜๊ธฐ ์ „์—.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 10.
  • [BOJ] ํ›„์œ„ ํ‘œ๊ธฐ์‹(1918) [๋ฐฑ์ค€(BOJ)] ํ›„์œ„ ํ‘œ๊ธฐ์‹(1918) C++ ๋ฌธ์ œ : BOJ_1918๋ฒˆ ํ›„์œ„ ํ‘œ๊ธฐ์‹ ๋ฌธ์ œ ์„ค๋ช… Stack ์ค‘์œ„ ํ‘œ๊ธฐ์‹์œผ๋กœ ์˜ˆ์ œ๊ฐ€ ์ฃผ์–ด์ง€๋ฉด ์ด๊ฒƒ์„ ํ›„์œ„ ํ‘œ๊ธฐ์‹์œผ๋กœ ๋ฐ”๊พธ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ํ”ผ์—ฐ์‚ฐ์ž๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋งŒ ๋‚˜์˜ค๋ฉฐ, '-'๊ฐ€ ๊ฐ€์žฅ ์•ž์— ๋‚˜์˜ค๊ฑฐ๋‚˜, '*'๊ฐ€ ์ƒ๋žต๋˜๋Š” ์ž…๋ ฅ์€ ํ—ˆ์šฉํ•˜์ง€ ์•Š์Šต๋‹ˆ๋‹ค. stack์„ ์ƒํ™ฉ์— ๋งž๊ฒŒ ํ™œ์šฉํ•ด์„œ ํ’€์–ด์•ผ ํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ์ „์ฒด ๋ฌธ์ž์—ด์„ ์ž…๋ ฅ๋ฐ›๊ณ  ์•„๋ž˜์™€ ๊ฐ™์€ ๊ทœ์น™์œผ๋กœ ์ˆœํšŒํ•ฉ๋‹ˆ๋‹ค. ํ”ผ์—ฐ์‚ฌ์ž๋Š” ๋ฌด์กฐ๊ฑด ํ™”๋ฉด์— ์ถœ๋ ฅํ•œ๋‹ค. '('๊ฐ€ ๋‚˜์˜ค๋ฉด stack์— push ํ•œ๋‹ค. ')'๊ฐ€ ๋‚˜์˜ค๋ฉด '('๊ฐ€ ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ stack์„ ๋น„์šฐ๋ฉฐ ์ถœ๋ ฅํ•œ ๋’ค, ๋งˆ์ง€๋ง‰ '('๋„ ์ถœ๋ ฅ ์—†์ด pop ํ•ด์ค€๋‹ค. ์—ฐ์‚ฐ์ž๊ฐ€ ๋‚˜์™”์„ ๋•Œ stack์— top์— ์ž์‹ ๋ณด๋‹ค ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๊ฐ™๊ฑฐ๋‚˜ ๋†’์€ ์—ฐ์‚ฐ์ž๊ฐ€ ์žˆ์œผ๋ฉด ๊ทธ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 10.
  • [BOJ] ํ–‰์šด์˜ ๋ฐ”ํ€ด(2840) [๋ฐฑ์ค€(BOJ)] ํ–‰์šด์˜ ๋ฐ”ํ€ด(2840) C++ ๋ฌธ์ œ : BOJ_2840๋ฒˆ ํ–‰์šด์˜ ๋ฐ”ํ€ด ๋ฌธ์ œ ์„ค๋ช… ๊ตฌํ˜„ ์ €์—๊ฒŒ๋Š” ์–ด๋ ค์šด ๊ตฌํ˜„ ๋ฌธ์ œ์˜€์Šต๋‹ˆ๋‹ค. N๊ฐœ์˜ ์ˆซ์ž๊ฐ€ ์›ํ˜•์œผ๋กœ ์“ฐ์—ฌ์žˆ๋Š” ์›ํ˜• ํŒ์„ ํ•ญ์ƒ ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ๋Œ๋ฆฝ๋‹ˆ๋‹ค. ์ด๋•Œ ๋Œ์•„๊ฐ„ ์นธ์˜ ์ˆ˜์™€ ๊ฐ€๋ฆฌํ‚ค๋Š” ์นธ์— ์“ฐ์—ฌ์žˆ๋Š” ์•ŒํŒŒ๋ฒณ ๋ฌธ์ž๊ฐ€ K ๋ฒˆ ์ž…๋ ฅ๋ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ๋งˆ์ง€๋ง‰์œผ๋กœ ๊ฐ€๋ฆฌํ‚ค๋Š” ์นธ๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ์›ํ˜•์˜ ์•ŒํŒŒ๋ฒณ์„ ์ถœ๋ ฅํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Solution ์ €๋Š” ์šฐ์„  ํฌ๊ธฐ์— ๋งž๋Š” ๋ฒกํ„ฐ ๋ฐฐ์—ด์„ ํ• ๋‹นํ–ˆ์Šต๋‹ˆ๋‹ค. ๋˜ ์›ํ˜• ํŒ์„ ํ•˜๋‚˜์˜ ๋ฐฐ์—ด๋กœ ์ƒ๊ฐํ–ˆ๊ณ , ์ˆœํšŒ ์‹œ์ผฐ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ ์›ํ˜• ํŒ์ด ์‹œ๊ณ„๋ฐฉํ–ฅ์œผ๋กœ ๋Œ์•„๊ฐ„๋‹ค๋Š” ๊ฒƒ์€ ๋ฐฐ์—ด์˜ ์ž…์žฅ์—์„  ๋งˆ์ด๋„ˆ์Šค๋กœ ๋„๋Š” ๊ฒƒ์ด๊ธฐ ๋•Œ๋ฌธ์— ํšŒ์ „ํ•œ ์นธ ์ˆ˜๋งŒํผ ๋งˆ์ด๋„ˆ์Šค๋ฅผ ํ•˜์—ฌ ๋ฌธ์ž๋ฅผ ๋„ฃ์–ด์ฃผ์—ˆ์Šต๋‹ˆ๋‹ค. ๋ฌธ์ œ๊ฐ€ ์–ด๋ ค์› ๋˜ ์ด์œ ๋Š” ์ค‘๋ณต๋œ ๊ฐ’์„ ์ฒ˜๋ฆฌํ•˜๋Š” ๊ฒƒ์ด์—ˆ์Šต๋‹ˆ๋‹ค. ๋ฌธ.. ๊ณต๊ฐ์ˆ˜ 0 ๋Œ“๊ธ€์ˆ˜ 0 2022. 3. 10.
    ๋ฌธ์˜์•ˆ๋‚ด
    • ํ‹ฐ์Šคํ† ๋ฆฌ
    • ๋กœ๊ทธ์ธ
    • ๊ณ ๊ฐ์„ผํ„ฐ

    ํ‹ฐ์Šคํ† ๋ฆฌ๋Š” ์นด์นด์˜ค์—์„œ ์‚ฌ๋ž‘์„ ๋‹ด์•„ ๋งŒ๋“ญ๋‹ˆ๋‹ค.

    ยฉ Kakao Corp.