์ ์ฒด ๊ธ
-
[C++] ์คํ์ ๊ฐ๋ ๊ณผ STL Stack ์ฌ์ฉ๋ฒAlgorithm & Data Structure 2022. 1. 15. 22:46
๋ค์ด๊ฐ๋ฉฐ ์์ผ๋ก ์ธ ๊ฐ์ง ๊ด๋ จ ์๋ ์๋ฃ๊ตฌ์กฐ์ธ ์คํ, ํ, ๋ฑ์ ๋ํด์ ๋ค๋ฃฐ ๊ฒ์ด๋ค. ์คํ์ ๋จผ์ ๋ค์ด๊ฐ ์์๊ฐ ์ ์ผ ๋์ค์ ๋์ค๊ฒ ๋๋ ๊ตฌ์กฐ์ฌ์ FILO(First In Last Out) ์๋ฃ๊ตฌ์กฐ๋ผ๊ณ ๋ถ๋ฅด๊ธฐ๋ ํ๋ค. ๋ํ ๋ฐ๋๋ก ๋์ค์ ๋ค์ด๊ฐ ์์๊ฐ ์ ์ผ ๋จผ์ ๋์ค๊ฒ ๋๋ ๊ตฌ์กฐ์ด๋ฏ๋ก LIFO(Last In First Out)์ ํํ๋ฅผ ๋ ๋ ์๋ฃ๊ตฌ์กฐ์ด๊ธฐ๋ ํ๋ค. ๊ทธ๋ฆฌ๊ณ C++ STL์ ์คํ์ด ๊ตฌํ๋์ด ์์ด ์ฝ๊ฒ ์ด์ฉํ ์ ์๋ค! ์คํ(Stack) ์ด๋? ์คํ(stack)์ ์ ํ์ ์ผ๋ก ์ ๊ทผํ ์ ์๋ ๋์ด ๊ตฌ์กฐ์ด๋ค. ๊ทธ ์ ๊ทผ ๋ฐฉ๋ฒ์ ์ธ์ ๋ ๋ชฉ๋ก์ ๋์์๋ง ์ผ์ด๋๋ค. ๋๋จผ์ ๋ด๊ธฐ ๋ชฉ๋ก(Pushdown list)์ด๋ผ๊ณ ๋ ํ๋ค. ์คํ์ ํ ์ชฝ ๋์์๋ง ์๋ฃ๋ฅผ ๋ฃ๊ฑฐ๋ ๋บ ์ ์๋ ์ ํ ๊ตฌ์กฐ(LIFO - Last I..
-
[๋ฐฑ์ค(BOJ) 1158๋ฒ] ์์ธํธ์ค ๋ฌธ์ (C++)PS(Problem Solving)/C++ 2022. 1. 13. 23:05
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1158 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ N๊ณผ K๊ฐ ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์์๋๋ก ์ฃผ์ด์ง๋ค. (1 ≤ K ≤ N ≤ 5,000) ์ถ๋ ฅ ์์ ์ ๊ฐ์ด ์์ธํธ์ค ์์ด์ ์ถ๋ ฅํ๋ค. ํ์ด STL List์ erase ํจ์๊ฐ ๊ทธ ๋ค์ ์์์ ์์น๋ฅผ ๋ฐํํ๋ค๋ ๊ฒ์ ๊ธฐ์ตํ๊ณ ์์ผ๋ฉด ํด๊ฒฐ ํ ์ ์๋ ๋ฌธ์ ๋ค! ์์ค ์ฝ๋ #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; // ์ด๊ธฐ ์ธ์์. 1 ~ n๋ช int k; // ์ ๊ฑฐํ ์ฐจ๋ก cin >> n >> k; list L; for (int i = 1; i
-
[๋ฐฑ์ค(BOJ) 5397๋ฒ] ํค๋ก๊ฑฐ (C++)PS(Problem Solving)/C++ 2022. 1. 13. 22:47
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/5397 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ๊ฐ์ฐ์ด๊ฐ ์ ๋ ฅํ ์์๋๋ก ๊ธธ์ด๊ฐ L์ธ ๋ฌธ์์ด์ด ์ฃผ์ด์ง๋ค. (1 ≤ L ≤ 1,000,000) ๊ฐ์ฐ์ด๊ฐ ๋ฐฑ์คํ์ด์ค๋ฅผ ์ ๋ ฅํ๋ค๋ฉด, '-'๊ฐ ์ฃผ์ด์ง๋ค. ์ด๋ ์ปค์์ ๋ฐ๋ก ์์ ๊ธ์๊ฐ ์กด์ฌํ๋ค๋ฉด, ๊ทธ ๊ธ์๋ฅผ ์ง์ด๋ค. ํ์ดํ์ ์ ๋ ฅ์ ''๋ก ์ฃผ์ด์ง๋ค. ์ด๋๋ ์ปค์์ ์์น๋ฅผ ์์ง์ผ ์ ์๋ค๋ฉด, ์ผ์ชฝ ๋๋ ์ค๋ฅธ์ชฝ์ผ๋ก 1๋งํผ ์์ง์ธ๋ค. ๋๋จธ์ง ๋ฌธ์๋ ๋น๋ฐ๋ฒํธ์ ์ผ๋ถ์ด๋ค. ๋ฌผ๋ก , ๋์ค์ ๋ฐฑ์คํ์ด์ค๋ฅผ ํตํด์ ์ง์ธ ์๋ ์๋ค. ๋ง์ฝ ์ปค์์ ์์น๊ฐ ์ค์ ๋ง์ง๋ง์ด ์๋๋ผ๋ฉด, ์ปค์ ๋ฐ ์ปค์ ์ค๋ฅธ์ชฝ์ ์๋ ๋ชจ๋ ๋ฌธ์๋ ์ค๋ฅธ์ชฝ์ผ๋ก ํ ์นธ ์ด๋ํ๋ค. ์ถ๋ ฅ ..
-
[๋ฐฑ์ค(BOJ) 1406๋ฒ] ์๋ํฐ (C++)PS(Problem Solving)/C++ 2022. 1. 13. 22:39
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1406 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์๋ ์ด๊ธฐ์ ํธ์ง๊ธฐ์ ์ ๋ ฅ๋์ด ์๋ ๋ฌธ์์ด์ด ์ฃผ์ด์ง๋ค. ์ด ๋ฌธ์์ด์ ๊ธธ์ด๊ฐ N์ด๊ณ , ์์ด ์๋ฌธ์๋ก๋ง ์ด๋ฃจ์ด์ ธ ์์ผ๋ฉฐ, ๊ธธ์ด๋ 100,000์ ๋์ง ์๋๋ค. ๋์งธ ์ค์๋ ์ ๋ ฅํ ๋ช ๋ น์ด์ ๊ฐ์๋ฅผ ๋ํ๋ด๋ ์ ์ M(1 ≤ M ≤ 500,000)์ด ์ฃผ์ด์ง๋ค. ์ ์งธ ์ค๋ถํฐ M๊ฐ์ ์ค์ ๊ฑธ์ณ ์ ๋ ฅํ ๋ช ๋ น์ด๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๋ช ๋ น์ด๋ ์์ ๋ค ๊ฐ์ง ์ค ํ๋์ ํํ๋ก๋ง ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๋ชจ๋ ๋ช ๋ น์ด๋ฅผ ์ํํ๊ณ ๋ ํ ํธ์ง๊ธฐ์ ์ ๋ ฅ๋์ด ์๋ ๋ฌธ์์ด์ ์ถ๋ ฅํ๋ค. ํ์ด ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ํด๊ฒฐ ํ ์ ์๋ ๋ฌธ์ ๋ค. ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์ปค์๋ฅผ ์ด์ฉํ๋ ๋ฌธ์ ๊ฐ ์ฃผ๋ก ๋์จ๋ค. ๋ฐ๋ผ์ ๋ฉ๋ชจ์ฅ ๊ฐ์ ๋ฌธ์ ๋ค์ ํ์ดํ ๋ ์ฉ์ดํ๊ฒ ์ฌ์ฉ..
-
[C++] ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ๊ฐ๋ ๊ณผ STL List ์ฌ์ฉ๋ฒAlgorithm & Data Structure 2022. 1. 9. 23:33
๋ค์ด๊ฐ๋ฉฐ ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Linked List)๋ 3๊ฐ์ง ์ข ๋ฅ๊ฐ ์๋ค. ๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Singly Linked List), ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Doubly Linked List), ์ํ ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Circular Linked List)๊ฐ ์ด์ ํด๋นํ๋ค. ๊ทธ๋ฆฌ๊ณ C++ STL์ ์ฐ๊ฒฐ ๋ฆฌ์คํธ๊ฐ ๊ตฌํ๋์ด ์์ด ์์ฝ๊ฒ ์ฌ์ฉํ ์ ์๋ค! ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Linked List)๋? ์ฐ๊ฒฐ ๋ฆฌ์คํธ, ๋งํฌ๋ ๋ฆฌ์คํธ(linked list)๋ ๊ฐ ๋ ธ๋๊ฐ ๋ฐ์ดํฐ์ ํฌ์ธํฐ๋ฅผ ๊ฐ์ง๊ณ ํ ์ค๋ก ์ฐ๊ฒฐ๋์ด ์๋ ๋ฐฉ์์ผ๋ก ๋ฐ์ดํฐ๋ฅผ ์ ์ฅํ๋ ์๋ฃ ๊ตฌ์กฐ์ด๋ค. ์ด๋ฆ์์ ๋งํ๋ฏ์ด ๋ฐ์ดํฐ๋ฅผ ๋ด๊ณ ์๋ ๋ ธ๋๋ค์ด ์ฐ๊ฒฐ๋์ด ์๋๋ฐ, ๋ ธ๋์ ํฌ์ธํฐ๊ฐ ๋ค์์ด๋ ์ด์ ์ ๋ ธ๋์์ ์ฐ๊ฒฐ์ ๋ด๋นํ๊ฒ ๋๋ค. ์ฐ๊ฒฐ ๋ฆฌ์คํธ์ ์ข ๋ฅ๋ก๋ ๋จ์ผ ์ฐ๊ฒฐ ๋ฆฌ์คํธ, ์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์ค..
-
[๋ฐฑ์ค(BOJ) 3273๋ฒ] ๋ ์์ ํฉ (C++)PS(Problem Solving)/C++ 2022. 1. 7. 23:17
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/3273 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ ์์ด์ ํฌ๊ธฐ n์ด ์ฃผ์ด์ง๋ค. ๋ค์ ์ค์๋ ์์ด์ ํฌํจ๋๋ ์๊ฐ ์ฃผ์ด์ง๋ค. ์ ์งธ ์ค์๋ x๊ฐ ์ฃผ์ด์ง๋ค. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) ์ถ๋ ฅ ๋ฌธ์ ์ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค. ํ์ด ๊ต์ฅํ ๊ฐ๋จํ๊ฒ ์ ๊ทผํ๋ ๋ฌธ์ ์ธ๋ฐ ์๊ฐ ์ด๊ณผ๊ฐ ๋์ ํ ์ ์์๋ ๋ฌธ์ ์๋ค. ์๋๋ ์๋ชป๋ ์์ค ์ฝ๋์ด๋ค! // ์๋ชป๋ ์์ค ์ฝ๋! /* #include using namespace std; int number[100002]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i <..
-
[๋ฐฑ์ค(BOJ) 2577๋ฒ] ์ซ์์ ๊ฐ์ (C++)PS(Problem Solving)/C++ 2022. 1. 7. 23:04
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/2577 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค์ A, ๋์งธ ์ค์ B, ์ ์งธ ์ค์ C๊ฐ ์ฃผ์ด์ง๋ค. A, B, C๋ ๋ชจ๋ 100๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 1,000๋ณด๋ค ์์ ์์ฐ์์ด๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์๋ A × B × C์ ๊ฒฐ๊ณผ์ 0 ์ด ๋ช ๋ฒ ์ฐ์๋์ง ์ถ๋ ฅํ๋ค. ๋ง์ฐฌ๊ฐ์ง๋ก ๋์งธ ์ค๋ถํฐ ์ด ๋ฒ์งธ ์ค๊น์ง A × B × C์ ๊ฒฐ๊ณผ์ 1๋ถํฐ 9๊น์ง์ ์ซ์๊ฐ ๊ฐ๊ฐ ๋ช ๋ฒ ์ฐ์๋์ง ์ฐจ๋ก๋ก ํ ์ค์ ํ๋์ฉ ์ถ๋ ฅํ๋ค. ํ์ด ๋จ์ํ๊ฒ ํ์ดํ ์ ์๋ ๋ฌธ์ ์ด๋ค. ๊ฐ ์ซ์์ ๊ฐ์๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด์ ํ๋ ๋ง๋ค์ด์ ํ์ดํ๋ฉด ๋๋ค! ์์ค ์ฝ๋ #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie..
-
[๋ฐฑ์ค(BOJ) 1919๋ฒ] ์ ๋๊ทธ๋จ ๋ง๋ค๊ธฐ (C++)PS(Problem Solving)/C++ 2022. 1. 7. 22:59
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1919 ๋ฌธ์ ์ ๋ณด ์ ๋ ฅ ์ฒซ์งธ ์ค๊ณผ ๋์งธ ์ค์ ์์ด ๋จ์ด๊ฐ ์๋ฌธ์๋ก ์ฃผ์ด์ง๋ค. ๊ฐ๊ฐ์ ๊ธธ์ด๋ 1,000์๋ฅผ ๋์ง ์์ผ๋ฉฐ, ์ ์ด๋ ํ ๊ธ์๋ก ์ด๋ฃจ์ด์ง ๋จ์ด๊ฐ ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๋ต์ ์ถ๋ ฅํ๋ค. ํ์ด string ์๋ฃํ์ ํตํด ๋ฌธ์์ด 2๊ฐ๋ฅผ ์ ๋ ฅ ๋ฐ์ ํ์ ๊ฐ๊ฐ ์ํ๋ฒณ์ ๊ฐ์๋ฅผ ๋ฐฐ์ด์ ์ ์ฅํ๋ค. ๊ทธ๋ฆฌ๊ณ ์ํ๋ฒณ์ ๊ฐ์๊ฐ ๋ค๋ฅธ ๋งํผ ๋ํด์ฃผ๋ฉด ์ ๋๊ทธ๋จ ๊ด๊ณ์ ์๋๋ก ๋ง๋ค๊ธฐ ์ํด ์ ๊ฑฐํด์ผ ํ๋ ์ต์ ๊ฐ์์ ๋ฌธ์ ์๊ฐ ๋์จ๋ค! ๋ ๋ฒ์งธ ๋ฌธ์์ด์ ์ํ๋ฑ ๊ฐ์๊ฐ ๋ ๋ง์์ ๋จ์ํ๊ฒ ์ฐจ์ด๋ฅผ ๊ณ์ฐํ๋ฉด ์์๊ฐ ๋์ฌ ์ ์์ผ๋ฏ๋ก abs() ํจ์๋ฅผ ์ฌ์ฉํด์ ์ ๋๊ฐ์ผ๋ก ๊ณ์ฐํ๋ค. ์์ค ์ฝ๋ #include using namespace std; int mai..