Struggling Journey

다익스트라 알고리즘은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘. 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산함. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작. 다익스트라 알고리즘 동작 과정 출발 노드를 설정함. 최단 거리 테이블을 초기화함. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택함. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신함. 위 과정에서 3번과 4번을 반복함. 알고리즘 동작 과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있음. 처리 과정에서 더 짧은 경로를 찾으면 갱신함. 다익스트라 알고리즘을 수행한 뒤에 테이블에 ..

신장 트리 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 함. 최소 신장 트리 최소한의 비용으로 구성되는 신장 트리 크루스칼 알고리즘 최소 비용 신장 트리를 찾는 알고리즘 Edge의 개수를 E, Vertex의 개수를 V라고 하면 이 알고리즘은 O(ElogV)의 시간복잡도를 갖는다. 구체적인 동작 과정 간선 데이터를 비용에 따라 오름차순으로 정렬 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 사이클이 발생하는 경우 최소 신장 트리에 포함 X 모든 간선에 대하여 2번의 과정을 반복 [참고] ko.wikipedia.org..

1. 식별자(Identifiers) 개념 식별자는 엔터티를 구분짓는 논리적인 이름 식별자는 엔터티를 대표할 수 있는 속성 엔터티에는 반드시 하나의 유일한 식별자가 존재한다. 2. 식별자의 특징 주식별자에 의해 엔터티내에 모든 인스턴스들이 유일하게 구분되어야 한다. 주식별자를 구성하는 속성의 수는 유일성을 만족하는 최소의 수가 되어야 한다. 지정된 주식별자의 값은 자주 변하지 않는 것이어야 한다. 주식별자가 지정이 되면 반드시 값이 들어와야 한다. 3. 식별자 분류 및 표기법 가. 식별자 분류 나. 식별자 표기법 4. 주식별자 도출기준 ▶주식별자 도출 기준 해당 업무에서 자주 이용되는 속성을 지정한다. 예) 직원(엔터티)-사원번호, 주민번호 예) 주문자(엔터티)-고객 등록번호, 주민번호, 이메일, 핸드폰번..

programmers.co.kr/learn/courses/30/lessons/42583 1. 문제 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 경과 시간다리를 지난 트럭 다리를 건너는 트럭 대기 트럭 0 [] [] [7,4,5,6] ..

programmers.co.kr/learn/courses/30/lessons/42587 1. 문제 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 ..

www.acmicpc.net/problem/10825 1. 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키 코드에서 대문자는 소문자보다 작으므로 사전순으로 앞에 온다.) 입) 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거..

www.acmicpc.net/problem/10816 1. 문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입) 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다..

www.acmicpc.net/problem/1920 1. 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입) 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31 보다 크거나 같고 2^31보다 작다. 출) M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 2. 풀이 import java.util.Arrays; import java.util.Scan..