컴퓨터공학 💻 도서관📚

다익스트라 최단 경로 알고리즘은 현실 세계의 길찾기 문제에서 사용될 수 있는 알고리즘이다. 네덜란드의 컴퓨터 과학자 '에츠허르 다익스트라'가 고안한 알고리즘 길찾기 문제 자체는 다이나믹 프로그래밍의 원리가 적용된 문제라고 할 수 있다. 다익스트라 최단 경로 알고리즘은 길찾기 문제 중에서도 탐욕적인 원리를 이용한다는 점에서 그리디 알고리즘으로 분류한다   최단 거리 테이블을 초기화할 때 다른 모든 노드까지 가는 비용은 무한으로 설정하고 자기자신에 대한 노드는 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++ 코드   자바 코드