์ ์ฒด๋ณด๊ธฐ
-
[C++] ๋ฑ์ ๊ฐ๋ ๊ณผ STL Deque ์ฌ์ฉ๋ฒAlgorithm & Data Structure 2022. 1. 18. 22:47
๋ค์ด๊ฐ๋ฉฐ ๋ฑ(Deque)์ Double Ended Queue์ ์ฝ์๋ก ํ์ ์์ชฝ ๋์์ ์์๋ฅผ ์ถ๊ฐํ๊ฑฐ๋ ์ญ์ ๋ฅผ ํ ์ ์๋ ์๋ฃ๊ตฌ์กฐ์ด๋ค. ๊ทธ๋ฆฌ๊ณ C++ STL์ ๋ฑ์ด ๊ตฌํ๋์ด ์์ด ์ฝ๊ฒ ์ด์ฉํ ์ ์๋ค! ๋ฑ(Deque) ์ด๋? ๋ฑ(deque, "deck"๊ณผ ๋ฐ์์ด ๊ฐ์ ← double-ended queue)์ ์์ชฝ ๋์์ ์ฝ์ ๊ณผ ์ญ์ ๊ฐ ๋ชจ๋ ๊ฐ๋ฅํ ์๋ฃ ๊ตฌ์กฐ์ ํ ํํ์ด๋ค. ๋ ๊ฐ์ ํฌ์ธํฐ๋ฅผ ์ฌ์ฉํ์ฌ, ์์ชฝ์์ ์ญ์ ์ ์ฝ์ ์ ๋ฐ์์ํฌ ์ ์๋ค. ํ์ ์คํ์ ํฉ์น ํํ๋ก ์๊ฐํ ์ ์๋ค. - ์ํค๋ฐฑ๊ณผ ๋ฑ ๋ฑ์ ๋ํด์ ์๋์ ์ฌ์ง์ ๋ณด๊ณ ์ดํดํด๋ณด์. ์ ์ฌ์ง์ ๋ณด๋ฉด ์์ 32๋ฅผ back์ ๋ฃ์ด์ ๋ฑ ์์ ์์๊ฐ 5, 17, 32๊ฐ ๋ค์ด์๊ฒ ๋๋ค. ์ฌ๊ธฐ์ front์ ์๋ ์์ 5๋ฅผ ์ ๊ฑฐํ๋ฉด ๋ฑ ์์ 17,..
-
[๋ฐฑ์ค(BOJ) 2164๋ฒ] ์นด๋2 (C++)PS(Problem Solving)/C++ 2022. 1. 17. 22:48
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/2164 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ ์ N(1 ≤ N ≤ 500,000)์ด ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๋จ๊ฒ ๋๋ ์นด๋์ ๋ฒํธ๋ฅผ ์ถ๋ ฅํ๋ค. ํ์ด ๋ฌธ์ ์ ์กฐ๊ฑด์ ์ ์ฝ์ด์ ํ๋ก ํ์ด์ผ ํ๋ค๋ ๊ฒ์ ํ์ ํ๋ฉด ์ฝ๊ฒ ํด๊ฒฐํ ์ ์๋ค. ๋ฌธ์ ์์ 1๋ถํฐ n๊น์ง์ ์นด๋๋ฅผ 1์ด ์ ์ผ ์๋ก ์ค๊ฒ ์์๋๋ก ๋ฐ์ผ๋ก ๋์ฌ์ ธ ์๊ณ , ์ ์ผ ์์ ์๋ ์นด๋๋ฅผ ๋ฒ๋ฆฐ๋ค๋ ๊ฒ์ ํตํด ๋จผ์ ๋ค์ด๊ฐ ๊ฒ์ด ๋จผ์ ๋์ค๋ (FIFO) ๊ตฌ์กฐ๋ฅผ ๋ ์ฌ๋ฆด ์ ์๋ค. ์์ค ์ฝ๋ #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; queue Q; for (int..
-
[๋ฐฑ์ค(BOJ) 10845๋ฒ] ํ (C++)PS(Problem Solving)/C++ 2022. 1. 17. 22:39
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/10845 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ฃผ์ด์ง๋ ๋ช ๋ น์ ์ N (1 ≤ N ≤ 10,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋ช ๋ น์ด ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ฃผ์ด์ง๋ ์ ์๋ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค. ๋ฌธ์ ์ ๋์์์ง ์์ ๋ช ๋ น์ด ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ๋ ์๋ค. ์ถ๋ ฅ ์ถ๋ ฅํด์ผํ๋ ๋ช ๋ น์ด ์ฃผ์ด์ง ๋๋ง๋ค, ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ๋ค. ํ์ด STL Queue๋ฅผ ์ดํดํ๋ฉด ์ฝ๊ฒ ํด๊ฒฐํ ์ ์๋ค! ์์ค ์ฝ๋ #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; queue Q; while (n--) { strin..
-
[C++] ํ์ ๊ฐ๋ ๊ณผ STL Queue ์ฌ์ฉ๋ฒAlgorithm & Data Structure 2022. 1. 17. 22:31
๋ค์ด๊ฐ๋ฉฐ ํ๋ ๋จผ์ ๋ค์ด๊ฐ ์์๊ฐ ๋จผ์ ๋์ค๊ฒ ๋๋ ๊ตฌ์กฐ์ฌ์ FIFO(First In First Out) ์๋ฃ๊ตฌ์กฐ๋ผ๊ณ ๋ถ๋ฅธ๋ค. ๊ทธ๋ฆฌ๊ณ C++ STL์ ํ๊ฐ ๊ตฌํ๋์ด ์์ด ์ฝ๊ฒ ์ด์ฉํ ์ ์๋ค! ํ๋ BFS, Flood Fill ์๊ณ ๋ฆฌ์ฆ์ ๋ณดํต ์ฌ์ฉํ๋ค. ํ(Queue) ๋? ํ(queue)๋ ์ปดํจํฐ์ ๊ธฐ๋ณธ์ ์ธ ์๋ฃ ๊ตฌ์กฐ์ ํ๊ฐ์ง๋ก, ๋จผ์ ์ง์ด ๋ฃ์ ๋ฐ์ดํฐ๊ฐ ๋จผ์ ๋์ค๋ FIFO(First In First Out)๊ตฌ์กฐ๋ก ์ ์ฅํ๋ ํ์์ ๋งํ๋ค. ์์ด ๋จ์ด queue๋ ํ๋ฅผ ์ฌ๋ฌ ์ผ๋ ฌ๋ก ๋์ด์ ์ฌ๋๋ค๋ก ์ด๋ฃจ์ด์ง ์ค์ ๋งํ๊ธฐ๋ ํ๋ฉฐ, ๋จผ์ ์ค์ ์ ์ฌ๋์ด ๋จผ์ ๋๊ฐ ์ ์๋ ์ํฉ์ ์ฐ์ํ๋ฉด ๋๋ค. ๋์ค์ ์ง์ด ๋ฃ์ ๋ฐ์ดํฐ๊ฐ ๋จผ์ ๋์ค๋ ์คํ๊ณผ๋ ๋ฐ๋๋๋ ๊ฐ๋ ์ด๋ค. ํ๋ฆฐํฐ์ ์ถ๋ ฅ ์ฒ๋ฆฌ๋ ์๋ ์์คํ ์ ๋ฉ์์ง ์ฒ..
-
[๋ฐฑ์ค(BOJ) 2493๋ฒ] ํ (C++)PS(Problem Solving)/C++ 2022. 1. 16. 23:23
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/2493 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ํ์ ์๋ฅผ ๋ํ๋ด๋ ์ ์ N์ด ์ฃผ์ด์ง๋ค. N์ 1 ์ด์ 500,000 ์ดํ์ด๋ค. ๋์งธ ์ค์๋ N๊ฐ์ ํ๋ค์ ๋์ด๊ฐ ์ง์ ์์ ๋์ธ ์์๋๋ก ํ๋์ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. ํ๋ค์ ๋์ด๋ 1 ์ด์ 100,000,000 ์ดํ์ ์ ์์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ์ฃผ์ด์ง ํ๋ค์ ์์๋๋ก ๊ฐ๊ฐ์ ํ๋ค์์ ๋ฐ์ฌํ ๋ ์ด์ ์ ํธ๋ฅผ ์์ ํ ํ๋ค์ ๋ฒํธ๋ฅผ ํ๋์ ๋น์นธ์ ์ฌ์ด์ ๋๊ณ ์ถ๋ ฅํ๋ค. ๋ง์ฝ ๋ ์ด์ ์ ํธ๋ฅผ ์์ ํ๋ ํ์ด ์กด์ฌํ์ง ์์ผ๋ฉด 0์ ์ถ๋ ฅํ๋ค. ํ์ด ์ด ๋ฌธ์ ๋ ์ด๋ ค์ด ๋ฌธ์ ์ฌ์ ํด๊ฒฐํ๋๋ฐ ํ๋ค์๋ค. ํ์ฌ ์ ๋ ฅํ๋ ํ์ ๋์ด๊ฐ ๊ธฐ์กด ์คํ์ ํ์ ๋์ด๋ณด๋ค ํฌ๊ฑฐ๋ ์์๋๋ฅผ ์ ์๊ฐํด์ฃผ๋ฉด ๋๋ค. ๋ง์ฝ ์คํ์ top์ด ํ..
-
[๋ฐฑ์ค(BOJ) 1874๋ฒ] ์คํ ์์ด (C++)PS(Problem Solving)/C++ 2022. 1. 16. 22:56
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1874 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ ์ค์ n (1 ≤ n ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ n๊ฐ์ ์ค์๋ ์์ด์ ์ด๋ฃจ๋ 1์ด์ n์ดํ์ ์ ์๊ฐ ํ๋์ฉ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๋ฌผ๋ก ๊ฐ์ ์ ์๊ฐ ๋ ๋ฒ ๋์ค๋ ์ผ์ ์๋ค. ์ถ๋ ฅ ์ ๋ ฅ๋ ์์ด์ ๋ง๋ค๊ธฐ ์ํด ํ์ํ ์ฐ์ฐ์ ํ ์ค์ ํ ๊ฐ์ฉ ์ถ๋ ฅํ๋ค. push์ฐ์ฐ์ +๋ก, pop ์ฐ์ฐ์ -๋ก ํํํ๋๋ก ํ๋ค. ๋ถ๊ฐ๋ฅํ ๊ฒฝ์ฐ NO๋ฅผ ์ถ๋ ฅํ๋ค. ํ์ด ๊ต์ฅํ ํด๊ฒฐํ๊ธฐ ์ด๋ ค์ด ๋ฌธ์ ์๋ค. ์์ 1๋ฒ์ ๋ณด๊ณ ๋ฌธ์ ๋ฅผ ์ดํดํด๋ณด์. 8 4 3 6 8 7 5 2 1 ์ ์ ๋ ฅํ๋ค๊ณ ํ์. ๋ฐ๋ผ์ ์ฒ์์ 4๋ฅผ ์์ด์ ๋ฃ์ด์ผ ํ๋ค. ๊ทธ ๊ณผ์ ์ ์๋์ ๊ฐ๋ค. 1 2 3 4๋ฅผ ์คํ์ push ํ๋ค. ์คํ์์ 4๋ฅผ pop ํด..
-
[๋ฐฑ์ค(BOJ) 10773๋ฒ] ์ ๋ก (C++)PS(Problem Solving)/C++ 2022. 1. 16. 22:30
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/10773 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ ๋ฒ์งธ ์ค์ ์ ์ K๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ K ≤ 100,000) ์ดํ K๊ฐ์ ์ค์ ์ ์๊ฐ 1๊ฐ์ฉ ์ฃผ์ด์ง๋ค. ์ ์๋ 0์์ 1,000,000 ์ฌ์ด์ ๊ฐ์ ๊ฐ์ง๋ฉฐ, ์ ์๊ฐ "0" ์ผ ๊ฒฝ์ฐ์๋ ๊ฐ์ฅ ์ต๊ทผ์ ์ด ์๋ฅผ ์ง์ฐ๊ณ , ์๋ ๊ฒฝ์ฐ ํด๋น ์๋ฅผ ์ด๋ค. ์ ์๊ฐ "0"์ผ ๊ฒฝ์ฐ์ ์ง์ธ ์ ์๋ ์๊ฐ ์์์ ๋ณด์ฅํ ์ ์๋ค. ์ถ๋ ฅ ์ฌ๋ฏผ์ด๊ฐ ์ต์ข ์ ์ผ๋ก ์ ์ด ๋ธ ์์ ํฉ์ ์ถ๋ ฅํ๋ค. ์ต์ข ์ ์ผ๋ก ์ ์ด๋ธ ์์ ํฉ์ 231-1๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์์ด๋ค. ํ์ด ์ ์๊ฐ 0์ธ ๊ฒฝ์ฐ์ ๊ฐ์ฅ ์ต๊ทผ์ ์ด ์๋ฅผ ์ง์์ผ ํ๋ ๋ฌธ์ ๋ค. ์คํ์ LIFO ๊ตฌ์กฐ๋ฅผ ๊ฐ์ง๊ณ ์์ผ๋ฏ๋ก ์คํ์ ์ด์ฉํ๋ฉด ํด๊ฒฐ ํ ์ ์๋ค๋ ๊ฒ์ ์ ์ ์๋ค. ์์ค ์ฝ๋ #i..
-
[๋ฐฑ์ค(BOJ) 10828๋ฒ] ์คํ (C++)PS(Problem Solving)/C++ 2022. 1. 16. 22:25
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/10828 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์ฃผ์ด์ง๋ ๋ช ๋ น์ ์ N (1 ≤ N ≤ 10,000)์ด ์ฃผ์ด์ง๋ค. ๋์งธ ์ค๋ถํฐ N๊ฐ์ ์ค์๋ ๋ช ๋ น์ด ํ๋์ฉ ์ฃผ์ด์ง๋ค. ์ฃผ์ด์ง๋ ์ ์๋ 1๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100,000๋ณด๋ค ์๊ฑฐ๋ ๊ฐ๋ค. ๋ฌธ์ ์ ๋์์์ง ์์ ๋ช ๋ น์ด ์ฃผ์ด์ง๋ ๊ฒฝ์ฐ๋ ์๋ค. ์ถ๋ ฅ ์ถ๋ ฅํด์ผํ๋ ๋ช ๋ น์ด ์ฃผ์ด์ง ๋๋ง๋ค, ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ๋ค. ํ์ด STL Stack์ ์ดํดํ๋ฉด ์ฝ๊ฒ ํด๊ฒฐ ํ ์ ์๋ค! ์์ค ์ฝ๋ #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; stack S; while (n--) { stri..