1. 정의 -문자열이란? string이나 char[ ] 배열 초기화 함수: memset(배열이름, 초기화값, sizeof(배열이름)); -GCD란? Greatest Common Divisor: 최대공약수 -LCM이란? Least Common Multiple: 최소공배수 두 자연수의 공통된 배수 중 가장 작은 수 -> 최대공약수를 통해 구할 수 있음 2. 동작 원리 -GCD 방식1: 두 수 m, n를 입력받고 2부터 n까지 두 자연수를 모두 나누어보면 최대공약수를 구할 수 있음 방식2: 유클리드 호제법 m을 n으로 나눈 나머지를 r이라고 하면, m과 n의 최대공약수는 n과 r의 최대공약수와 같은 것을 이용 -LCM 두 수의 곱을 두 수의 최대공약수로 나누어주면 최소공배수를 알 수 있음 3. 코드 //GCD..

1. 플로이드-와샬이란? 다익스트라 알고리즘과 같이 최단 거리를 구할 수 있는 알고리즘 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구하는 알고리즘 모든 쌍을 행렬로 선언하고 DP를 이용해 각 쌍의 최단 거리를 업데이트한다 거쳐가는 정점을 기준으로 최단 거리를 업데이트한다. 2. 동작 원리 정점 i에서 정점 j까의 최단 경로 dp[i][j] = min(dp[i][j], dp[i][n] + dp[n][j]) n -> 경유점 i에서 j로 곧바로 가는 경우 vs i에서 다른 정점 k를 거쳐 j로 가는 경로 3. 코드 void floyd() { for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { a..

1. 벨만 포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 다익스트라 알고리즘과 달리 매 반복마다 모든 간선을 확인한다. 시간복잡도가 느리다. -> O(VE) 2. 동작 원리 시작점에서 한 정점 x까지의 최단 경로를 구하다고 하면, x를 제외한 모든 노드(V-1)가 시작점과 x 사이의 최단 경로를 구성한다. 모든 정점으로 가는 최단 경로 갱신 과정을 V-1번 반복하면 된다. 음수사이클이 있는지 알아보려면 1번 더 돌려서 최단 거리가 갱신되는지 확인하기 3. 코드 #define INF 987654321 typedef pair P; long long dist[510]; //각 도시의 거리 계산 long long 필수 vec..

1. 다익스트라 알고리즘이란? Dijkstra 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 특정 노드에서 그래프의 모든 노드로 가는 최단 경로를 찾는 알고리즘 1:N관계이며 음수가중치는 없다 2. 동작 원리 dist배열은 시작 노드에서 i번째 노드까지의 거리를 뜻하고, 처음 시작점을 제외한 모든 노드를 INF로 초기화해줘야 함 방문하지 않은 정점 중에서 시작 노드로부터 거리가 가장 가까운 정점을 방문하고 방문한 정점에서 인접한 정점들에 대해서 거리를 갱신해줌 시간복잡도를 줄이기 위해 우선순위 큐를 이용 우선순위 큐는 내림차순으로 정렬되기 때문에 값을 넣을 때 -를 붙여주고 값을 빼낼 때도 -를 붙여서 빼준다 3. 코드 int start; int dist[20010]; vector ..

1. DFS, BFS란? 그래프 탐색: 하나의 정점으로부터 시작해서 차례대로 모든 정점을 한 번씩 방문하는 것 DFS와 BFS는 그래프 탐색의 일종 2. 동작 방식 DFS: 깊이우선탐색 stack이나 재귀함수를 이용함. 루트 노드에서 시작해서 해당 노드의 자식 노드를 먼저 탐색 이동할 때마다 가중치가 있거나 이동 과정에서 제약이 있는 경우 BFS: 너비우선탐색 queue를 이용함. 루트 노드에서 시작해서 해당 노드의 인접 노드를 우선적으로 탐색 단순 최단 경로를 찾는 문제 3. 코드 //1차원 DFS vector adj[1010]; bool visited[1010]; //dfs방문 void dfs(int now) { Dvisited[now] = true; printf("%d ", now); for (in..