매일 조금씩

이게 골드라니?! 하는 문제였다. 골드가 다 이러면 얼마나 좋을까.. 강의실을 넘겨받을수 있냐없냐 문제다. 1~3시 강의실을 2~4강의가 넘겨받을수없으므로 새로운 강의실이 필요하다. 3~5시 강의면 1~3시 강의실을 넘겨받을 수 있다. pq의 기본 정렬은 내림차순이므로 강의실별 강의 끝나는 시간을 -를 붙여서 pq에 넣는다. 만약 어떤 강의가 pq의 top에 있는 가장 빨리 끝나는 강의보다 시작시간이 같거나 늦으면 pop 하고 빠르면 pop하지 않는다. 그리고 그 강의의 끝나는 시간을 pq에 넣는다. #include #include #include #include #include using namespace std; int n; const int MAX = 200001; pair arr[MAX]; // ..

서류순위와 면접순위 어느것 하나 낮은것이 없어야한다는 것이 포인트다. 서류순위대로 오름차순정렬한다. (1등이 제일 앞에옴) 서류 1등의 면접 순위를 따로 저장한다. (int interview) 서류1등인 인덱스 0을 제외한 인덱스 1부터 n-1까지 중에서 면접순위 값이 interview값보다 작은것을 찾는다. 3번을 통해 발견한 값을 interview 값으로 갱신하고 count를 증가시킨다. 3,4번을 반복한다. #include #include #include #include using namespace std; int t, n; const int MAX = 100000; pair arr[MAX]; int result[MAX]; int main(void) { cin >> t; for (int tc = 0..

알고리즘을 풀기 전, 최단 경로 알고리즘은 크게 두가지로 나뉜다는 것을 배웠다. 다익스트라 알고리즘은 그리디 알고리즘의 성격을 띠며 한지점에서 여러지점으로 가는 최단 경로를 구한다. 플루이드 워셜 알고리즘은 여러지점에서 여러지점으로 가는 최단 경로를 구한다. 따라서, 다익스트라는 배열에 노드별 결과값을 저장하며 플루이드 워셜은 이차원 배열에 결과값을 저장한다. 이번에 풀어본 "전보"라는 문제는 시작지점인 START에서 다른 노드들로 가는 최단 거리를 구한 다음, 도달할 수 있는 노드의 갯수와 구한 최단 거리들 중 가장 짧은 거리를 구하는 문제였다. 문제는 다음과 같다. 풀이는 다음과 같다. #include #include #include #include #include #define INF 1e9 usi..

2. 플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. 플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다. 플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다. 플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다. 각단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사한다.점화식은 다음과 같다. $$D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$$ #include..

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 다양한 문제 상황이 있다. 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현한다. 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 1. 다익스트라 알고리즘 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다. 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다. (현실 세계의 도로(간선)은 음의 간선으로 표현되지 않음) 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다. 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복하기 때문. 알고리즘의 동작과정 출발 ..

전자정부프레임워크 = Spring/MyBatis MariaDB (여기까지 java 끝) (오늘 새로 들어갈거) * System 가상머신 - 하드웨어에 대한 가상화 * Intel / Virtualization(메인보드) 가 지원을 해줘야함 * 속도 느려짐 .. * 윈도우 업데이트 1. VMWare - VMWare (유로 / 무료(*)) 2. VirtualBox - Oracle (무료 - 느림) 리눅스 프로그램 2개 ubuntu centos -> www.centos.org egovFrame template project 를 mariaDB용으로 만들기 egov teplate project로 프로젝트를 만들면 가상 데이터들을 넣어야 확인이 가능한데 그걸 넣으라고 DATABASE안에 DB 종류별로 데이터를 넣는 ..