DevLog ๐Ÿ“จ 24

[DevLog][CSAPP] 9์žฅ 9.9 malloc lab ๋™์ ํ• ๋‹น๊ธฐ ๊ตฌํ˜„

9.9 ๋™์  ๋ฉ”๋ชจ๋ฆฌ ํ• ๋‹น ๋™์  ๋ฉ”๋ชจ๋ฆฌ ํ• ๋‹น์„ ํ•˜๋ฉด ์–ด๋–ค ์ผ์ด ์ผ์–ด๋‚˜๋Š”๊ฐ€: ๋Ÿฐํƒ€์ž„ ๋ฉ”๋ชจ๋ฆฌ ์ด๋ฏธ์ง€์— ์žˆ๋Š” heap์˜์—ญ์ด ์œ„๋กœ ์ƒ์Šนํ•˜๋Š” ํ˜•ํƒœ๋กœ ๋Š˜์–ด๋‚œ๋‹ค. ์ด๋•Œ ํž™์˜ ํƒ‘ ๋ถ€๋ถ„์„ ๊ฐ€๋ฆฌํ‚ค๋Š” ํฌ์ธํ„ฐ๋ฅผ brk๋ผ๊ณ  ํ•œ๋‹ค. ๋™์  ๋ฉ”๋ชจ๋ฆฌ ํ• ๋‹น๊ธฐ์˜ ๊ตฌ๋ถ„: ๋ช…์‹œ์  ํ• ๋‹น๊ธฐ๊ฐ€ ์žˆ๊ณ  ๋ฌต์‹œ์  ํ• ๋‹น๊ธฐ๊ฐ€ ์žˆ๋‹ค. ๋ช…์‹œ์  ํ• ๋‹น๊ธฐ๋Š” ์ฝ”๋“œ ๋‚ด์—์„œ ํŠน์ •ํ•œ ์–‘์˜ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ํ• ๋‹น๋ฐ›๊ณ  ํ•ด์ œํ•  ๋•Œ ์‚ฌ์šฉํ•œ๋‹ค. (c์—์„œ์˜ malloc, free์™€ c++์˜ new, delete๊ฐ€ ์ด์— ํ•ด๋‹นํ•œ๋‹ค.) ๋ฌต์‹œ์  ํ• ๋‹น๊ธฐ๋Š” ํ”„๋กœ๊ทธ๋žจ์ด ์ข…๋ฃŒ๋  ๋•Œ์™€ ๊ฐ™์ด ๋ธ”๋ก๋“ค์„ ๋”์ด์ƒ ์‚ฌ์šฉํ•˜์ง€ ์•Š์„ ๋•Œ ์ž๋™์œผ๋กœ ํ• ๋‹น ํ•ด์ œํ•ด ์ค€๋‹ค. ๋‹ค๋ฅธ ๋ง๋กœ๋Š” garbage collector๋ผ๊ณ  ํ•œ๋‹ค 9.9.1. malloc๊ณผ freeํ•จ์ˆ˜ 01) malloc๊ณผ free malloc์€ C์˜ ํ‘œ์ค€ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์—..

DevLog ๐Ÿ“จ 2023.09.24

[DevLog][CSAPP] 9์žฅ ๊ฐ€์ƒ๋ฉ”๋ชจ๋ฆฌ (9.1~9.4)

์ฑ…์„ ์ฝ์œผ๋ฉฐ ํ๋ฆ„์„ ์ •๋ฆฌ.. ๊ฐ€์ƒ๋ฉ”๋ชจ๋ฆฌ Virtual Memory ๊ฐ€์ƒ๋ฉ”๋ชจ๋ฆฌ๋Š” '์‚ฌ์šฉ์ž๊ฐ€ ํ•˜๋‚˜์˜ ํฐ ๋ฉ”์ธ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ ๊ฐ™๋„๋ก ๋Š๋ผ๊ฒŒ๋”' ์‹ค์ œ ์‚ฌ์šฉ๊ฐ€๋Šฅํ•œ ์ €์žฅ ์ž์›์„ ์ถ”์ƒํ™”ํ•˜๋Š” ๋ฉ”๋ชจ๋ฆฌ ๊ด€๋ฆฌ ๊ธฐ๋ฒ•์ด๋‹ค. ๋ฉ”์ธ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ๋””์Šคํฌ์— ์ €์žฅ๋œ ์ฃผ์†Œ๊ณต๊ฐ„์˜ ์บ์‹œ๋กœ ์ทจ๊ธ‰ํ•˜์—ฌ ๋ฉ”์ธ ๋ฉ”๋ชจ๋ฆฌ ๋‚ด ํ™œ์„ฑํ™”๋œ ์˜์—ญ๋งŒ ์œ ์ง€ํ•˜๊ณ , ๋ฐ์ดํ„ฐ๋ฅผ ๋””์Šคํฌ์™€ ๋ฉ”๋ชจ๋ฆฌ ๊ฐ„์— ํ•„์š”ํ•œ ๊ฒฝ์šฐ์—๋งŒ ์ „๋‹ฌํ•œ๋‹ค. ๊ฐ ํ”„๋กœ์„ธ์Šค์— ํ†ต์ผ๋œ ์ฃผ์†Œ๊ณต๊ฐ„์„ ์ œ๊ณตํ•˜์—ฌ ๋ฉ”๋ชจ๋ฆฌ ๊ด€๋ฆฌ๋ฅผ ๋‹จ์ˆœํ™”ํ•œ๋‹ค. ๊ฐ ํ”„๋กœ์„ธ์Šค์˜ ์ฃผ์†Œ๊ณต๊ฐ„์„ ๋‹ค๋ฅธ ํ”„๋กœ์„ธ์Šค์— ์˜ํ•œ ์†์ƒ์œผ๋กœ๋ถ€ํ„ฐ ๋ณดํ˜ธํ•œ๋‹ค. 9.1. ๋ฌผ๋ฆฌ ๋ฐ ๊ฐ€์ƒ์ฃผ์†Œ ๋ฐฉ์‹ 01) ๋ฌผ๋ฆฌ์ฃผ์†Œ ๋ฐฉ์‹ ๋ฉ”๋ชจ๋ฆฌ์— ์ ‘๊ทผํ•˜๋Š” ๊ฒƒ์€ ๋ฌผ๋ฆฌ์ฃผ์†Œ ๋ฐฉ์‹์ด ์žˆ๊ณ  ๊ฐ€์ƒ์ฃผ์†Œ ๋ฐฉ์‹์ด ์žˆ๋‹ค. ๋ฌผ๋ฆฌ์ฃผ์†Œ ๋ฐฉ์‹์€ ๋ฉ”๋ชจ๋ฆฌ์˜ ์ฃผ์†Œ๋ฅผ ๊ทธ๋Œ€๋กœ ์‚ฌ์šฉํ•˜๋Š” ๊ฒƒ์œผ๋กœ, ์ฃผ์†Œ 0์— 1๋ฐ”์ดํŠธ..

DevLog ๐Ÿ“จ 2023.09.10

[DevLog][DS]Red Black Tree: Operation

Red Black Tree 1. Concept [revisited] ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์„ฑ์งˆ์„ ๋งŒ์กฑํ•˜๋Š” ์ด์ง„ ๊ฒ€์ƒ‰ ํŠธ๋ฆฌ BST ๋ชจ๋“  ๋…ธ๋“œ๋Š” red or black root ๋…ธ๋“œ๋Š” black leaf (nil)๋…ธ๋“œ๋Š” black red ๋…ธ๋“œ์˜ ์ž์‹์€ black ํ•œ ๋…ธ๋“œ์—์„œ leaf(nil)๋กœ ๊ฐ€๋Š” ๊ฐ ๊ฒฝ๋กœ์— ํฌํ•จ๋œ black ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๋Š” ๋ชจ๋‘ ๊ฐ™๋‹ค. 2. Operations typedef enum {RBTREE_BLACK, RBTREE_RED} color_t; typedef int key_t; typedef struct node_t { key_t key; color_t color; struct node_t* parent; struct node_t* left; struct node_t* right; } typede..

[DevLog][DS] Red Black Tree: concept

Red Black Tree ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์„ฑ์งˆ์„ ๋งŒ์กฑํ•˜๋Š” ์ด์ง„ ๊ฒ€์ƒ‰ ํŠธ๋ฆฌ ๋ชจ๋“  ๋…ธ๋“œ๋Š” ๋ ˆ๋“œ๋‚˜ ๋ธ”๋ž™ ๋ฃจํŠธ๋Š” ๋ธ”๋ž™ ๋ฆฌํ”„(NIL)๋Š” ๋ธ”๋ž™ ๋ ˆ๋“œ ๋…ธ๋“œ์˜ ์ž์‹์€ ๋ชจ๋‘ ๋ธ”๋ž™ ํ•œ ๋…ธ๋“œ๋กœ๋ถ€ํ„ฐ ๊ทธ ์ž์†์ธ ๋ฆฌํ”„ ๋…ธ๋“œ๋กœ๊นŒ์ง€ ๊ฐ€๋Š” ๊ฒฝ๋กœ์— ํฌํ•จ๋œ ๋ธ”๋ž™ ๋…ธ๋“œ์˜ ๊ฐœ์ˆ˜๊ฐ€ ๊ฐ™์Œ ๋ ˆ๋“œ ๋ธ”๋ž™ ํŠธ๋ฆฌ๋Š” ์ด์ง„ ๊ฒ€์ƒ‰ ํŠธ๋ฆฌ๋กœ์„œ, ๊ฐ ๋…ธ๋“œ ๋‹น ํ•œ ๋น„ํŠธ์˜ ์ถ”๊ฐ€ ๋ฉ”๋ชจ๋ฆฌ์— ๋…ธ๋“œ์˜ ์ƒ‰๊น”(๋ ˆ๋“œ, ๋ธ”๋ž™)์„ ์ €์žฅํ•œ๋‹ค. ๋ฃจํŠธ์—์„œ ๋ฆฌํ”„๊นŒ์ง€์˜ ๊ฒฝ๋กœ์— ๋‚˜ํƒ€๋‚˜๋Š” ๋…ธ๋“œ์˜ ์ƒ‰์„ ์ œํ•œํ•จ์œผ๋กœ์จ ๊ทธ๋Ÿฌํ•œ ๊ฒฝ๋กœ ์ค‘ ์–ด๋– ํ•œ ๊ฒƒ๋„ ๋‹ค๋ฅธ ๊ฒƒ๋ณด๋‹ค ๋‘ ๋ฐฐ ์ด์ƒ ๊ธธ์ง€ ์•Š์Œ์„ ๋ณด์žฅํ•  ์ˆ˜ ์žˆ๋‹ค. ์ด๋กœ์จ ๊ทผ์‚ฌ์ ์œผ๋กœ ๊ท ํ˜•์„ ์ด๋ฃฌ ํŠธ๋ฆฌ ๊ฐ€ ๋œ๋‹ค. ๊ฒฝ๊ณ„๋…ธ๋“œ sentinel ๊ฐ ๋…ธ๋“œ๋งˆ๋‹ค ๋ฆฌํ”„๋…ธ๋“œ๋ฅผ ๋ชจ๋‘ NIL๋กœ ๋ถ™์—ฌ์ฃผ๋Š” ๋Œ€์‹ , ์ด๋ฅผ ํ‘œํ˜„ํ•˜๋Š” ํ•˜๋‚˜์˜ ๋…ธ๋“œ๋งŒ์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š”๋ฐ ์ด๋ฅผ ๊ฒฝ๊ณ„๋…ธ๋“œ(sentinel)..

[DevLog] 2์ง„์ˆ˜ ํ‘œํ˜„์—์„œ 1์˜ ๊ฐœ์ˆ˜ ์„ธ๊ธฐ

2์ง„์ˆ˜ ํ‘œํ˜„์—์„œ 1์˜ ๊ฐœ์ˆ˜๋Š” ์ผ๋ฐ˜์ ์œผ๋กœ 2๋กœ ๋‚˜๋ˆ„์–ด์ฃผ๊ณ , ๊ทธ ๋‚˜๋จธ์ง€๋ฅผ ์นด์šดํŒ…ํ•˜๋ฉฐ ์…€ ์ˆ˜ ์žˆ๋‹ค. ์‹œ๊ฐ„๋ณต์žก๋„ $O(logN)$ def func(N): cnt = 0 while N: cnt += N % 2 N //= 2 return cnt bitwise ์—ฐ์‚ฐ์ž๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ์ด์™€ ์œ ์‚ฌํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ 1์˜ ๊ฐœ์ˆ˜๋ฅผ ์…€ ์ˆ˜ ์žˆ๋‹ค. ์ฃผ์–ด์ง„ ์ˆ˜ N์˜ ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ๋น„ํŠธ๊ฐ€ 1์ธ์ง€ ํ™•์ธํ•˜๊ณ , N์„ ํ•˜๋‚˜์”ฉ right shiftํ•˜๋ฉด์„œ 1์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ผ๋‹ค. ์ด๋Š” N์˜ ๋น„ํŠธ์ˆ˜๋งŒํผ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฐ๋‹ค. ์‹œ๊ฐ„๋ณต์žก๋„ $O(logN)$ def func(N): cnt = 0 while N: cnt += N & 1 # ํ˜„์žฌ ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ ๋น„ํŠธ๊ฐ€ 1์ธ์ง€ ํ™•์ธ N >>= 1 # N์„ ์˜ค๋ฅธ์ชฝ์œผ๋กœ 1 ๋น„ํŠธ์”ฉ ์ด๋™ํ•˜์—ฌ ๋‹ค์Œ ๋น„ํŠธ ํ™•์ธ return cnt ์ด๋ณด๋‹ค ๋” ..

DevLog ๐Ÿ“จ 2023.08.30

[DevLog][Baekjoon] 1655: ๊ฐ€์šด๋ฐ๋ฅผ ๋งํ•ด์š”

01) ๋ฌธ์ œ ๋ฐฑ์ค€์ด๋Š” ๋™์ƒ์—๊ฒŒ "๊ฐ€์šด๋ฐ๋ฅผ ๋งํ•ด์š”" ๊ฒŒ์ž„์„ ๊ฐ€๋ฅด์ณ์ฃผ๊ณ  ์žˆ๋‹ค. ๋ฐฑ์ค€์ด๊ฐ€ ์ •์ˆ˜๋ฅผ ํ•˜๋‚˜์”ฉ ์™ธ์น ๋•Œ๋งˆ๋‹ค ๋™์ƒ์€ ์ง€๊ธˆ๊นŒ์ง€ ๋ฐฑ์ค€์ด๊ฐ€ ๋งํ•œ ์ˆ˜ ์ค‘์—์„œ ์ค‘๊ฐ„๊ฐ’์„ ๋งํ•ด์•ผ ํ•œ๋‹ค. ๋งŒ์•ฝ, ๊ทธ๋™์•ˆ ๋ฐฑ์ค€์ด๊ฐ€ ์™ธ์นœ ์ˆ˜์˜ ๊ฐœ์ˆ˜๊ฐ€ ์ง์ˆ˜๊ฐœ๋ผ๋ฉด ์ค‘๊ฐ„์— ์žˆ๋Š” ๋‘ ์ˆ˜ ์ค‘์—์„œ ์ž‘์€ ์ˆ˜๋ฅผ ๋งํ•ด์•ผ ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ๋ฐฑ์ค€์ด๊ฐ€ ๋™์ƒ์—๊ฒŒ 1, 5, 2, 10, -99, 7, 5๋ฅผ ์ˆœ์„œ๋Œ€๋กœ ์™ธ์ณค๋‹ค๊ณ  ํ•˜๋ฉด, ๋™์ƒ์€ 1, 1, 2, 2, 2, 2, 5๋ฅผ ์ฐจ๋ก€๋Œ€๋กœ ๋งํ•ด์•ผ ํ•œ๋‹ค. ๋ฐฑ์ค€์ด๊ฐ€ ์™ธ์น˜๋Š” ์ˆ˜๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ๋™์ƒ์ด ๋งํ•ด์•ผ ํ•˜๋Š” ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…/์ถœ๋ ฅ ์ฒซ์งธ ์ค„์—๋Š” ๋ฐฑ์ค€์ด๊ฐ€ ์™ธ์น˜๋Š” ์ •์ˆ˜์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. N์€ 1๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™๊ณ , 100,000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค. ๊ทธ ๋‹ค์Œ N์ค„์— ๊ฑธ์ณ์„œ ๋ฐฑ์ค€์ด๊ฐ€ ์™ธ์น˜๋Š” ์ •์ˆ˜..

[DevLog][Baekjoon] 8983: ์‚ฌ๋ƒฅ๊พผ

01) ๋ฌธ์ œ KOI ์‚ฌ๋ƒฅํ„ฐ์—๋Š” N ๋งˆ๋ฆฌ์˜ ๋™๋ฌผ๋“ค์ด ๊ฐ๊ฐ ํŠน์ •ํ•œ ์œ„์น˜์— ์‚ด๊ณ  ์žˆ๋‹ค. ์‚ฌ๋ƒฅํ„ฐ์— ์˜จ ์‚ฌ๋ƒฅ๊พผ์€ ์ผ์ง์„  ์ƒ์— ์œ„์น˜ํ•œ M ๊ฐœ์˜ ์‚ฌ๋Œ€(์ด์„ ์˜๋Š” ์žฅ์†Œ)์—์„œ๋งŒ ์‚ฌ๊ฒฉ์ด ๊ฐ€๋Šฅํ•˜๋‹ค. ํŽธ์˜์ƒ, ์ผ์ง์„ ์„ x-์ถ•์ด๋ผ ๊ฐ€์ •ํ•˜๊ณ , ์‚ฌ๋Œ€์˜ ์œ„์น˜ x1, x2, ..., xM์€ x-์ขŒํ‘œ ๊ฐ’์ด๋ผ๊ณ  ํ•˜์ž. ๊ฐ ๋™๋ฌผ์ด ์‚ฌ๋Š” ์œ„์น˜๋Š” (a1, b1), (a2, b2), ..., (aN, bN)๊ณผ ๊ฐ™์ด x,y-์ขŒํ‘œ ๊ฐ’์œผ๋กœ ํ‘œ์‹œํ•˜์ž. ๋™๋ฌผ์˜ ์œ„์น˜๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ๋ชจ๋“  ์ขŒํ‘œ ๊ฐ’์€ ์–‘์˜ ์ •์ˆ˜์ด๋‹ค. ์‚ฌ๋ƒฅ๊พผ์ด ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ด์˜ ์‚ฌ์ •๊ฑฐ๋ฆฌ๊ฐ€ L์ด๋ผ๊ณ  ํ•˜๋ฉด, ์‚ฌ๋ƒฅ๊พผ์€ ํ•œ ์‚ฌ๋Œ€์—์„œ ๊ฑฐ๋ฆฌ๊ฐ€ L ๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์œ„์น˜์˜ ๋™๋ฌผ๋“ค์„ ์žก์„ ์ˆ˜ ์žˆ๋‹ค๊ณ  ํ•œ๋‹ค. ๋‹จ, ์‚ฌ๋Œ€์˜ ์œ„์น˜ xi์™€ ๋™๋ฌผ์˜ ์œ„์น˜ (aj, bj) ๊ฐ„์˜ ๊ฑฐ๋ฆฌ๋Š” |xi-aj| + bj๋กœ ๊ณ„์‚ฐํ•œ๋‹ค. ์˜ˆ๋ฅผ..

[DevLog][Baekjoon] 2110: ๊ณต์œ ๊ธฐ ์„ค์น˜

01) ๋ฌธ์ œ ๋„ํ˜„์ด์˜ ์ง‘ N๊ฐœ๊ฐ€ ์ˆ˜์ง์„  ์œ„์— ์žˆ๋‹ค. ๊ฐ๊ฐ์˜ ์ง‘์˜ ์ขŒํ‘œ๋Š” x1, ..., xN์ด๊ณ , ์ง‘ ์—ฌ๋Ÿฌ๊ฐœ๊ฐ€ ๊ฐ™์€ ์ขŒํ‘œ๋ฅผ ๊ฐ€์ง€๋Š” ์ผ์€ ์—†๋‹ค. ๋„ํ˜„์ด๋Š” ์–ธ์ œ ์–ด๋””์„œ๋‚˜ ์™€์ดํŒŒ์ด๋ฅผ ์ฆ๊ธฐ๊ธฐ ์œ„ํ•ด์„œ ์ง‘์— ๊ณต์œ ๊ธฐ C๊ฐœ๋ฅผ ์„ค์น˜ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ์ตœ๋Œ€ํ•œ ๋งŽ์€ ๊ณณ์—์„œ ์™€์ดํŒŒ์ด๋ฅผ ์‚ฌ์šฉํ•˜๋ ค๊ณ  ํ•˜๊ธฐ ๋•Œ๋ฌธ์—, ํ•œ ์ง‘์—๋Š” ๊ณต์œ ๊ธฐ๋ฅผ ํ•˜๋‚˜๋งŒ ์„ค์น˜ํ•  ์ˆ˜ ์žˆ๊ณ , ๊ฐ€์žฅ ์ธ์ ‘ํ•œ ๋‘ ๊ณต์œ ๊ธฐ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ€๋Šฅํ•œ ํฌ๊ฒŒ ํ•˜์—ฌ ์„ค์น˜ํ•˜๋ ค๊ณ  ํ•œ๋‹ค. C๊ฐœ์˜ ๊ณต์œ ๊ธฐ๋ฅผ N๊ฐœ์˜ ์ง‘์— ์ ๋‹นํžˆ ์„ค์น˜ํ•ด์„œ, ๊ฐ€์žฅ ์ธ์ ‘ํ•œ ๋‘ ๊ณต์œ ๊ธฐ ์‚ฌ์ด์˜ ๊ฑฐ๋ฆฌ๋ฅผ ์ตœ๋Œ€๋กœ ํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ž…/์ถœ๋ ฅ ์ฒซ์งธ ์ค„์— ์ง‘์˜ ๊ฐœ์ˆ˜ N (2 ≤ N ≤ 200,000)๊ณผ ๊ณต์œ ๊ธฐ์˜ ๊ฐœ์ˆ˜ C (2 ≤ C ≤ N)์ด ํ•˜๋‚˜ ์ด์ƒ์˜ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ N๊ฐœ์˜ ์ค„์—๋Š” ์ง‘์˜ ์ขŒํ‘œ..

[DevLog][Baekjoon] 2261: ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋‘ ์ 

01) ๋ฌธ์ œ 2์ฐจ์› ํ‰๋ฉด์ƒ์— n๊ฐœ์˜ ์ ์ด ์ฃผ์–ด์กŒ์„ ๋•Œ, ์ด ์ ๋“ค ์ค‘ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋‘ ์ ์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ n(2 ≤ n ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ n๊ฐœ์˜ ์ค„์—๋Š” ์ฐจ๋ก€๋กœ ๊ฐ ์ ์˜ x, y์ขŒํ‘œ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ๊ฐ์˜ ์ขŒํ‘œ๋Š” ์ ˆ๋Œ“๊ฐ’์ด 10,000์„ ๋„˜์ง€ ์•Š๋Š” ์ •์ˆ˜์ด๋‹ค. ์—ฌ๋Ÿฌ ์ ์ด ๊ฐ™์€ ์ขŒํ‘œ๋ฅผ ๊ฐ€์งˆ ์ˆ˜๋„ ์žˆ๋‹ค. ์˜ˆ์ œ ์ž…/์ถœ๋ ฅ 4 0 0 10 10 0 10 10 0 # output is 10002) ํ’€์ด ํ‰๋ฉด์„ ๋ถ„ํ• ํ•œ๋‹ค ๋ถ„ํ• ๋œ ํ‰๋ฉด์—์„œ ์ตœ์†Œ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ๋Š”๋‹ค ์„œ๋กœ ๋ถ„ํ• ๋˜์–ด ์žˆ๋Š” ์ ๋“ค ์ค‘์—์„œ ์ตœ์†Œ ๊ฑฐ๋ฆฌ๊ฐ€ ๋  ์ˆ˜ ์žˆ๋Š” ์ ๋“ค๋งŒ ํƒ์ƒ‰ํ•˜์—ฌ ์ตœ์†Œ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐฑ์‹ ํ•œ๋‹ค. ์ด์ „ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ˆ˜์—…์—์„œ ๋ถ„๋ช…ํžˆ ์ ‘ํ–ˆ๋˜ ๋ฌธ์ œ์ธ๋ฐ๋„ ๋ฐ”๋กœ ๊ตฌํ˜„์ด ๋– ์˜ค๋ฅด์ง€ ์•Š์•˜๋‹ค. ์œ„์™€ ๊ฐ™์€ ํ๋ฆ„์œผ๋กœ divide/combine ..

[DevLog][Baekjoon] 1629: ๊ณฑ์…ˆ

[1629] ๊ณฑ์…ˆ 1) ๋ฌธ์ œ ์ž์—ฐ์ˆ˜ A๋ฅผ B๋ฒˆ ๊ณฑํ•œ ์ˆ˜๋ฅผ ์•Œ๊ณ  ์‹ถ๋‹ค. ๋‹จ ๊ตฌํ•˜๋ ค๋Š” ์ˆ˜๊ฐ€ ๋งค์šฐ ์ปค์งˆ ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ ์ด๋ฅผ C๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ์ฒซ์งธ ์ค„์— A, B, C๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. A, B, C๋Š” ๋ชจ๋‘ 2,147,483,647 ์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋‹ค. ์ฒซ์งธ ์ค„์— A๋ฅผ B๋ฒˆ ๊ณฑํ•œ ์ˆ˜๋ฅผ C๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค. ์˜ˆ์ œ ์ž…/์ถœ๋ ฅ 10 11 12 # output is 4 2) ํ’€์ด $\ A^(x+y) = A^x \times A^y$ ์ž„์„ ์ด์šฉํ•ด ๋ถ„ํ•  ์ •๋ณต์œผ๋กœ ํ’€์–ด์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์€ ๋“ค์—ˆ๋Š”๋ฐ, ๊ตฌ์ฒด์ ์ธ ๊ตฌํ˜„๋ฐฉ๋ฒ•์ด ๋– ์˜ค๋ฅด์ง€ ์•Š์•˜๋‹ค. ๊ฒฐ๊ตญ ํ’€์ด๋ฅผ ์ฐธ๊ณ ํ–ˆ๊ณ , ํ•ต์‹ฌ์€ ๋ชจ๋“ˆ๋Ÿฌ ์—ฐ์‚ฐ์˜ ์„ฑ์งˆ์ด๋ผ๋Š” ์ ์„ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค. ๋ชจ๋“ˆ๋Ÿฌ ์—ฐ์‚ฐ์˜ ๋ถ„๋ฐฐ๋ฒ•์น™ $(A \pm B), \bmod, C ..