SW Test/BaekJoon
-
[BaekJoon] 4179๋ฒ : ๋ถ!SW Test/BaekJoon 2021. 4. 23. 01:43
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด BFS ํ์ฉํ๋ ๋ฌธ์ ๋ก ๋ถ์ ์์์ ์์ BFS๋ฅผ ๋๋ฆฐ ํ ์งํ์ด๋ฅผ BFS๋ฅผ ์งํํ์ฌ ๋ถ์ด ๋จผ์ ํ์ฐ๋ ๊ฒฝ์ฐ ์งํํ ์ ์๋๋ก ํฉ๋๋ค. ์ฃผ์ํด์ผํ ์ ์ 2๊ฐ์ง๋ก ๋ถ์ด ์ฌ๋ฌ ๊ฐ ์กด์ฌํ ์ ์๋ค๋ ์ ๊ณผ, ๋ถ์ด ์์ ์๋ ์๋ค๋ ์ ์ ๋๋ค. ์ฆ, ๋ถ์ด ์ฌ๋ฌ ๊ฐ ์กด์ฌ๋ BFS๋ฅผ ๋๊ฐ์ด ํด๋ ๊ด์ฐฎ์ง๋ง, ๋ถ์ด ์๋ ๊ฒฝ์ฐ์๋ ๋ถ์ด ์ด๋ํ ๊ฑฐ๋ฆฌ ๋ฐฐ์ด์ ์ด๊ธฐํ์ธ ์ํ ๊ทธ๋๋ ์์ต๋๋ค. #include #include #include #include using namespace std; int n,m; int arr[1000][1000]; int fdist[1000][1000]; int jdist[1000][1000]; int dir[4][2] = {{0,1},{1,0..
-
[BaekJoon] 7576๋ฒ : ํ ๋งํSW Test/BaekJoon 2021. 4. 23. 01:38
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์์์ ์ด ์ฌ๋ฌ ๊ฐ ์๋ BFS ๋ฌธ์ ๋ก BFS์ ๋ํ ํน์ง์ด ์ ๋๋ก ์์ด์ผ ํฉ๋๋ค. BFS๋ ํ์ ์ฒ์ ์์์ ์ ํ ๊ฐ ๋ด์๋ค๋ฉด, ์ด ๋ฌธ์ ๋ ์์์ ์ด ์ฌ๋ฌ ๊ฐ ์์ผ๋ฉด ์ฌ๋ฌ ๊ฐ๋ฅผ ํ๋์ ํ์ ๋ด๊ธฐ๋ง ํ๋ฉด ๋ฉ๋๋ค. ํ์์ front์ ํด๋น๋๋ ์์์ ์์ BFS๋ฅผ ์งํํ๊ฒ ๋๊ณ ํน์ ์์ญ์ ์ฌ๋ฌ ์์์ ์ค ์ฒ์ ๋ฐฉ๋ฌธํ ๋๊ฐ ์ต๋จ ๊ฑฐ๋ฆฌ์ ๋๋ค. #include #include #include using namespace std; int n,m; int arr[1000][1000]; int dist[1000][1000]; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; bool inside(int y, int x){ return..
-
[BaekJoon] 2178๋ฒ : ๋ฏธ๋ก ํ์SW Test/BaekJoon 2021. 4. 23. 01:34
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด BFS ํน์ง ์ค ํ๋๋ ํ์ํ๋ ์์ญ์ ์ต์ํ์ ๊ฑฐ๋ฆฌ๋ก ํ์ํ๋ค๋ ํน์ง์ด ์์ต๋๋ค. ๋ฐ๋ผ์ BFS ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์ํ๋ ๊ณต๊ฐ์ ์ฒ์์ผ๋ก ํ์ํ๋ ์๊ฐ์ด ์ต๋จ๊ฑฐ๋ฆฌ ์ ๋๋ค. #include #include #include #include #include using namespace std; int n,m; int arr[100][100]; int dist[100][100]; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; bool inside(int y,int x){ return 0m; for(int i=0;i>s; for(int j=0;j
-
[BaekJoon] 1926๋ฒ : ๊ทธ๋ฆผSW Test/BaekJoon 2021. 4. 23. 01:26
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด BFS๋ฅผ ํ์ฉํ๋ ๋ฌธ์ ๋ก ๋ฐฐ์ด์ ๋ชจ๋ ์ง์ญ์์ BFS๋ฅผ ์คํํฉ๋๋ค. ์ฒ์ BFS์์ ์คํํ์ฌ ํ์ํ์ง ์์ ์ง์ญ์์ ๋ค์ BFS๋ฅผ ์คํํ์ฌ ๊ทธ๋ฆผ์ ๊ฐฏ์๋ฅผ ํ์ ํฉ๋๋ค. ๊ทธ๋ฆผ์ ์ต๋ ํฌ๊ธฐ๋ BFS๋ฅผ ์คํํ๋ฉด์ ํ์์ popํ ๊ฐฏ์๋ฅผ ์ธ์ด ๋น๊ตํฉ๋๋ค. #include #include #include using namespace std; int n,m; int arr[500][500]; bool visit[500][500]; int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}}; bool inside(int y,int x){ return 0m; for(int i=0;iarr[i][j]; } } int cnt = 0; int ans..
-
[BaekJoon] 11724๋ฒ : ์ฐ๊ฒฐSW Test/BaekJoon 2021. 4. 23. 01:21
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ๊ทธ๋ํ๋ฅผ ๊ตฌํํ ์ ์๋์ง ํ์ธํ๋ ๋ฌธ์ ๋ก ์ธ์ ํ๋ ฌ์ด๋ ์ธ์ ๋ฆฌ์คํธ๋ฅผ ํตํด ํํํ ์ ์์ต๋๋ค. ์ด ๋ฌธ์ ๊ฐ์ ๊ฒฝ์ฐ๋ ์ธ์ ํ๋ ฌ๋ณด๋ค ์ธ์ ๋ฆฌ์คํธ๋ก ํ ๊ฒฝ์ฐ ์๊ฐ๋ณต์ก๋๊ฐ ๋ฎ์ต๋๋ค. O(N2) >n>>m; bool visit[1005]; fill(visit, visit+1005, false); for(int i=0;i>a>>b; vec[a].push_back(b); vec[b].push_back(a); }..
-
[BaekJoon] 10816๋ฒ : ์ซ์์นด๋ 2SW Test/BaekJoon 2021. 4. 21. 03:53
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์ด๋ถํ์์์ ์ฐพ์์ผ ํ target ์์์ ์ธ๋ฑ์ค ์ค ๊ฐ์ฅ ์์ ๊ฐ๊ณผ ๊ฐ์ฅ ํฐ ๊ฐ์ ์ฐพ์ ๋นผ๋ ๊ฐ์ด ๊ฐ์์ ๋๋ค. ์ง์ ๊ตฌํํ ์ ์์ง๋ง, ํท๊ฐ๋ฆด ์ํ์ด ์๊ธฐ ๋๋ฌธ์ STL ์ค upper_bound์ lower_bound ๊ฐ์ ์ธ ์ ์์ต๋๋ค. #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); long long arr[100000]; int num; cin>>num; for(int i=0;i>arr[i]; } sort(arr, arr+num); int n; cin>>n; for(int i=0;i>ans; bool check = false; lo..
-
[BaekJoon] 1920๋ฒ : ์ ์ฐพ๊ธฐSW Test/BaekJoon 2021. 4. 21. 03:43
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์ด ๋ฌธ์ ๋ ๊ฐ๋จํ๊ฒ map, set STL์ ์ฌ์ฉํด์ ํ๋ฉด ์๊ฐ์ด๊ณผ๊ฐ ๋ฉ๋๋ค. ์ด์งํ์ ํธ๋ฆฌ๋ก ์ฝ์ , ์ ๋ ฌ ๊ณผ์ ์์ ์๊ฐ์ด ๋ ๊ฑธ๋ ค์ ์ด์งํ์๊ณผ ์๊ฐ๋ณต์ก๋๋ O(logN)์ผ๋ก ๊ฐ์ง๋ง ๋๋ฆฝ๋๋ค. ์ด์งํ์ ์ฝ๋๋ฅผ ์๋์ ๊ฐ์ด ์ง์ ๊ตฌํํด๋ ๋์ง๋ง, STL์ binary_search ํจ์๋ฅผ ์ฌ์ฉํ๋ฉด ๋ณด๋ค ํธ๋ฆฌํฉ๋๋ค. c, c++ stream ๋๊ธฐํ ๋๋ ์ฝ๋์ ๋ฒํผ ๋น์์ฃผ๋ ์ฝ๋๋ ์์ด์ผ ์๊ฐ์ด๊ณผ๊ฐ ๋ํ๋์ง ์์ต๋๋ค. #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int arr[100005]; int num; cin>>num; for(int i..
-
[BaekJoon] 12865๋ฒ : ํ๋ฒํ ๋ฐฐ๋ญSW Test/BaekJoon 2021. 4. 20. 02:07
์ด ๊ธ์ c++๋ก ํ์ด๋ฅผ ์์ฑํ์์ต๋๋ค. ๋ฌธ์ ์์ ํ์ด ์ด ๋ฌธ์ ๋ฅผ ๊ทธ๋ฆฌ๋๋ผ๊ณ ์คํดํ์ฌ ์ค๋ ๋๋น ๊ฐ์น๊ฐ ๊ฐ์ฅ ํฐ ๊ฒฝ์ฐ๋ฅผ ๋ฃ๋๋ค๊ณ ํ ๊ฒฝ์ฐ ์์ธ๊ฐ ๋ฐ์ํ๊ฒ ๋ฉ๋๋ค. ๊ทธ๋ฆฌ๋๊ฐ ์๋ DP๋ก ํด๊ฒฐํด์ผ ํ๋ฉด DP๋ก ์ ๋ช ํ 0-1 knapsack ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. D[i][w] : ํ์ฌ w ๋ฌด๊ฒ๊ฐ ๋จ์ ์ํ์์ i๋ฒ์งธ item์ ํ๊น์ง ์ต๋ ๊ฐ์น if w[i] < w, D[i][w] = max(D[i-1][w-w[i]]+v[i], D[i-1][w]) : i๋ฒ์งธ Item์ ๋ด์ ์ ์๋ค๋ฉด, i-1๋ฒ์งธ๊น์ง Item์ ๋ด์ผ๋ฉด์ ํ์ฌ ๋ด์ ์ ์๋ ๋ฌด๊ฒ๊ฐ w-w[i]๋งํผ ๋จ์ ๊ฒฝ์ ์ ์ต๋ ๊ฐ์นํฉ์ i๋ฒ์งธ Item์ ๊ฐ์น๋ฅผ ํฉํ ๊ฐ๊ณผ D[i-1][w] ๊ฐ ๋น๊ต else, D[i][w] = D[i-1][w] #include #..