컴퓨터공학 💻 도서관📚

주어진 N, M의 범위를 보니 플로이드 워셜 알고리즘은 500개 이상이므로 안 되고 기본 다익스트라 알고리즘도 시간복잡도가 O(N^^2)이므로 시간초과가 나올 수 있기 때문에 우선순위 힙을 이용한 다익스트라 알고리즘으로 구현하면 된다  도시 C에서 출발해서 각각의 노드로 도달하기 위한 최단 거리 값을 구한 뒤에 C에서 도달이 가능한 도시의 개수를 구할 수 있을 것이고 또한, 도시들이 모두 메시지를 받는 데까지 걸리는 시간을 구하기 위해서 도달이 가능한 도시 중에서 가장 큰 비용을 가지는 즉, 가장 거리가 먼 도시에 대한 정보를 출력하면 된다    C++ 코드   자바 코드

플로이드 워셜 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다는 점에서 점화식에 맞게  3중 반복문을 이용해서 2차원 테이블을 갱신한다 3중 반복문을 이용하기 때문에 시간복잡도가 O(N^^3) 이기에 노드의 개수가 적은 상황에서 효과적으로 사용할 수 있고 노드의 개수, 간선의 개수가 많은 경우에는 일반적으로 다익스트라 알고리즘을 사용해야 해결할 수 있는 경우가 많다   플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형이기 때문에 점화식을 동반한다     (중간 생략)      플로이드 워셜 알고리즘을 사용해야 하는 경우 노드의 개수가 500개 이상으로는 주어지지 않는 경우가 많다.  3중 반복문을 사용해서 시간복잡도가 O..

V 는 노드의 개수를 의미한다O(V) 번에 걸쳐서 최단 거리가 가장 짧은 노드를 찾기 위해 O(V) 번 선형 탐색을 해야 하므로 전체 시간 복잡도는 O(V^^2) 이다더욱 효율적으로 동작하는 알고리즘을 설계할 필요가 있다.     최소 힙은 값이 낮은 데이터부터 꺼내는 방식으로 동작하고 (오름차순)최대 힙은 값이 높은 데이터부터 꺼내는 방식으로 동작한다 (내림차순) 단순히 리스트로 우선순위 큐를 구현했을 때,  데이터를 삽입할 때는 단순히 데이터를 맨 뒤에 차례대로 넣으면 되기 때문에 O(1)(상수 시간) 이 걸리지만 데이터를 삭제할 때는 전체 데이터를 순회하며 우선순위가 가장 높은 데이터가 무엇인지 확인해야 하기 때문에 O(N)(선형 시간) 이 걸린다 힙은 내부적으로 트리 구조를 이용하여 데이터의 삽입..

다익스트라 최단 경로 알고리즘은 현실 세계의 길찾기 문제에서 사용될 수 있는 알고리즘이다. 네덜란드의 컴퓨터 과학자 '에츠허르 다익스트라'가 고안한 알고리즘 길찾기 문제 자체는 다이나믹 프로그래밍의 원리가 적용된 문제라고 할 수 있다. 다익스트라 최단 경로 알고리즘은 길찾기 문제 중에서도 탐욕적인 원리를 이용한다는 점에서 그리디 알고리즘으로 분류한다   최단 거리 테이블을 초기화할 때 다른 모든 노드까지 가는 비용은 무한으로 설정하고 자기자신에 대한 노드는 0으로 설정한다  자기자신에서 자기자신으로 가는 비용은 0이라고 볼 수 있기 때문이다     다음 단계로 넘어갈 때 아직 방문하지 않은 노드 중에서 최단 거리 비용이 가장 작은 노드를 선택해야 한다 이때 2번 노드와 5번 노드가 모두 같은 비용을 가지..

LIS 알고리즘   D[i] 는  array[i] 를 마지막 원소로 가지는 부분 수열의 최대 길이이다.   각각의 원소 하나만 이용해서 수열을 만든다 하면 그 길이는 1이기 때문에 1로 초기화   입력을 역순으로 뒤집고 LIS 알고리즘을 수행해서 정답을 도출한다    각각의 원소 하나만 이용해서 수열을 만든다 하면 그 길이는 1이기 때문에 1로 초기화문자열을 역순으로 바꾸는 함수 파이썬은 array.reverse() C++ 은 reverse(array.begin() , array.end()) ,  자바는 Collections.reverse(array) 이다 파이썬 max함수는 몇 개가 들어오든 거의 다 감당 가능하고 C++ max 함수와  자바 Math.max 함수는 2개만 비교 가능해서 코드의 마지막이..

왼쪽 아래나 왼쪽 위를 확인할 때 리스트의 범위를 벗어날 수 있기 때문에 이를 체크해야 한다   DP 테이블에 값을 입력 받은 후 초기값들(dp[i][0]) 을 활용해  1열부터는 각 칸의 최댓값을 찾아서 넣어준다    파이썬은 이런 코드도 가능한가 보다 for tc in range(int(input())):  dp.append(array[index : index + m]) 인덱스 슬라이싱을 이용해서 각 행별로 끊어서 dp테이블에 추가했다 [[1, 3, 3, 2], [2, 1, 4, 1], [0, 6, 4, 7]] 파이썬 max함수는 몇 개가 들어오든 거의 다 감당 가능한 것 같고 C++ max 함수와  자바 Math.max 함수는 2개만 비교 가능한 것 같다.   C++ 코드   자바 코드

f(6)의 값은  f(5), f(3), f(2)의 값에서 1을 더한 값과 같다. (대박) 그래서 f(5), f(3), f(2)  이 세개의 값 중 최소를 찾으면 f(6) 값의 최소를 찾을 수 있다.    f(1)의 최솟값은 0이기 때문에 DP 배열의 값을 0으로 초기화한다 d[i] = d[i-1] + 1 은 모든 수(i) 에서 적용할 수 있기 때문에 맨 위에 배치 최솟값을 업데이트하는 식으로 해도 문제가 생기지 않는다 제일 작은 수인 '2'부터 각 연산을 적용한 값들을 모두 비교해서 최솟값을 확실하게 찾은 후 다음 수로 넘어가기 때문이다             DP[i-2] 값을 안다면 DP[i] 값도 안다는 것을 의미한다    DP[i-2] 값을 만들 수 있다면 DP[i] 값도 만들 수 있다는 의미가 되..

' / ' 는 나눗셈을 의미하며 결과가 float 로 나타난다' // ' 는 나눗셈을 의미하며 결과가 int 로 나타난다  data1 = 5 / 2data2 = 5 // 2print(data1)print(data2)# 출력 결과2.52