๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๋ฐ˜์‘ํ˜•

Algorithm16

BOJ 3273 ) ๋‘ ์ˆ˜์˜ ํ•ฉ (C++) https://www.acmicpc.net/problem/3273๋งŒ๋งŒํ•˜๊ฒŒ ๋ดค๋Š”๋ฐ ์ƒ๊ฐ๋ณด๋‹ค ์˜ค๋ž˜ ๊ฑธ๋ ธ๋‹ค.N์ด 10^6์ด๊ธฐ ๋•Œ๋ฌธ์— ๋ฌด์ž‘์ • ์ด์ค‘ for๋ฌธ์„ ๋Œ๋ ค๋ฒ„๋ฆฌ๋ฉด ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚œ๋‹ค. ai + aj = x (1 ≤ i 1000000๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๊ธฐ ๋•Œ๋ฌธ์— x - ai ๊ฐ€ ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜์ง€ ์•Š๋Š”์ง€๋„ ์ฒดํฌํ•ด ์ฃผ์–ด์•ผ ํ•œ๋‹ค๋Š”๊ฑธ ๋†“์น˜๋Š” ๋ฐ”๋žŒ์— ํ—ค๋งธ๋‹ค. #include using namespace std;int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, k; cin>>n; vector v = vector(n); vector v1 = vector(1000002); for(int i=0;i>v[i]; } ci.. 2024. 7. 17.
BOJ 15738 ) ๋’ค์ง‘๊ธฐ (C++) 15738๋ฒˆ: ๋’ค์ง‘๊ธฐ ์ฒซ์งธ ์ค„์— ๋ฐฐ์—ด A์˜ ํฌ๊ธฐ N(1 ≤ N ≤ 100,000)๊ณผ ์œ„์น˜ K(1 ≤ K ≤ N), ์—ฐ์‚ฐ์˜ ๊ฐœ์ˆ˜ M(1 ≤ M ≤ 100,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ์—๋Š” ๋ฐฐ์—ด A์— ๋“ค์–ด์žˆ๋Š” ์ˆ˜๊ฐ€ 1๋ฒˆ์งธ ์ˆ˜๋ถ€ํ„ฐ ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ๋ฐฐ์—ด์— ๋“ค์–ด์žˆ๋Š” www.acmicpc.net algorithm ํ—ค๋”์˜ reverse ํ•จ์ˆ˜๋ฅผ ์‚ฌ์šฉํ•˜๋ฉด ์‰ฝ๊ฒŒ ํ•ด๊ฒฐ์ด ๊ฐ€๋Šฅํ•œ ๋ฌธ์ œ๋‹ค. ๋ฌธ์ œ์—์„œ๋Š” ๋ฐฐ์—ด์˜ ์›์†Œ๋„ ์ž…๋ ฅํ•ด์ฃผ์ง€๋งŒ ์‹ค์ œ ๋ฌธ์ œ๋ฅผ ํ‘ธ๋Š” ๋ฐ์—๋Š” ํ•„์š”๊ฐ€ ์—†์œผ๋ฏ€๋กœ ์ž…๋ ฅ๋งŒ ๋ฐ›๊ณ  ๋ฐฐ์—ด์—๋Š” ๋ช‡ ๋ฒˆ์งธ์›์†Œ์ธ์ง€๋ฅผ ์ž…๋ ฅํ•ด์ฃผ์—ˆ๋‹ค. ๊ทธ ๋‹ค์Œ ๋“ค์–ด์˜ค๋Š” ์ž…๋ ฅ์— ๋”ฐ๋ผ reverse ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด ๋ฐฐ์—ด์„ ๋’ค์ง‘์–ด์ฃผ๊ณ  ๋งˆ์ง€๋ง‰์— ์ „์ฒด ๋ฐฐ์—ด์„ ๋Œ๋ฉด์„œ K๋ฒˆ์งธ ์›์†Œ๊ฐ€ ๋ช‡๋ฒˆ์งธ์— ์œ„์น˜ํ•˜๊ณ  ์žˆ๋Š”์ง€๋ฅผ ์ถœ๋ ฅํ•ด ์ฃผ๋ฉด ๋œ๋‹ค. #include #include #inclu.. 2022. 6. 20.
BOJ 15705 ) ๋‹จ์–ด ์ฐพ๊ธฐ (C++) https://www.acmicpc.net/problem/15705 15705๋ฒˆ: ๋‹จ์–ด ์ฐพ๊ธฐ N×M ํฌ๊ธฐ์˜ ํ‘œ์˜ ๊ฐ ์นธ์— ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๊ฐ€ ํ•˜๋‚˜์”ฉ ์“ฐ์—ฌ ์žˆ๋‹ค. ๋‹จ์–ด S๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ํ‘œ์— ๋‹จ์–ด S๊ฐ€ ์žˆ๋Š”์ง€ ์—†๋Š”์ง€ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค. ๋‹จ์–ด S๊ฐ€ ํ‘œ์— ์กด์žฌํ•˜๋ ค๋ฉด, ํ‘œ์˜ ํ•œ ์นธ์—์„œ ์‹œ์ž‘ www.acmicpc.net ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ๋‹ค ์‹œ๋„ํ•ด๋ณด๋ฉด ๋˜๋Š” ๊ฐ„๋‹จํ•œ ๋ฌธ์ œ๋‹ค. ๋‹จ์–ด์˜ ์ฒซ ๋ฌธ์ž์™€ ๋ฐฐ์—ด์— ์ €์žฅ๋œ ๋ฌธ์ž๊ฐ€ ๊ฐ™์œผ๋ฉด ๊ฑฐ๊ธฐ์„œ๋ถ€ํ„ฐ ํƒ์ƒ‰์„ ์‹œ์ž‘ํ•œ๋‹ค. search ํ•จ์ˆ˜์—์„œ ์‹œ์ž‘์ ์œผ๋กœ๋ถ€ํ„ฐ ์–ด๋Š ๋ฐฉํ–ฅ์œผ๋กœ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ• ์ง€๋ฅผ ์ •ํ•˜๊ณ , dfs ํ•จ์ˆ˜๋ฅผ ํ˜ธ์ถœํ•ด ํ•ด๋‹น ๋ฐฉํ–ฅ์œผ๋กœ ๊ณ„์†ํ•ด์„œ ํƒ์ƒ‰์„ ์ง„ํ–‰ํ•œ๋‹ค. ๋งˆ์ง€๋ง‰ ๋ฌธ์ž๊นŒ์ง€ ์ผ์น˜ํ•˜๋ฉด true๋ฅผ ๋ฐ˜ํ™˜ํ•˜๊ณ  ์ข…๋ฃŒํ•œ๋‹ค. #include #include #define pii pair #defi.. 2022. 6. 19.
BOJ 3190 ) ๋ฑ€ (C++) 3190๋ฒˆ: ๋ฑ€ 'Dummy' ๋ผ๋Š” ๋„์Šค๊ฒŒ์ž„์ด ์žˆ๋‹ค. ์ด ๊ฒŒ์ž„์—๋Š” ๋ฑ€์ด ๋‚˜์™€์„œ ๊ธฐ์–ด๋‹ค๋‹ˆ๋Š”๋ฐ, ์‚ฌ๊ณผ๋ฅผ ๋จน์œผ๋ฉด ๋ฑ€ ๊ธธ์ด๊ฐ€ ๋Š˜์–ด๋‚œ๋‹ค. ๋ฑ€์ด ์ด๋ฆฌ์ €๋ฆฌ ๊ธฐ์–ด๋‹ค๋‹ˆ๋‹ค๊ฐ€ ๋ฒฝ ๋˜๋Š” ์ž๊ธฐ์ž์‹ ์˜ ๋ชธ๊ณผ ๋ถ€๋”ชํžˆ๋ฉด ๊ฒŒ์ž„์ด ๋๋‚œ๋‹ค. ๊ฒŒ์ž„ www.acmicpc.net ํ์— ๋ฑ€์˜ ๋ชธ ์ขŒํ‘œ๋ฅผ ๋„ฃ์–ด์ฃผ๊ณ  ์ด๋™๋งˆ๋‹ค ๋จธ๋ฆฌ์™€ ๊ผฌ๋ฆฌ๋ฅผ ๊ด€๋ฆฌํ•ด์ค€๋‹ค. ์ฒ˜์Œ์— ์ ‘๊ทผ์„ ์ž˜๋ชปํ•ด์„œ ๋งค ์ด๋™๋งˆ๋‹ค ํ ๋‚ด๋ถ€์˜ ๋ชจ๋“  ๋ชธ์˜ ์ขŒํ‘œ๋ฅผ ์ด๋™์‹œ์ผœ์ฃผ๋ ค๊ณ  ํ•˜๋‹ค๊ฐ€ ํฌ๊ธฐํ–ˆ์—ˆ๋Š”๋ฐ ์ƒ๊ฐํ•ด๋ณด๋‹ˆ ๋จธ๋ฆฌ์™€ ๊ผฌ๋ฆฌ๋งŒ ๊ด€๋ฆฌํ•ด์ค˜๋„ ์ƒ๊ด€์—†๊ฒ ๋‹ค๋Š” ๊ฒฐ๋ก ์— ์ด๋ฅด๋ €๋‹ค. dir์ด๋ผ๋Š” ๋ณ€์ˆ˜๋ฅผ ๋‘๊ณ  ์™ผ์ชฝ ํšŒ์ „์ธ ๊ฒฝ์šฐ -1, ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํšŒ์ „์ธ ๊ฒฝ์šฐ +1์„ ํ•ด์คŒ์œผ๋กœ์จ ๋ฐฉํ–ฅ ๊ด€๋ฆฌ๋ฅผ ํ•ด์ฃผ๊ณ  cnt์™€ routeidx๋กœ ํ•ด๋‹น ํšŒ์ฐจ์— ๋ฐฉํ–ฅ ์ด๋™์ด ์ผ์–ด๋‚˜๋Š”์ง€๋ฅผ ๊ด€๋ฆฌํ•ด์คฌ๋‹ค. ๋งค ์ด๋™์—์„œ ๋‹ค์Œ ์ขŒํ‘œ์— ๊ณผ์ผ์ด ์žˆ์œผ๋ฉด ์ขŒํ‘œ๋ฅผ ํ์— ๋„ฃ.. 2022. 6. 16.
BOJ 5921 ) Escaping the Farm (C++) 5921๋ฒˆ: Escaping the Farm The cows have decided on a daring plan to escape from the clutches of Farmer John. They have managed to procure a small inflatable raft, and during the cover of night, a group of cows will board the raft and row across the river bordering the farm. The pla www.acmicpc.net ์†Œ๊ฐ€ 20๋งˆ๋ฆฌ๋ฐ–์— ๋˜์ง€ ์•Š์œผ๋ฏ€๋กœ ๋ชจ๋“  ๊ฒฝ์šฐ๋ฅผ ๊ณ ๋ คํ•ด๋„ ๋œ๋‹ค. DFS๋ฅผ ์ด์šฉํ•ด ๊ฐ ์†Œ๋ฅผ ๋ฐฐ์— ํƒœ์šธ์ง€ ๋ง์ง€๋ฅผ ๊ณ ๋ฅธ ํ›„ N๋ฒˆ์งธ ์†Œ์— ๋Œ€ํ•œ ์„ ํƒ๊นŒ์ง€ ๋๋‚˜๋ฉด ๊ฐ ์ž๋ฆฟ์ˆ˜์˜ ํ•ฉ์—์„œ ์ž๋ฆฌ์˜ฌ๋ฆผ์ด .. 2022. 6. 13.
BOJ 2428 ) ํ‘œ์ ˆ (C++) 2428๋ฒˆ: ํ‘œ์ ˆ ์ฒซ์งธ ์ค„์— ์ œ์ถœํ•œ ์†”๋ฃจ์…˜์˜ ๊ฐœ์ˆ˜ N์ด ์ฃผ์–ด์ง„๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ๊ฐ ์†”๋ฃจ์…˜ ํŒŒ์ผ์˜ ํฌ๊ธฐ size(F1), size(F2), ..., size(FN)์ด ์ฃผ์–ด์ง„๋‹ค. (1 ≤ N ≤ 100,000, 1 ≤ size(Fi) ≤ 100,000,000) ์†”๋ฃจ์…˜ ํŒŒ์ผ์˜ ํฌ๊ธฐ๋Š” ์ •์ˆ˜์ด www.acmicpc.net N์ด 10^6์ด๋ฏ€๋กœ ์Œ์„ ์ฐพ๊ธฐ ์œ„ํ•ด ์ด์ค‘ for๋ฌธ์„ ๋Œ๋ฆด ๊ฒฝ์šฐ ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋‚œ๋‹ค. binary search๋ฅผ ์จ์•ผํ•˜๊ณ  (i,j)์™€ (j,i)๋Š” ๊ฐ™์€ ์ผ€์ด์Šค ์ด๋ฏ€๋กœ i=0.9*v[n]; } int main(){ cin.tie(NULL); ios_base::sync_with_stdio(false); cin>>N; int t; for(int i=0;i>t; v.push_back(t); } sort(v... 2022. 6. 9.
๋ฐ˜์‘ํ˜•