할머니의 콤퓨타 도전기

long long 형의 범위를 벗어난 수들을 + 연산자를 이용해 덧셈을 하게되면 오버플로우 발생 따라서 굉장히 큰 수에 대해서는 문자배열을 이용해 덧셈 진행 Algorithm 문자 배열 (A, B) 2개를 뒤에서 부터 더해가며 새로운 문자 배열(result)에 저장 1번 과정을 진행하면서 올림 수(sum)을 계속 저장 문자 배열 A, B를 모두 순회하고 올림 수에 저장된 수가 없다면 result를 뒤집어 주고 종료 Ex. A = "12345", B = "666" 5 + 6 = 11 올림 수 1 result에 1 추가 sum = 1, result = "1" 4 + 6 + sum = 11 올림 수 1 result에 1 추가 sum = 1, result = "11" 3 + 6 + sum = 10 올림 수 1 ..

원반이 1개 시작점 'A'에서 도착지 'C'로 바로 옮김 원반이 2개 (원반이 1개일 때 처럼) 작은 원반을 B로 옮김 (원반이 1개일 때 처럼) 큰 원반을 C로 옮김 (원반이 1개일 때 처럼) 작은 원반을 다시 C로 옮김 원반이 3개 (원반이 2개일 때 )이용해서 (1번 원반, 2번 원반)을 A에서 B로 옮김 (원반이 1개일 때)이용해서 3번 원반을 옮김 (원반이 2개일 때)이용해서 (1번 원반, 2번 원반)을 B에서 C로 옮김 원반이 N개 (원반이 N-1개일 때 처럼) N-1개 원반을 B로 옮김 (원반이 1개일 때 처럼) 마지막 원반을 C로 옮김 (원반이 N-1개일 때 처럼) N-1개의 원반을 B에서 C로 옮김

Kruskal Algorithm 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용 (간선에 가중치가 포함) 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 사용 최소 신장 트리를 구하기 위한 알고리즘 신장 트리 (Spanning tree) 그래프에서 모든 정점을 포함하고 정점 간 서로 연결이 되며 사이클 (cycle)이 존재하지 않는 그래프 연결 관계에서 사이클 형성 안함 모든 정점이 포함되어 있으면서 모든 노드는 적어도 하나의 간선으로 연결되어 있음 신장 트리는 정점이 n개일 때, 간선이 n-1개 신장 트리들 중 가중치의 합이 최소가 되는 신장트리를 최소 신장 트리 (Minimum Spanning Tree, MST..

GCD int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a%b); } LCM LCM = (a*b)/GCD GCD(a,b) = G라고 둠. a = Gx, b = Gy (x, y는 서로소인 정수) 성립. 따라서 a, b의 합집합은 G, x, y 즉, a*b의 최소공배수는 G*x*y. a*b = G*G*x*y이므로 LCM = (a*b)/G = (a*b)/GCD

Floyd Warshall Algorithm 다익스트라 알고리즘은 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 플로이드 와샬 알고리즘은 모든 정점에서 모든 정점으로의 최단 경로를 구함 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘 수행 기본적으로 다이나믹 프로그래밍 기술 위의 그래프에서 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열로 출력 0 5 INF 8 7 0 9 INF 2 INF 0 4 INF INF 3 0 위 테이블은 현재까지 계산된 최소 비용 이러한 이차원 배열을 반복적으로 갱신해 최종적으로 모든 최소비용을 구해야함 반복의 기준은 거쳐가는 정점 1. 노드 1을 거쳐가는 경우: 색칠..

위상 정렬 순서가 정해져 있는 작업을 차례대로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 DAG (Directed Acyclic Graph: 사이클이 발생하지 않는 방향 그래프)에만 적용 가능 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음 위상 정렬은 시작점이 존재해야함. 사이클 그래프에서는 시작점 찾을 수 없음. 불가능 위상 정령은 두 가지의 해결책 보여줌 현재 그래프는 위상 정렬이 가능? 가능하다면, 그 결과는? 구현 방법 진입 차수가 0인 정점을 큐에 삽입 큐에서 원소를 꺼내 연결된 모든 간선 제거 간선 제거 이후에 진입차수가 0이된 정점을 큐에 삽입 큐가 빌 때 까지 2~3번 과정 반복 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재하는 것 모든 원소를 방문했다면 큐에..