Computer Science

[C/C++] 행렬의 연산 : 상등

상등: 두 행렬의 크기가 같고 각각 대응하는 성분이 모두 같은 두 행렬아래 두 행렬은 상등이다.C++로 구현하기메소드 오버라이딩을 통해 행렬의 상등 연산을 구현해보자.#include #include "matrix.h"using namespace std;int main() { Matrix m1(3, 4); Matrix m2(3, 4); Matrix m3(3, 3); if (m1 == m2) printf("m1과 m2는 같은 행렬\n"); else printf("m1과 m2는 다른 행렬\n"); if (m2 == m3) printf("m2과 m3는 같은 행렬\n"); else printf("m2과 m3는 다른 행렬\n"); return 0;}...class Matr..

[C/C++] 전치 행렬

전치 행렬: 기존 행렬의 행과 열을 교환하여 얻은 행렬, MijT = Mji행과 열을 교환하기 때문에 기존 행렬과 크기 달라진다. m X n 행렬 -> n X m 행렬C++로 구현하기Matrix 클래스의 메소드로 transpose()를 추가했다.#include #include "matrix.h"using namespace std;int main() { Matrix m1(3, 4); printf("기존 행렬\n"); m1.print(); m1.transpose(); printf("전치 행렬\n"); m1.print(); return 0;}...class Matrix { int **mat; int row; int col;public: ... void..

[C/C++] 단위행렬, 영행렬

단위 행렬: 주대각선 원소가 모두 1이며 나머지 원소는 모두 0인 정사각 행렬(정사각 행렬은 행과 열의 크기가 같은 행렬)영 행렬: 모든 원소가 0인 행렬 (행렬 덧셈의 항등원)C++로 구현하기사실 단위행렬은 정사각행렬이어야 하지만 정사각행렬이 아니어도 처리하도록 코드를 짰다.기존 생성자 함수를 오버로딩해 type이라는 인자를 하나 더 받는 경우를 추가했다.type 인자 값이 0이면 해당 행렬은 영행렬이고, 1이면 단위행렬이다.두 함수의 경우 값을 입력할 필요가 없기 때문에 입력을 받지 않고 자동으로 값을 할당한다.#include #include "matrix.h"using namespace std;int main() { // 영행렬 Matrix m1(2, 3, 0); // 단위 행렬 ..

[C/C++] 행렬

선형대수를 복습하며 C++ 클래스로 만들어보려고 한다. (코드의 효율은 일단 좀 미뤄두고....)행렬: 수 또는 문자들을 행과 열을 갖는 직사각형 모양으로 나열하여 묶어둔 것위 행렬은 m X n 크기의 행렬이다.원소 Amn는 m행 n열의 값을 나타낸다.C++로 구현하기Matrix라는 클래스로 행렬을 구현했다.생성자 파라미터로 배열의 크기를 전달받고 생성자에서 배열 크기에 맞는 2차원 배열을 동적할당 및 원소 값 입력을 받는다. 아래와 같은 main() 함수로 행렬을 생성 및 출력해보자.#include #include "matrix.h"using namespace std;int main() { Matrix m1(3, 3); Matrix m2(3, 2); m1.print(); m2.pr..

11-3. [C/C++] Floyd의 최단 경로 알고리즘

Floyd의 최단 경로 알고리즘 Floyd-Warshall 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 찾는 알고리즘이다. 다익스트라 알고리즘은 출발점이 정해져 있던 것과 달리 플로이드-워셜 알고리즘은 출발점이 정해져 있지 않다. 플로이드 워셜 알고리즘도 다익스트라처럼 단계마다 거쳐 가는 정점을 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다익스트라 알고리즘과 다르다. 노드의 개수가 N개 일 때 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N2)의 연산을 통해 현재 노드를 거쳐 가는 모든 경로를 고려한다. 그래서 총 시간 복잡도는 O(N3)이 된다. 플로이드 워셜 알고리즘에서는 모든 노드에 대해 다른 ..

11-2. [C/C++] Dijkstra의 최단 경로 알고리즘

Dijkstra의 최단 경로 알고리즘 Dijkstra 알고리즘은 하나의 시작 정점 v에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘이다. 그래서 Dijkstra 알고리즘은 출발점이 정해져 있는 상황에 사용하기 적합하다. 다익스트라 알고리즘은 간선의 가중치 값 중 음수가 없을 때 정상적으로 동작한다. 현실의 길(간선)에는 음수 가중치가 없기 때문에 다익스트라 알고리즘은 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 "가장 비용이 적은 노드"를 선택해서 임의의 과정을 반복하기 때문이다. 다익스트라 알고리즘 (1) 출발 노드를 설정한다. (2) 최단 거리 테이블을 초기화한다. (3) 방문하지 않은 노드 중에서 최단 거리..

11-1. 가중치 그래프에서의 최단 경로

최단 경로란? 최단 경로(shortest path) 문제는 가중치 그래프에서 정점 u와 정점 v를 연결하는 경로 중에서 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제이다. 이때 간선의 가중치는 보통 비용이나 거리, 시간 등을 나타낸다. 지도를 가중치 그래프로 나타낸다고 하면, 지도의 각 지역들은 그래프의 정점을 나타내고 가중치(간선)는 어떤 지역에서 다른 지역으로 이동하는 거리를 의미한다. 일반적으로 지도에서 출발점과 도착점을 설정하면 최단 경로를 보여준다. 숭실대입구역에서 서울대입구역으로 가는 경로는 엄청나게 많겠지만, 최단 경로는 많지 않을 것이다. (경로 상의 가중치 합이 같은 경로가 여러 개 있을 수도 있음) 최단 경로 알고리즘 최단 경로를 구하는 대표 알고리즘으로는 Dijkstra와 Flo..

10-5. [C/C++] MST를 위한 Prim 알고리즘

Prim 알고리즘 Prim 알고리즘은 하나의 정점에서부터 시작해 트리를 단계적으로 확장해나가는 방법이다. 처음에는 시작 정점만이 MST에 포함된다. 다음으로 지금까지 만들어진 MST에 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점을 선택하여 트리를 확장한다. 이 과정을 트리가 (n - 1)개의 간선을 가질 때까지 계속한다. Prim() (1) 그래프에서 시작 정점을 선택해 초기 MST를 만든다. (2) 현재 MST의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택한다. (3) 이 정점 v와 이때의 간선을 MST에 추가한다. (4) 모든 정점이 삽입될 때 까지 2번으로 이동한다. Kruskal 알고리즘이 간선을 중심으로 하는 알고리즘인데 비해 Prim 알고리즘은 정점을 중심..