SW Test/BaekJoon
-
[BaekJoon] 2295๋ฒ ์ธ ์์ ํฉSW Test/BaekJoon 2021. 8. 22. 21:41
์ด ๊ธ์ C++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์ด ๋ฌธ์ ๋ฅผ 3์ค for๋ฌธ์ ์ฌ์ฉํ๋ฉด ํฉ์ ๊ตฌํ๊ณ ํฉ์ด ์กด์ฌํ๋์ง ํ๋จํ์ฌ ์๊ฐ๋ณต์ก๋๊ฐ O(N4)์ด๊ธฐ ๋๋ฌธ์ ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๊ฒ ๋ฉ๋๋ค. ๋ง์ง๋ง ํฉ์ด ์กด์ฌํ๋์ง๋ฅผ ์ด๋ถํ์์ ์ฌ์ฉํ๋๋ผ๋ ์๊ฐ๋ณต์ก๋๊ฐ O(N3logN)์ด๋ผ์ ์๊ฐ์ด๊ณผ๊ฐ ๋ถ๊ฐํผํฉ๋๋ค. ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด์๋ ์ด๋ถํ์์ ์ฌ์ฉํ๋, ์๋ก์ด ๊ธฐ๋ฒ์ ํ์ฉํด์ผ ํฉ๋๋ค. ์ฆ 2๊ฐ์ ์ซ์์ ํฉ์ ํ๋์ ๋ฐฐ์ด์ ๋ง๋ญ๋๋ค. ์ด ๋์ ์๊ฐ๋ณต์ก๋๋ O(N2)์ ๋๋ค. ์ดํ ์ฒ์ ๋ฐฐ์ด์ ๋ ๊ฐ์ ์ฐจ์ด๊ฐ 2๊ฐ์ ์ซ์์ ํฉ ๋ฐฐ์ด์ ์กด์ฌํ๋์ง ํ์ธํ๋ฉด ๋ฉ๋๋ค. O(N2logN)์ผ๋ก ํด๊ฒฐํ ์ ์์ต๋๋ค. ex) a1+a2+a3 = a4 ->, a4 - a3 = a1+a2 #include #include #includ..
-
[BaekJoon] 1654๋ฒ ๋์ ์๋ฅด๊ธฐSW Test/BaekJoon 2021. 8. 22. 21:34
์ด ๊ธ์ C++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์ด ๋ฌธ์ ๋ ์ด๋ถํ์์ ํ์ฉํ Parametric Search ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ผ ํฉ๋๋ค. 1๋ถํฐ ์ต๋ ๊ธธ์ด๋ฅผ ์์ชฝ์ผ๋ก ํ์ฌ ์ ๋ฐ์ฉ ๊ธธ์ด์ผ ๊ฒฝ์ฐ์ ์ํ๋ ๋์ ์ ๊ฐฏ์๊ฐ ๋๋์ง ํ์ธํ์ฌ s์ e๋ฅผ ์กฐ์ ํฉ๋๋ค. #include #include #include using namespace std; int main(){ int n,k; cin>>n>>k; int arr[10000]; for(int i=0;i>arr[i]; } long long s = 1; long long e = 1; for(int i=1;i
-
[BaekJoon] 18870๋ฒ ์ขํ์์ถSW Test/BaekJoon 2021. 8. 22. 21:23
์ด ๊ธ์ C++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์ฒ์ ์๊ฐํ์ ๋ ์ ๋ ฌ ํ map์ ํตํด ์ค๋ณต์ ๊ฑฐํ๊ณ ๊ฐ์ key๋ก 0๋ถํฐ ํ๋์ฉ ๋ด๊ธฐ๋ count๋ฅผ value๋ก ํ์ฌ ์ถ๊ฐํ ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ์ด๋ ๊ฒ ํ๋ฉด map์ insert์ ์๊ฐ๋ณต์ก๋๋ O(logN), ์ดํ ์ ๋ ฌ์ ๋ํ ์๊ฐ๋ณต์ก๋ O(NlogN)์ด ๊ฑธ๋ ค ์ ์ฒด ์์ ๋ํด์ ํ์ํ ๋์ ์๊ฐ๋ณต์ก๋๋ O(N2logN)์ ๋๋ค. ๋ค์ ํ์ด๋ ๋ฌด์กฐ๊ฑด ์๊ฐ์ด๊ณผ๊ฐ ๋ํ๋๊ฒ ๋๋๋ฐ map์ด ์๋ unordered_map์ ์ฌ์ฉํ๋ฉด ์ด์ง ๊ฒ์ ํธ๋ฆฌ๊ฐ ์๋ ํด์ฌ ํ ์ด๋ธ๋ก ๊ตฌํ์ด ๋์ด O(1)๋ง์ ํต๊ณผํ ์ ์์ต๋๋ค. #include #include #include #include using namespace std; int main(){ int arr[1..
-
[BaekJoon] 2230๋ฒ ์๊ณ ๋ฅด๊ธฐSW Test/BaekJoon 2021. 8. 22. 20:52
์ด ๊ธ์ C++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ๋ค์ ๋ฌธ์ ๋ ์ด๋ถํ์์ผ๋ก๋ ํด๊ฒฐํ ์ ์์ต๋๋ค. ํด๋น ์์ด์ ์ ๋ ฌ ํ ์ฒ์ ์ธ๋ฑ์ค๋ถํฐ ๋๊น์ง ํ์์ ํ๋ ํด๋น ์ธ๋ฑ์ค์ ๊ฐ๋ณด๋ค M์ด ํฐ ๊ฐ์ ์ด๋ถํ์์ ํ์ฌ ์ฝ์ ํ ์ธ๋ฑ์ค๋ฅผ ์ฐพ์ ์ ์์ต๋๋ค. ์ฆ, ์ ๋ ฌ์ ๋ฌด๋๋จ๋ฆฌ์ง ์๊ณ ํด๋น ๊ฐ์ ์ถ๊ฐํ ์ธ๋ฑ์ค(lower_bound)๋ฅผ ๋ฐํํฉ๋๋ค. ํ์ง๋ง, ํฌ ํฌ์ธํฐ ๋ผ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ ํ์ด๋ฅผ ํ๋ ค๊ณ ํฉ๋๋ค. ์ด ๋ฌธ์ ์์ ํฌ ํฌ์ธํฐ๋ฅผ ์ฌ์ฉํ๋ฉด ์ ๋ ฌํ ๋ O(NlogN)๊ณผ ์๋ฅผ ๊ณ ๋ฅด๋ ๋ฐฉ๋ฒ O(N)์ผ๋ก ์๊ฐ๋ณต์ก๋๋ O(NlogN)์ด ๋ฉ๋๋ค. #include #include #include using namespace std; int main(){ int arr[100000]; int n,m; cin>>n>>m..
-
[BaekJoon] 1806๋ฒ ๋ถ๋ถํฉSW Test/BaekJoon 2021. 8. 22. 20:46
์ด ๋ฌธ์ ๋ C/C++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ๋ถ๋ถํฉ์ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ 3์ค for๋ฌธ์ ์ด์ฉํด์ ํ๋์ฉ ๋ง์ ์ ํ์ฌ s๋ฅผ ๋์๋์ง ํ์ธํ๋ ๋ฐฉ๋ฒ์ด ๊ธฐ๋ณธ์ ์ผ๋ก ๋ ์ฌ๋ฆด ์ ์์ต๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ถ๋ถํฉ ๊ตฌํ๋ ๋ฐฉ๋ฒ์ ์กฐ๊ธ ๋ฐฐ์ฐ์ ๋ถ์ด๋ผ๋ฉด ์๋ก์ด ๋ฐฐ์ด์ ๋ง๋ค์ด ์ฒ์๋ถํฐ ํด๋น ์ธ๋ฑ์ค๊น์ง์ ์์๋ค์ ํฉ์ ๋ํ๋ด๋ ๋ฐฐ์ด์ ๋ง๋ญ๋๋ค. ์ดํ 2์ค for๋ฌธ์ ์ด์ฉํ์ฌ sum(j) - sum(i)๊ฐ s๊ฐ ๋์๋์ง ํ์ธํ๋ฉด ์๊ฐ๋ณต์ก๋๋ฅผ ๋ฎ์ถ ์ ์์ต๋๋ค. ํ์ง๋ง N์ ํฌ๊ธฐ๋ 10๋ง์ด๋ผ O(n2)์ด์ฌ๋ ์๊ฐ์ด๊ณผ๊ฐ ๋ฐ์ํ๊ธฐ ๋๋ฌธ์ ํฌ ํฌ์ธํฐ ๋ผ๋ ์๊ณ ๋ฆฌ์ฆ์ ์ฌ์ฉํด์ ํ์ด์ผ ํฉ๋๋ค. ํฌ ํฌ์ธํฐ ๋ฅผ ์ฌ์ฉํ๋ฉด O(N)์ผ๋ก ํด๊ฒฐํ ์ ์์ต๋๋ค. #include #include #include using namespace st..
-
[BeakJoon] 5430๋ฒ: ACSW Test/BaekJoon 2021. 7. 22. 13:40
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ๊ฑฐ๊พธ๋ก ๋ค์ง๋ ํจ์๋ฅผ ์ค์ ๋ก ์ํํ์ง ์๊ณ ๊ฑฐ๊พธ๋ก ๋ค์ง์์ ๊ฒฝ์ฐ๋ ๋งจ ๋ค์ ์์ ๋ฐํ, ์๋ ์์์ผ ๋๋ ์์ ์์ ๋ฐํ์ผ๋ก ๋ฐ๊พธ๋ฉด ๋ฉ๋๋ค. deque๋ฅผ ์ฌ์ฉํ์ฌ ๋งจ ์์ ์์์ ๋งจ ๋ค์ ์์๋ฅผ ์ฝ๊ฒ ์ ๊ทผํ ์ ์์ต๋๋ค. ์ถ๊ฐ๋ก ๊ถ๊ธํ ์ ์ด๋ ์์ ํ ๋ถ๋ถ ์์ผ๋ฉด ๋๊ธ๋ก ๋จ๊ฒจ์ฃผ์ธ์.
-
[BaekJoon] 17298๋ฒ : ์คํฐ์SW Test/BaekJoon 2021. 7. 19. 22:13
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์ฒ์ ๋ฌธ์ ๋ฅผ ๋ณด๋ฉด ๋ ์ค๋ฅด๋ ํ์ด๋ O(n2)๋ฐฉ๋ฒ์ผ๋ก 2์ค for๋ฌธ์ผ๋ก ์ ์ฒด ํ์ํ๋ฉด์ ๋น๊ตํ๋ ๋ฐฉ๋ฒ์ ๋๋ค. ํ์ง๋ง, ์ด ๋ฌธ์ ๋ ๊ฒฝ์ฐ์ ์๊ฐ 1,000,000์ด๊ธฐ ๋๋ฌธ์ ๋น์ฐํ ์๊ฐ์ด๊ณผ๊ฐ ๋ ๊ฒ์ด๋ผ๊ณ ์๊ฐํด์ผํฉ๋๋ค. stack์ ํ์ฉํ๋ฉด O(n)์ผ๋ก ํ์ด๊ฐ ๊ฐ๋ฅํฉ๋๋ค. #include #include #include using namespace std; int main() { // your code goes here int num; cin>>num; vector vec; for(int i=0;i>n; vec.push_back(n); } stack s; for(int i=vec.size()-1;i>0;i--){ s.push(vec[i]); } int ..
-
[BaekJoon] 1697๋ฒ : ์จ๋ฐ๊ผญ์งSW Test/BaekJoon 2021. 4. 23. 01:52
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ํ์ด BFS๋ฅผ ํ์ฉํ๋ ๋ฌธ์ ์ธ๋ฐ 2์ฐจ์์ด ์๋ 1์ฐจ์์ผ๋ก ์์ฑํ๋ฉด ๋ฉ๋๋ค. #include #include using namespace std; int arr[100005]; int main(){ int n,k; cin>>n>>k; queue q; arr[n] = 1; q.push(n); while(!q.empty()){ int cur = q.front(); if(cur == k) break; q.pop(); if(cur>0 && arr[cur-1] == 0){ q.push(cur-1); arr[cur-1] = arr[cur]+1; } if(cur