PROGRAMMING/알고리즘
-
(백준 1260번 DFS와 BFS C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 4PROGRAMMING/알고리즘 2024. 4. 10. 08:54
백준 1260번 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS와 BFS를 알고 있으면 어렵지 않게 구현이 가능한 문제다. #include #include #include #include using namespace std; class Graph { public: int N, M; vector adj; vector visited; Graph(int N, int M) : N(N), M(M), adj(N..
-
(백준 2178번 미로 탐색 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 3PROGRAMMING/알고리즘 2024. 4. 9. 07:41
bfs 문제도 슬슬 익숙해지는 것 같다! 최단 거리를 구할 때는 역시 bfs! 백준 2178번 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net #include #include #include #include using namespace std; constexpr int MAX_N = 101; int arr[MAX_N][MAX_N] = { 0 }; bool isInside(int x, int y, int N, int M) { if (x = N ..
-
(백준 7562번 나이트의 이동 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 27PROGRAMMING/알고리즘 2024. 4. 8. 21:16
날씨가 좋아서 기분이 좋다🌸 꽃이 피어도 알고리즘!! 백준 7562번 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net #include #include #include using namespace std; constexpr int MAX_N = 301; int arr[MAX_N][MAX_N] = { 0 }; void reset_arr(int I){ for (int i = 0; i < I; i++) { for (int j = 0; j < I; j++..
-
(백준 2644번 촌수계산 C++) 라이님 블로그 대회 알고리즘 따라잡기 9) BFS 1PROGRAMMING/알고리즘 2024. 4. 8. 20:21
오늘부터는 bfs를 풀어볼까 한다! 역시나 오늘도 reference는 라이님의 블로그! https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220785747864&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 너비 우선 탐색(Breadth-First Search) (수정 2018-11-22) 자, 이제 빨리 DFS의 반대 개념인 BFS에 대해 배워보죠. BFS는 너비 우선 탐색(breadth-first sea... blog.naver.com 백준 2644번 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1..
-
(백준 11724번 연결 요소의 개수 C++) 라이님 블로그 대회 알고리즘 따라잡기 8) DFS 1PROGRAMMING/알고리즘 2024. 4. 4. 08:02
그 유명하다는 DFS! 자세한 설명은 라이님의 블로그를 참고해서 공부해보았다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220785731077&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList 깊이 우선 탐색(Depth-First Search) (수정 2019-08-18) 어후... 강의 꾸준히 쓰기 정말 힘드네요. 이번엔, 원래 3부 전에 썼어야 할 내용인 탐색에 대해 작성할 겁... blog.naver.com 기본 템플릿은 라이님 블로그를 보면서 익혔다. stack으로도 짤 수 있는데, 보다보니 라이님 알고리즘이 직관적이라서 이 템플릿으로 적응..
-
(백준 3190번 뱀 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 4PROGRAMMING/알고리즘 2024. 4. 3. 01:07
아직 단순 구현이 익숙하지 않은지라,, 다른 분들의 풀이를 보면서 아이디어를 얻었다. 백준 3190번 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net (1) 우선 이 문제에서는 크게 3개의 상태를 N*N 맵에 나타내야 한다. 1. 아무것도 없는 상태 = 0 2. 사과가 있는 상태 = 1 3. 뱀이 자리를 차지하고 있는 상태 = 2 (2) 뱀의 상태와 움직임을 나타내야 한다. 뱀의 위치를 나타내기 위해 queue에 pair를 추가해서 많이 썼다. - 만..
-
(백준 1158번 요세푸스 문제 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 2PROGRAMMING/알고리즘 2024. 3. 26. 08:20
★ 연결 리스트 문제는 deque로 푼다 메모 ★ 백준 1158번 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net #include #include using namespace std; int main() { int N, K; cin >> N >> K; deque dq; for (int i = 1; i
-
(백준 1021번 회전하는 큐 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 1PROGRAMMING/알고리즘 2024. 3. 26. 08:05
아무래도 코드 디자인을 안 하고 짜다보니 코드에 예외도 많은 것 같고, 복잡하게 짜는 것 같아서 챗gpt의 도움을 받았다. 백준 1021번 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net #include #include using namespace std; int main() { int N, M; cin >> N >> M; deque dq; for (int i = 1; i > target; for (int i = 0; i < dq.size(..