컴퓨터공학 💻 도서관📚

이 문제는 간선이 음수가 될 수 있다는 조건을 제외하면 일반적인 다익스트라 알고리즘과 같은 조건이다    (음수 간선)2번 노드 : 2 + 1 + (-2) = 16번 노드 : 2 + 1 + (-2) + 2 + 2 = 5   (음수 간선 사이클) 음수 간선의 순환이 포함되는 경우에는 최소비용을 특정한 값으로 결정할 수 없는 경우가 발생할 수 있다 밑에 예시에서는 음수 간선의 사이클이 발생한다 이때 싸이클에 포함되어 있는 모든 간선에 대한 값을 모두 더하면 음수의 값이 나온다 이 경우에는 싸이클을 반복적으로 도는 과정을 통해서 비용을 무한히 줄일 수 있다그래서 그래프 내에 음수 간선의 순환이 포함되어 있다면, 최소비용, 즉 최단거리가 음의 무한인 노드가 발생한다 -4 + 2 + 1 = -2 -2 + (-2)..

여기에서는 이진 탐색 트리를 어떻게 만드는 건지는 생략하고 하나의 이진 탐색 트리가 있을 때 이진 탐색 트리에서 특정 데이터를 찾는 방법에 대해 소개한다   이진 탐색 트리의 왼쪽과 오른쪽에 대해서 균형이 잡혀 있는 경우, 즉 트리 구조가 이상적일 경우에만 logN 의 시간복잡도를 보장한다      파이썬으로 트리 구조를 구현할 때는 하나의 노드 클래스를 정의해서 구현할 수 있다트리는 간단히 딕션너리로 구현할 수 있다

파이썬의 힙 라이브러리는 기본값이 최소 힙 이다 그리고 최대 힙은 데이터를 넣을 때와 데이터를 뺄 때 - 를 붙이면 된다   C++의 힙 라이브러리는 기본값이 최대 힙 이다   (자바 코드는 없음)

프로토콜의 뜻은, '약속', '규약', '협약'을 의미하는 단어입니다.  네트워크 분야에서는 통신을 원활하게 수용할 수 있도록 하는 통신 규약(약속)이라고 할 수 있다       클라이언트와 서버가 밑에와 같이 자원, 행위, 표현을 포함한 형태로 데이터를 주고 받자고 약속하고 사용하는 것이 REST 이다   interface :  경계면, 접점, 공유 영역       실제 REST API 를 구현할 때는 아무에게나 조회 권한을 줄 수 없기에  실제로는 API를 호출할 때 별도의 인증용 토큰을 같이 보내도록 만들어서 적절한 권한이 있는 사용자일 때 데이터에 접근할 수 있도록 한다

(중간 생략)       쿼리(Query)란 쉽게 이야기해서 데이터베이스에 정보를 요청하는 것이다

하나의 수를 소수 판별할 때   위의 알고리즘은 약수의 성질을 이용하여 시간복잡도를 개선할 수 있다   하나의 소수가 아닌 다수의 소수를 판별해야 하면 에라토스테네스의 체 알고리즘을 활용하면 좋다  (중간 생략)  위에서 본 약수의 성질을 에라토스테네스의 체에서도 사용할 수 있다 N = 26 이라면 그 제곱근 값은 5와 6 사이일 것이다 그렇기에 5까지만 에라토스테네스의 체 알고리즘을 수행하면 더 효율적으로 답을 낼 수 있다 모든 약수는 가운데 약수(제곱근)을 기준으로 대칭이기 때문에 5까지만 확인하면 반대편 약수들은 다 사라졌기 때문에 5 이후부터의 수는 소수만 남게 된다      10억이라는 하나의 수가 소수인지 아닌지 판별하려고 에라토스테네스의 체를 이용한다면 소수 여부를 기록하기 위해 10억개의 ..

사이클이 없는 방향 그래프를 DAG 라고 한다   위상정렬 알고리즘은 DFS, 큐를 이용해서 구현할 수 있다   사이클이 존재하는 방향 그래프라면 사이클에 포함되어 있는 모든 노드는 진입 차수가 1이상이기에 지금과 같이 설계한 경우 사이클에 포함되어 있는 모든 노드는 큐에 들어갈 수 없기 때문에 위상 정렬을 수행할 수 없다    (여러 개의 노드가 한꺼번에 큐에 들어갈 때는 어떤 순서로 들어가도 상관 없지만 예제에서는  더 작은 번호의 노드가 먼저 들어가게 설정했다)  (중간 과정 생략)       C++ 코드  자바 코드

싸이클(Cylce)은 '순환'을 의미한다.  일반적으로 싸이클은 좋지 못한 현상이다.   자칫 무한 루프에 빠질 수 있고 순환을 이루는 개체간의 종속성이 올라간다.  간선을 의존관계라고 생각해보면 A는 C에 의존하고 C는 B에 의존하고 B는 A에 의존한다. 종속성이 커질수록 결합도가 올라가 유지보수가 어려워진다.  원본 그래프에 존재하는 모든 간선을 활용하진 않고 일부 간선을 활용해서 모든 노드가 포함되어 있는 부분 그래프를 만든 것이 신장 트리이다.   최소 신장 트리 (MST, Minimum Spanning Tree)   크루스칼 알고리즘은 간선을 하나씩 확인하면서 최소 신장 트리에 포함을 시킬지, 시키지 않을지를 결정하는 방식으로 동작한다   (원래는 비용에 따라 오름차순 정렬을 해야 하는데 여기에..