컴퓨터공학 💻 도서관📚

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

[ 이 문제를 보고 느낀점 :  알고리즘은 지저분해 보이지만 자세히 보면 예쁜 학문이다. ]        와..... 이걸 점화식으로 한 코드로 끝냈다고... 미친.. 슈퍼 플레이   자바 최댓값 알려주는 함수 :  Math.max()

다이나믹 프로그래밍이란 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 해 수행 시간 효율성을 비약적으로 향상시키는 알고리즘이다. 다이나믹 프로그래밍은 동적 계획법이라고도 부른다자료구조에서 동적 할당의 '동적' 은 '프로그램이 실행되는 도중에' 라는 뜻을 담고 있지만알고리즘에서 다이나믹 프로그래밍의 '다이나믹' 은 별다른 의미 없이 사용된 단어이다.   1. 문제를 작은 문제로 쪼갤 수 있고,  2. 중복되는 문제들이 있다면  DP 를 활용할 수 있다.     피보나치 수열은 다아나믹 프로그래밍을 활용해서 풀 수 있는 대표적인 문제이다  1) 재귀함수를 이용한 피보나치 수열 피보나치 수열 점화식 :  An = An-1 + An-2재귀적으로 호출되는 부분 :  An-1 + An-2 ..