PS(Problem Solving)
-
[๋ฐฑ์ค(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..
-
[๋ฐฑ์ค(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๊ฐ์ ์ค์ ๊ฑธ์ณ ์ ๋ ฅํ ๋ช ๋ น์ด๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค. ๋ช ๋ น์ด๋ ์์ ๋ค ๊ฐ์ง ์ค ํ๋์ ํํ๋ก๋ง ์ฃผ์ด์ง๋ค. ์ถ๋ ฅ ์ฒซ์งธ ์ค์ ๋ชจ๋ ๋ช ๋ น์ด๋ฅผ ์ํํ๊ณ ๋ ํ ํธ์ง๊ธฐ์ ์ ๋ ฅ๋์ด ์๋ ๋ฌธ์์ด์ ์ถ๋ ฅํ๋ค. ํ์ด ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ก ํด๊ฒฐ ํ ์ ์๋ ๋ฌธ์ ๋ค. ์ฐ๊ฒฐ ๋ฆฌ์คํธ๋ ์ปค์๋ฅผ ์ด์ฉํ๋ ๋ฌธ์ ๊ฐ ์ฃผ๋ก ๋์จ๋ค. ๋ฐ๋ผ์ ๋ฉ๋ชจ์ฅ ๊ฐ์ ๋ฌธ์ ๋ค์ ํ์ดํ ๋ ์ฉ์ดํ๊ฒ ์ฌ์ฉ..
-
[๋ฐฑ์ค(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 <..