목록분류 전체보기 (83)
천천히 빛나는
백트래킹 (Back-tracking) 정답을 찾는 도중에 막히면 더 이상 깊이 들어가지 않고 이전 단계로 돌아가서 정답을 찾는 방법 깊이 우선 탐색 DFS는 가능한 모든 경로를 탐색한다. 불필요할 것 같은 경로를 사전에 차단하지 않기 때문에 경우의 수를 줄이지 못한다. 백트래킹은 지금 경로가 정답이 아닐 것 같다면 이전 단계로 돌아가므로 DFS보다 효율적이다. 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 탐색하는 것이 백트래킹이다. 문제풀이에서는 모든 경우의 수를 탐색하는 과정에서 (DFS 등으로 구현) 조건문으로 절대 답이 될 수 없는 상황을 설정하고 그런 상황이 되었을 때는 탐색을 중지시킨 뒤 다시 이전 단계로 돌아가서 탐색하도록 구현할 수 있다. 백트래킹 예시 bool visited..
1260. (DFS와 BFS) 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. #include #include #include #include using namespace std; vectorgraph[1001]; int n, m, v; bool visited1[1001]; bool visited2[1001]; void dfs(int x) { visited1[x] = 1; cout m >> v; for (int i = 0; i > x >> y; ..
1. 음료수 얼려 먹기 connected component를 찾는 문제이다. 얼음을 얼릴 수 있는 공감이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로 그래프 형태로 모델링 할 수 있다. 다음과 같이 3 x 3 크기의 얼음틀이 있다고 가정하면 위 그림과 같이 그래프로 만들 수 있다. 상, 하, 좌, 우로 연결되어 있는 노드들은 인접한 형태가 된다. 특정 지점에서 BFS 또는 DFS를 수행해서 이동 가능한 모든 경로에 대해서 다 방문처리를 진행하도록 처리할 수 있다. 1) BFS를 이용해서 구현 #include #include using namespace std; bool notAllowed[1001][1001]; int n, m; void bfs(int row, int col) { queue ..
https://shine-slowly.tistory.com/48 알고리즘 : DFS와 BFS (1) - DFS (C++로 구현) 참고 영상 : https://youtu.be/7C9RgOcvkvo?si=PuM-7RIBWbVPtYTw bfs와 dfs는 탐색 알고리즘이다. 내가 헷갈렸던 부분이 있는데 그래프를 인접 행렬, 인접 리스트로 표현할 수 있다고 배웠는데 bfs, dfs는 각각 큐랑 shine-slowly.tistory.com DFS에 관한 내용은 위 포스트에 있습니다. 참고 영상 : https://youtu.be/7C9RgOcvkvo?si=PuM-7RIBWbVPtYTw BFS (Breath-First Search, 너비우선탐색) 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. BFS는 큐..
참고 영상 : https://youtu.be/7C9RgOcvkvo?si=PuM-7RIBWbVPtYTw bfs와 dfs는 탐색 알고리즘이다. 내가 헷갈렸던 부분이 있는데 그래프를 인접 행렬, 인접 리스트로 표현할 수 있다고 배웠는데 bfs, dfs는 각각 큐랑 스택을 사용하여 구현한다는 점이었다. bfs와 dfs는 그래프를 탐색하는 알고리즘인 것이다. 그래프를 표현하는 방식이 아니다! https://shine-slowly.tistory.com/39 알고리즘 : 자료구조(1) 스택 (Stack) (C++로 구현) 스택 (Stack) 스택(stack)은 쌓아놓은 더미라는 의미 그대로, 책상에 쌓여있는 책을 생각하면 된다. 가장 큰 특징은 LIFO(Last In First Out-후입선출)이다. 제일 최근에 들..
그래프의 표현 그래프를 컴퓨터가 처리하게 만들기 위해서는 그래프를 적절한 자료구조로 변환해 주어야 한다. 표현 방식에는 인접행렬(adjaceny matrix)와 인접리스트(adjaceny list)가 있다. 인접 행렬 그래프 (adjaceny matrix) 모든 정보를 저장하는 방식이다. 직관적이며 쉽게 구현이 가능하지만 불필요한 정보 저장이 많다. 그래프의 크기가 커지면 메모리 초과가 발생할 수도 있다. 보통 2차원 배열을 사용하여 구현한다. 정점의 개수가 총 n개이면 인접행렬은 nxn의 크기를 갖는다. 무방향 그래픠 경우 대각선을 중심으로 대칭이며 가중치가 있을 경우 1이 아닌 가중치를 저장하게 된다. 인접 리스트 그래프 (adjaceny list) 갈 수 있는 곳만 저장하는 방식이다. 필요한 정보만..
본 포스팅에서는 그래프의 기본 용어만 다룹니다. 인접행렬 및 인접리스트 관련 내용을 원한다면 (2)를 읽어주세요. 그래프(Graph) 정점(Node/Vertex, 노드)과 간선(Edge, 엣지)으로 이루어진 자료구조이다. 정점의 집합을 V, 간선의 집합을 E, 그래프를 G라고 했을 때 G=(V, E)라고 할 수 있다. 정점 A에서 B로 이동할 수 있는 방법을 경로(Path)라고 한다. 그래프 내에서 정점끼리의 path는 여러 개여도 된다. 또 두 정점 간 경로가 존재하지 않을 수도 있다. 정점 A에서 B로 가는 Path가 존재하면 정점 B는 정점 A로부터 reachable하다고 한다. 노드가 겹치지 않는 경로를 elementary하다고 하며 길이(length)는 엣지의 수를 나타낸다. 간선으로 연결되어 ..
2609. (최대공약수와 최소공배수) 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int a, b; cin >> a >> b; int minVal = 1; int n = min(a, b); while (n > 1) { if (a % n == 0 && b % n == 0) { minVal *= n; a /= n; b /= n; n = min(a, b); } n--; } cout > b; cout > a >> b; cout n; while (n--) { cin >> x; int temp = 0; ..
17298. (오큰수) 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 두 개의 풀이 방식이 있습니다. 더 이해하기 편한 걸로 코드를 구현해보시는 걸 추천합니다 :D 개인적으로 저는 2번이 이해하기가 더 쉬웠습니다. 1) 오큰수를 찾지 못한 값들을 stack에 저장하는 경우 vector input(n); // 입력받은 값들 stack index; // 오큰수를 찾지 못한 값들 - Stack에는 오큰수를 찾지 못한 값들이 쌓일 예정이다. (정확히는 몇번째로 입력한 값인지가 쌓인다.) - 입력..
Stack에 대한 문제들을 다루는 챕터이다. Queue(큐)와 Deque(덱)은 그래프와 BFS에서 집중적으로 다룰 예정이다. https://shine-slowly.tistory.com/39 알고리즘 : 자료구조(1) 스택 (Stack) (C++로 구현) 스택 (Stack) 스택(stack)은 쌓아놓은 더미라는 의미 그대로, 책상에 쌓여있는 책을 생각하면 된다. 가장 큰 특징은 LIFO(Last In First Out-후입선출)이다. 제일 최근에 들어온 데이터가 가장 먼저 나가는 shine-slowly.tistory.com 스택을 아예 모른다면 이 글을 가볍게 읽는 것을 추천한다. c++로 스택을 구현하는 과정과 c++ stl stack을 사용하는 방법이 나와 있다. 10828. (스택) 정수를 저장하는..