[C++] ํˆฌ ํฌ์ธํ„ฐ(Two Pointer)
ยท
๐Ÿ“ Computer Science/โœ Algorithm
ํˆฌ ํฌ์ธํ„ฐ(Two Pointer) 1์ฐจ์› ๋ฐฐ์—ด์—์„œ ๊ฐ์ž ๋‹ค๋ฅธ ์›์†Œ๋ฅผ ๊ฐ€๋ฆฌํ‚ค๊ณ  ์žˆ๋Š” 2๊ฐœ์˜ ํฌ์ธํ„ฐ๋ฅผ ์กฐ์ž‘ํ•˜์—ฌ ์›ํ•˜๋Š” ๊ฐ’์„ ์–ป๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ๋ฌธ์ œ https://www.acmicpc.net/problem/2003 2003๋ฒˆ: ์ˆ˜๋“ค์˜ ํ•ฉ 2 ์ฒซ์งธ ์ค„์— N(1≤N≤10,000), M(1≤M≤300,000,000)์ด ์ฃผ์–ด์ง„๋‹ค. ๋‹ค์Œ ์ค„์—๋Š” A[1], A[2], …, A[N]์ด ๊ณต๋ฐฑ์œผ๋กœ ๋ถ„๋ฆฌ๋˜์–ด ์ฃผ์–ด์ง„๋‹ค. ๊ฐ๊ฐ์˜ A[x]๋Š” 30,000์„ ๋„˜์ง€ ์•Š๋Š” ์ž์—ฐ์ˆ˜์ด๋‹ค. www.acmicpc.net #include using namespace std; int arr[10000]; int main() { int N, M; cin >> N >> M; for (int i = 0; i > arr[i]; ..
[C++] next_permutation, prev_permutation
ยท
๐Ÿ“ Computer Science/โœ Algorithm
next_permutation, prev_permutation ํ•จ์ˆ˜์— ๋ฒกํ„ฐ์˜ iterator๋‚˜ ๋ฐฐ์—ด์˜ ์ฃผ์†Œ๋ฅผ ๋„ฃ์œผ๋ฉด ๋‹ค์Œ ์ˆœ์—ด(next_permutation) ๋˜๋Š” ์ด์ „ ์ˆœ์—ด(prev_permutation)์˜ ๊ฒฐ๊ณผ๊ฐ€ ๋ฒกํ„ฐ๋‚˜ ๋ฐฐ์—ด์— ์ ์šฉ๋œ๋‹ค. ๋งŒ์•ฝ ๋‹ค์Œ ๋˜๋Š” ์ด์ „ ์ˆœ์—ด์ด ์—†๋‹ค๋ฉด False๋ฅผ return ํ•œ๋‹ค. ๋ฌธ์ œ https://www.acmicpc.net/problem/10972 10972๋ฒˆ: ๋‹ค์Œ ์ˆœ์—ด ์ฒซ์งธ ์ค„์— ์ž…๋ ฅ์œผ๋กœ ์ฃผ์–ด์ง„ ์ˆœ์—ด์˜ ๋‹ค์Œ์— ์˜ค๋Š” ์ˆœ์—ด์„ ์ถœ๋ ฅํ•œ๋‹ค. ๋งŒ์•ฝ, ์‚ฌ์ „์ˆœ์œผ๋กœ ๋งˆ์ง€๋ง‰์— ์˜ค๋Š” ์ˆœ์—ด์ธ ๊ฒฝ์šฐ์—๋Š” -1์„ ์ถœ๋ ฅํ•œ๋‹ค. www.acmicpc.net #include #include using namespace std; int num[10000]; int main() { int n; cin >>..
[C++] ๋น„ํŠธ ์—ฐ์‚ฐ์ž
ยท
๐Ÿ“ Computer Science/โœ Algorithm
๋น„ํŠธ ์—ฐ์‚ฐ์ž์ •์ˆ˜ ํƒ€์ž…์˜ ํ”ผ์—ฐ์‚ฐ์ž์—๋งŒ ์ ์šฉ๋  ์ˆ˜ ์žˆ๋‹ค. ๊ธฐ๋ณธ ์›๋ฆฌA^B๋Š” ๊ฐ’์ด ๊ฐ™์œผ๋ฉด 0 ๋‹ค๋ฅด๋ฉด 1์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค.~A๋Š” -A-1๊ณผ ๊ฐ™๋‹ค.์‹œํ”„ํŠธ ์—ฐ์‚ฐ์ž์—์„œ ๋นˆ ๋น„ํŠธ์—” ๋ชจ๋‘ 0์ด ์ฑ„์›Œ์ง€์ง€๋งŒ >> ์—ฐ์‚ฐ์ž์—์„œ A๊ฐ€ ์Œ์ˆ˜์ธ ๊ฒฝ์šฐ์—” 1์ด ์ฑ„์›Œ์ง„๋‹ค. ๋ฌธ์ œhttps://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/ ์นด์นด์˜ค ์‹ ์ž… ๊ณต์ฑ„ 1์ฐจ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ ๋ฌธ์ œ ํ•ด์„ค‘๋ธ”๋ผ์ธ๋“œ’ ์ „ํ˜•์œผ๋กœ ์‹ค์‹œ๋˜์–ด ์‹œ์ž‘๋ถ€ํ„ฐ ์—„์ฒญ๋‚œ ํ™”์ œ๋ฅผ ๋ชฐ๊ณ  ์˜จ ์นด์นด์˜ค ๊ฐœ๋ฐœ ์‹ ์ž… ๊ณต์ฑ„. ๊ทธ ์ฒซ ๋ฒˆ์งธ ๊ด€๋ฌธ์ธ 1์ฐจ ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ๊ฐ€ ์ง€๋‚œ 9์›” 16์ผ(ํ† ) ์˜คํ›„ 2์‹œ๋ถ€ํ„ฐ 7์‹œ๊นŒ์ง€ ์žฅ์žฅ 5์‹œ๊ฐ„ ๋™์•ˆ ์˜จ๋ผ์ธ๏ฟฝ๏ฟฝtech.kakao.com#include using namespace std;int main(){ int n ..
๋™๊ธฐ์™€ ๋น„๋™๊ธฐ & Blocking๊ณผ Non-Blocking
ยท
๐Ÿ“ Computer Science/โœ OS
๋™๊ธฐ์™€ ๋น„๋™๊ธฐ & Blocking๊ณผ Non-Blocking 1. ๋™๊ธฐ(Synchronous)์™€ ๋น„๋™๊ธฐ(Asynchronous) ํ•จ์ˆ˜๋ฅผ ์‹คํ–‰์‹œํ‚ด๊ณผ ๋™์‹œ์— ๋ฐ˜ํ™˜ ๊ฐ’์ด ๊ธฐ๋Œ€๋˜๋Š” ๊ฒฝ์šฐ๋Š” ๋™๊ธฐ๋ผ ํ‘œํ˜„ํ•˜๊ณ  ๊ทธ๋ ‡์ง€ ์•Š์€ ๊ฒฝ์šฐ๋Š” ๋น„๋™๊ธฐ๋ผ๊ณ  ํ‘œํ˜„ํ•œ๋‹ค. ๋™๊ธฐ: ์‹คํ–‰๋˜์—ˆ์„ ๋•Œ ๊ฐ’์ด ๋ฐ˜ํ™˜๋˜๊ธฐ ์ „๊นŒ์ง€๋Š” Blocking ์ƒํƒœ์ด๋‹ค. ๋น„๋™๊ธฐ: Blocking ๋˜์ง€ ์•Š๊ณ  ์ด๋ฒคํŠธ ํ์— ๋„ฃ๊ฑฐ๋‚˜ ๋ฐฑ๊ทธ๋ผ์šด๋“œ ์Šค๋ ˆ๋“œ์—๊ฒŒ ํ•ด๋‹น task๋ฅผ ์œ„์ž„ํ•˜๊ณ  ๋‹ค์Œ ์ฝ”๋“œ๋ฅผ ์‹คํ–‰ํ•˜๋ฏ€๋กœ ๊ธฐ๋Œ€๋˜๋Š” ๊ฐ’์ด ๋ฐ”๋กœ ๋ฐ˜ํ™˜๋˜์ง€ ์•Š๋Š”๋‹ค. 2. Blocking๊ณผ Non-Blocking ๊ฐ„๋‹จํžˆ ๋งํ•ด์„œ ํ˜ธ์ถœ๋œ ํ•จ์ˆ˜๊ฐ€ ํ˜ธ์ถœํ•œ ํ•จ์ˆ˜์—๊ฒŒ ์ œ์–ด๊ถŒ์„ ๊ฑด๋„ค์ฃผ๋Š” ์œ ๋ฌด์˜ ์ฐจ์ด๋ผ๊ณ  ๋ณผ ์ˆ˜ ์žˆ๋‹ค. 1) Blocking I/O ํ”„๋กœ์„ธ์Šค(์Šค๋ ˆ๋“œ)๊ฐ€ ์ปค๋„์—๊ฒŒ ์ž…์ถœ๋ ฅ ์ž‘์—…์„ ์š”์ฒญํ•˜๋Š” recvfrom() ํ•จ..
[C++] ์ตœ๋‹จ ๊ฒฝ๋กœ(๋‹ค์ต์ŠคํŠธ๋ผ, ํ”Œ๋กœ์ด๋“œ ์™€์ƒฌ, ๋ฒจ๋งŒ ํฌ๋“œ)
ยท
๐Ÿ“ Computer Science/โœ Algorithm
์ตœ๋‹จ ๊ฒฝ๋กœ ๋‘ ์ •์  ์‚ฌ์ด์˜ ๊ฒฝ๋กœ ์ค‘ ๊ฐ„์„ ์˜ ๊ฐ€์ค‘์น˜ ํ•ฉ์ด ์ตœ์†Œ์ธ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. 1. ๋‹ค์ต์ŠคํŠธ๋ผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ฐ€์ค‘์น˜๊ฐ€ ์ ์€ ์ˆœ์„œ๋Œ€๋กœ ๊ทธ ์ •์ ์— ์—ฐ๊ฒฐ๋œ ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๋ฉด์„œ ๊ฐ’์„ ๊ฐฑ์‹ ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์Œ์˜ ๊ฐ€์ค‘์น˜๋ฅผ ๊ฐ€์ง„ ๊ฒฝ๋กœ๋Š” ๊ตฌํ•  ์ˆ˜ ์—†๋‹ค. ๊ฐ€์ค‘์น˜ ํ•ฉ์˜ ์ตœ๋Œ“๊ฐ’์€ ๊ฐ€์ค‘์น˜ ์ตœ๋Œ“๊ฐ’ * (์ •์  ๊ฐœ์ˆ˜ - 1) ์ด๋‹ค. 1) ๋ฌธ์ œ https://www.acmicpc.net/problem/1753 1753๋ฒˆ: ์ตœ๋‹จ๊ฒฝ๋กœ ์ฒซ์งธ ์ค„์— ์ •์ ์˜ ๊ฐœ์ˆ˜ V์™€ ๊ฐ„์„ ์˜ ๊ฐœ์ˆ˜ E๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1≤V≤20,000, 1≤E≤300,000) ๋ชจ๋“  ์ •์ ์—๋Š” 1๋ถ€ํ„ฐ V๊นŒ์ง€ ๋ฒˆํ˜ธ๊ฐ€ ๋งค๊ฒจ์ ธ ์žˆ๋‹ค๊ณ  ๊ฐ€์ •ํ•œ๋‹ค. ๋‘˜์งธ ์ค„์—๋Š” ์‹œ์ž‘ ์ •์ ์˜ ๋ฒˆํ˜ธ K(1≤K≤V)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์…‹์งธ ์ค„๋ถ€ํ„ฐ E๊ฐœ์˜ ์ค„์— ๊ฑธ์ณ ๊ฐ ๊ฐ„์„ ์„ ๋‚˜ํƒ€๋‚ด๋Š” ์„ธ ๊ฐœ์˜ ์ •์ˆ˜ (u, v, ..
[C++] ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS), ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS)
ยท
๐Ÿ“ Computer Science/โœ Algorithm
๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(Depth First Search)๊ณผ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(Breadth First Search) ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์€ ํ•œ ๋ฐฉํ–ฅ์œผ๋กœ ๊ณ„์† ๊ฐ€๋‹ค๊ฐ€ ๋” ์ด์ƒ ๊ฐˆ ์ˆ˜ ์—†์œผ๋ฉด ๋ถ€๋ชจ ๋…ธ๋“œ๋กœ ๋Œ์•„์™€ ๋‹ค๋ฅธ ๋ฐฉํ–ฅ์œผ๋กœ ํƒ์ƒ‰ํ•œ๋‹ค. ์ฃผ๋กœ Stack์ด๋‚˜ ์žฌ๊ท€ ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•ด ๊ตฌํ˜„ํ•œ๋‹ค. ๋ชจ๋“  ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๊ฑฐ๋‚˜ ๊ฐ€์ค‘์น˜, ์ด๋™ ๊ณผ์ •์— ์ œ์•ฝ์ด ์žˆ์„ ๊ฒฝ์šฐ์— ์‚ฌ์šฉํ•˜๋ฉด ์ข‹๋‹ค. ์ž๊ธฐ ์ž์‹ ์„ ํ˜ธ์ถœํ•˜๋Š” ์ˆœํ™˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ˜•ํƒœ๋ฅผ ๊ฐ–๊ณ  ์žˆ๋‹ค. BFS๋ณด๋‹ค ์ข€ ๋” ๊ฐ„๋‹จํ•˜๋‚˜ ๋‹จ์ˆœ ๊ฒ€์ƒ‰ ์†๋„ ์ž์ฒด๋Š” BFS๋ณด๋‹ค ๋Š๋ฆฌ๋‹ค. ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์€ ํ˜„์žฌ ๋…ธ๋“œ์—์„œ ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ๋…ธ๋“œ๋ฅผ ๋จผ์ € ๋ฐฉ๋ฌธํ•ด ํƒ์ƒ‰ํ•œ๋‹ค. ์ฃผ๋กœ Queue๋ฅผ ์ด์šฉํ•ด ๊ตฌํ˜„ํ•œ๋‹ค. ๋‘ ๋…ธ๋“œ ์‚ฌ์ด์˜ ์ตœ๋‹จ ๊ฒฝ๋กœ ํ˜น์€ ์ž„์˜์˜ ๊ฒฝ๋กœ๋ฅผ ์ฐพ๋Š” ๊ฒฝ์šฐ์— ์‚ฌ์šฉํ•˜๋ฉด ์ข‹๋‹ค. ๊ธฐ๋ณธ ์›๋ฆฌ https://www.acmicpc.n..