개발

백준 11403번: 경로 찾기

문제 링크 : https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어 : BFS 한 줄을 탐색하면서, 값이 1인 것인 정점을 기준으로 탐색함. 그래서 답으로 사용할 배열의 값을 1로 변경. #include #include #include #include using namespace std; int N; int nMap[101][101]; int nAns[101][101]; int nChecked[101][101]; queue q; void BFS(int y) { q.push(y); w..

백준 7562번: 나이트의 이동

문제 링크 : https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ... www.acmicpc.net 아이디어 : BFS 현재 위치에서 나이트가 갈 수 있는 곳을 Queue에 넣고 돌린다. 항상 문제는 BFS 돌리더라도..

다이나믹 프로그래밍(Dynamic Programming)

다이나믹 프로그래밍이란 하나의 문제를 단 한 번만 풀도록 하는 알고리즘? 다이나믹 프로그래밍은 다음의 가정 하에 사용할 수 있습니다. 1번. 큰 문제를 작은 문제로 나눌 수 있습니다. 2번. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일합니다. 그것을 먼저 잘게 나누어서 해결한 뒤에 처리하여 나중에 전체의 답을 구한다. --> 분할 정복과 애매하게 다른 느낌이다? 이 과정에서 메모이제이션이 사용된다는 점에서 다르다고 합니다. --> 이미 계산한 결과는 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 단순히 반환하기만 하면 되는 것. 대표적으로 피보나치 수열을 문제로 다이나믹 프로그래밍으로 해결해본다. #include int d[100]; long long dp(int ..

이진 트리의 구현과 순회 방식

이 챕터는 알고리즘보다는 자료구조에 가까운 것 같아 자료구조 게시판에 게시한다. 이진 트리는 대표적인 비선형 자료구조이다. 완전 이진 트리와 이진 트리의 차이를 분명히 하고 넘어가야 한다. --> 나도 처음에 배열로 표현하면 될 것 같은데? 라고 생각했는데 여기서 할 것은 !이진 트리! 이다. 충분히 배열로 표현이 가능하나, 오른쪽에만 노드가 이어져있다 생각해보면 메모리 낭비가 심하다고 생각할 수 있다. 순회 방식은 3개 있다. 1. 전위 순회 (1) 먼저 자기 자신을 처리. (2) 왼쪽 자신을 방문 (3) 오른쪽 자식을 방문 2. 중위 순회 (1) 왼쪽 자신을 방문 (2) 먼저 자기 자신을 처리. (3) 오른쪽 자식을 방문 3. 후위 순회 (1) 왼쪽 자신을 방문 (2) 오른쪽 자식을 방문 (3) 먼저..

크루스칼 알고리즘 (Kruskal Algorithm)

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘 최소 비용 신장 트리 Idea. 간선을 거리가 짧은 순서대로 그래프에 포함시키면 어떨까? 간선 정보를 오름차순으로 정렬한 뒤에 비용이 적은 간선부터 차근차근 그래프에 포함 유의사항. 사이클이 형성되면 안된다. --> 사이클이 발생하는지의 여부는 Union-Find알고리즘을 사용 순서. 1. 정렬된 순서에 맞게 그래프에 포함시킵니다. 2. 포함시키기 전 사이클 테이블을 확인. 3. 사이클을 형성하는 경우 간선을 포함하지 않습니다. #include #include #include using namespace std; int getParent(int parent[], int x) { if (parent[x] == x) return x; retur..

Union-Find(합집합 찾기)

대표적인 그래프 알고리즘 여러 개의 노드가 존재 시, 두 개의 노드를 선택해서 이 두 노드가 서로 같은 그래프에서 속하는지 판별하는 알고리즘 #include int getParent(int parent[], int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent, parent[x]); } // 두 부모 노드를 합치는 함수 void unionParent(int parent[], int a, int b) { a = getParent(parent, a); b = getParent(parent, b); if (a < b) { parent[b] = a; } else { parent[a] = b; } } int findParent(int..

깊이 우선 탐색(Depth First Search, DFS)

깊이 우선 탐색은 스택이 사용된다. 굳이 스택을 사용하지 않더라도, 구현이 가능하다. 간단한 알고리즘을 사용 1. 스택의 최상단 노드를 확인합니다. 2. 최상단 노드에게 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺍니다. #include #include using namespace std; int number = 7; int c[7]; vector a[8]; void dfs(int x) { if (c[x]) return; c[x] = true; cout

너비 우선 탐색(Breadth First Search, BFS)

너비 우선 탐색은 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 너비 우선 탐색은 '최단 경로'를 찾아준다는 점! 준비물은 큐 #include #include #include using namespace std; int number = 7; int checked[7]; vector a[8]; void bfs(int start) { queue q; q.push(start); checked[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); printf("%d ", x); for (int i = 0; i < a[x].size(); i++) { int y = a[x][i]; if (!checked[y]) { q.push(y); ..

큐(Queue)

큐도 스택에 이어 같이 나오는 자료구조이다. 큐의 특징은? 먼저 들어 간 데이터가 먼저 나온다 스택과 다르다 그래서 입구와 출구가 각각 다른 구조라고 생각하면 된다. 앞에 스택과 같이 STL라이브러리를 사용해 큐를 구현할 예정이다. 똑같이 결과 값을 예상하고, 코딩을 했으면 좋겠다. #include #include using namespace std; int main(void) { queue q; q.push(7); q.push(5); q.push(4); q.pop(); q.push(6); q.pop(); while (!q.empty()) { cout

스택(Stack)

스택은 자료구조이다. 스택의 특징은? 가장 늦게들어오는 데이터가 먼저 나가는 구조이다. 스택은 입구와 출구가 하나밖에없는 구조로 생각하면 쉽다. 여기서는 STL 라이브러리를 사용한 스택을 프로그래밍 할 예정이다. 먼저 해당 코드를 보고, 결과 값이 어떻게 나올지 생각해보고 코딩했으면 좋겠다. 사실 이해했으면 코딩 안해도 된다. #include #include using namespace std; int main(void) { stack s; s.push(7); s.push(5); s.push(4); s.pop(); s.push(6); s.pop(); while (!s.empty()) { cout