Study29 다익스트라 알고리즘 1.기본개념다익스트라 알고리즘은 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 찾는 알고리즘이다. 가중치가 있는 방향 그래프 또는 무방향 그래프에서 작동하며, 음수 가중치는 허용되지 않는다. 이 알고리즘은 주로 우선순위 큐를 사용하여 효율적으로 최단 경로를 찾는다. 다익스트라 알고리즘의 주요 특징:시작 정점에서 다른 모든 정점으로의 최단 경로를 계산그리디 알고리즘의 일종으로, 매 단계에서 가장 비용이 적은 경로를 선택우선순위 큐를 사용하여 최단 경로를 효율적으로 갱신 2. 구현 예제class PriorityQueue { constructor() { this.values = []; } enqueue(val, priority) { this.val.. 2024. 7. 12. Max-Heap 알고리즘 1.기본개념Max-Heap은 이진 트리의 일종으로, 부모 노드가 자식 노드보다 항상 크거나 같은 값을 가지는 특성을 가짐Max-Heap의 규칙:완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽에서 오른쪽으로 채워짐부모 노드의 값이 자식 노드의 값보다 크거나 같음Max-Heap 배열로 표현인덱스 i의 노드는 다음과 같은 자식 노드와 부모 노드의 관계를 가짐왼쪽 자식 노드: 2i + 1오른쪽 자식 노드: 2i + 2부모 노드: (i - 1) // 2 ( // : 정수 나눗셈 연산자 - 소수점 이하를 버리고 정수 부분만을 반환)Index: 0 1 2 3 4 5 6 7 8Array: [20, 15, 18, 8, 10, 5, 7,.. 2024. 7. 12. C++ 을 시작하기 앞서 간단한 소개 1. C++이란 C++의 정의와 기본 개념 소개 C++은 C 언어의 확장으로, 객체 지향 프로그래밍과 절차적 프로그래밍을 모두 지원하는 프로그래밍 언어이다. 객체 지향 프로그래밍: 현실 세계의 개념을 프로그램에 반영할 수 있게 해주며, 코드의 재사용성과 유지보수성을 높여준다. 절차적 프로그래밍: 명령어의 집합으로 프로그램을 구성하는 방식으로, 일련의 절차를 따라 순차적으로 실행된다. C++의 역사와 발전 과정 C++은 1980년대 초에 Bjarne Stroustrup에 의해 개발되었다. 초기에는 C with Classes라는 이름으로 시작했으며, 이후에 C++로 이름이 변경되었다. C++은 지속적인 발전을 거쳐 표준화된 형태로 발표되었고, 현재는 ISO 표준으로 사용되고 있다. 2. C++의 주요 특징들.. 2023. 10. 14. 4. Threads - Threading issues fork() and exec() fork() 시스템 호출은 현재 실행 중인 프로세스를 복제하여 자식 프로세스를 생성 자식 프로세스는 부모 프로세스의 모든 자원을 상속 exec() 호출은 현재 프로세스를 다른 프로그램으로 대체 Cancellation : 스레드를 즉시 종료시키는 기능 비동기식 I/O 작업에서 사용 일반적으로 스레드를 종료하기 위해 pthread_cancel() 함수를 사용 Signal handling 프로세스 또는 스레드가 다른 프로세스 또는 운영 체제로부터 수신하는 메시지 Thread-local storage 스레드별로 고유한 데이터를 저장하기 위한 메커니즘 스레드 간에 공유할 필요가 없는 데이터를 저장하고 검색할 수 있음 Scheduler activation (already covere.. 2023. 4. 12. 이전 1 2 3 4 ··· 8 다음
