기록방

💡 0-1 BFS는 특정 상황의 그래프에서 최단 경로를 찾을 때 사용된다. 가중치가 0과 1로 이루어진 그래프에서 최단 경로를 찾을 때 사용한다.최단 경로를 구할 때 많이 사용하는 우선순위 큐 다익스트라(Dikjstra) 알고리즘은 시간 복잡도가 O(E log V)인 반면에, 0-1 BFS는 일반적인 BFS 시간 복잡도와 같이 O(V + E)의 선형 시간 복잡도를 갖는다.일반 BFS 에서 큐를 사용하는 것과 달리 덱(Deque)을 사용한다. 🚀 0-1 BFS의 동작 과정덱의 front에서 현재 방문한 노드를 꺼낸다.연결된 인접 노드를 살펴본다.(현재 비용+ 다음 노드 가중치) 다음 노드에 기록된 비용을 갱신해 준다.노드가 갱신될 때, 가중치가 0이라면 덱의 front, 가중치가 1이라면 덱의 back..

AWS EC2 환경에 Docker-compose를 이용해서 PostgreSQL 이미지를 컨테이너로 실행시켰다.로컬 IntelliJ에서 연결해서 사용하고 싶었는데, 계속 다음과 같은 오류가 났다. [28P01] FATAL: password authentication failed for user "[유저이름]" Docker-compose.yaml에 설정한 PostgreSQL 명령어는 다음과 같다. version: '3'services: # ~~~ postgres: container_name: postgres_container image: postgres:16.2 restart: always environment: POSTGRES_USER: --생략-- POSTGRE..

1번(4) 데이터 종속성⇒ 파일 구조에 응용 프로그램이 종속적. 파일 구조가 변경되면 응용 프로그램도 함께 변경해야 하는 문제 2번(3) 데이터의 가용성 증가를 위해 중복을 허용하고 싶었다.⇒ 데이터베이스는 데이터 중복을 최소화 한다. 3번(2) 예약 시스템과 같이 최신 정보를 다수의 사용자가 공유해야 하는 경우⇒ 동시 공유는 데이터베이스의 주 기능 4번(2) 데이터베이스의 안정성을 유지하기 위해 사용자의 데이터 공유를 제한한다.⇒ 데이터베이스는 데이터를 동시 공유 할 수 있다. 5번(4) 절차 기능⇒ DBMS의 주요 기능 : 정의, 조작, 제어 6번(2) 조작 기능⇒ 조작 기능 : 데이터를 삽입, 삭제, 수정, 검색하는 연산을 한다. 7번(3) 데이터베이스의 구조를 정의하거나 수정한다.⇒ 정의 기능의 ..

01 데이터베이스 관리 시스템의 등장 배경과거에는 데이터를 관리하기 위해 파일 시스템(file system)이라는 소프트웨어 이용데이터를 파일로 관리할 수 있도록 파일을 생성/삭제/수정/검색하는 기능을 제공운영체제와 함께 설치 됨응용 프로그램별로 필요한 데이터를 별도의 파일로 관리파일 시스템 환경에서는 응용 프로그래머가 파일의 논리적인 구조 뿐 아니라 물리적인 구조까지 정확히 파악해야 함필요한 데이터에 직접 접근하여 처리하는 응용 프로그램 개발을 위해파일 시스템의 문제점같은 내용의 데이터가 여러 파일에 중복 저장된다.파일 시스템에서는 응용 프로그램 별로 파일을 유지하므로 같은 데이터가 여러 파일에 저장될 수 있다. 데이터 중복성(data redundancy) 문제가 발생한다.데이터가 중복되면 저장 공간이..

분리 집합(Disjoint Set)은 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는 지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다. union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산 find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산 Union-Find 원리 이해하기 Union-Find를 표현하는 일반적인 방법은 1차원 배열을 이용하는 것 처음에는 노드가 연결되어 있지 않으므로 각 노드가 대표 노드가 됨 각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스 값으로 초기화 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 union 연산을 수행 대표 노드가 아..