PROGRAMMING
-
(백준 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으로도 짤 수 있는데, 보다보니 라이님 알고리즘이 직관적이라서 이 템플릿으로 적응..
-
(C++)DFS stack을 이용해서 구현해보기PROGRAMMING/STL 2024. 4. 4. 00:31
#include #include #include using namespace std; class Graph { int V; vector adj; public: Graph(int V) : V(V) {} void addEdge(int v, int w); void DFS(int s); }; void Graph::addEdge(int v, int w) { adj[v].push_back(w); } void Graph::DFS(int s) { vector visited(V, false); stack st; st.push(s); while (!st.empty()) { int s = st.top(); st.pop(); if (!visited[s]) { visited[s] = true; } for (auto i = ad..
-
(백준 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를 추가해서 많이 썼다. - 만..
-
(백준 2840번 행운의 바퀴 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 4PROGRAMMING/STL 2024. 3. 27. 20:46
백준 2840번 https://www.acmicpc.net/problem/2840 2840번: 행운의 바퀴 첫째 줄에 마지막 회전에서 화살표가 가리키는 문자부터 시계방향으로 바퀴에 적어놓은 알파벳을 출력한다. 이때, 어떤 글자인지 결정하지 못하는 칸은 '?'를 출력한다. 만약, 상덕이가 적어놓 www.acmicpc.net 풀이 방법 1. 길이가 N인 deque를 만들어 '?'으로 초기화한다. 2. K번 동안 입력 (n, k)에 대해 k가 맨 뒤에 가도록 설정하고, 맨 뒤에서 n번째에 다음 글자를 넣도록 한다. 문제 예시1에서 _ _ A → _ BA 이 되도록 한다. 3. B가 제일 뒤가 되도록 deque 원소를 이동한다. _ BA → A_B 2번과 3번 과정을 지속한다. #define _CRT_SECUR..
-
(백준 2346번 풍선 터뜨리기 C++) 라이님 블로그 대회 알고리즘 따라잡기 7) 리스트, 배열, 연결 리스트 3PROGRAMMING/STL 2024. 3. 26. 21:14
백준 2346번 https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net #include #include using namespace std; int main() { int N; cin >> N; int temp; deque dq; for (int i = 1; i > temp; dq.push_back(pair(i, temp)); } while (N--) { cout
-
(백준 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(..
-
★연결리스트 LinkedListPROGRAMMING/STL 2024. 3. 25. 00:27
라이님과 챗gpt를 통해 LinkedList 템플릿을 정리해보았다. https://blog.naver.com/PostView.naver?blogId=kks227&logNo=220781402507&parentCategoryNo=&categoryNo=299&viewDate=&isShowPopularPosts=false&from=postList' 리스트(List), 배열(Array), 연결 리스트(Linked List) 오랜만입니다. 논문 읽다가 멘붕이 와서 빠르게 글 씁니다. 원래는 이번 차례에 DFS를 강의하려고 했으... blog.naver.com 라이님 블로그에서 unique_ptr 를 사용해서 좀 더 간단하고 안전한 코드가 되도록 chat gpt한테 시켰다.ㅎㅎ 아래 템플릿이 상당히 마음에 들어서 외..