1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 단순한 그리디 알고리즘으로 풀린다. 회의시간이 주어졌을 때 1)끝나는 시간이 가장 빠른 회의를 먼저 선택 2)해당 회의시간과 겹치지 않는 회의가 나오면 그 회의를 또 선택 .. 이렇게 반복해서 회의 선택할 때마다 +1 을 해주면 최대로 진행할 수 있는 회의 수가 된다. 하지만 해당 문제에서 주어지는 회의시간이 끝나는 시간 대로 정렬되지 않았기 때문에 먼저 끝나는 시간 별로 들어온 회의 정보를 정렬해준다. 그렇다고 끝나는 시간별로만 정렬을 해주면 틀린다. 왜냐하면 8시 시작 8시 끝 5시 시작 8시 끝 이렇게 주어진 회의의 경우, 정렬하였을 때도 8-8 5-8 이렇게 정렬되기 때문..
11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 해당 문제는 최단경로를 구하는 문제이지만 '음수 경로'를 허용하고 있으므로 다익스트라가 아니라 벨만 포드를 사용해야 한다. 다익스트라는 그리디 방법이기 때문에 음수 경로가 있을 때 최단 경로를 선택하지 않을 수 있다. 하지만 벨만포드 알고리즘은 V-1번의 relaxation 과정을 통해 모든 엣지를 돌며 각각 노드의 모든 indegree로부터의 최저 가중치를 계산하게 되므로, 음수 경로를 허용한다. 하지..
[JSP 기초] Cookie 에 대해 알아보자 !
Cookie란 무엇일까 ? 쿠키란 말 그대로 "먹다가 흘린 쿠키" 처럼 생각하면 된다 . 쉽게 생각하여 서버와 클라이언트가 연결을 시도한 흔적이라고 생각하면 된다. http 프로토콜은 하나의 서버에 수많은 클라이언트가 붙게 되면 서버 부하가 발생하기 때문에 이를 방지하기 위해서 브라우저 (클라이언트)와 서버 사이의 응답 요청이 종료되면, 연결을 해제한다. 하지만 로그인 페이지나, 쇼핑몰같은 페이지에서 내가 웹페이지에 정해둔 정보가 새로고침할 때마다 초기화 된다는 것은 매우 불편하다. 이를 위한것이 바로 '쿠키'이다. 쿠키는 일단, 서버에 저장되지 않고 브라우저 (클라이언트) 에 저장된다. 쿠키에는 기존의 연결 정보들이 저장되며, 나중에 다시 접속 시, 이 쿠키를 가지고 과거의 접속을 이어나갈 수 있다! ..
연결성분 그래프에서 최대로 연결된 부분 그래프 어떻게 구할까 방법은 간단하다. 정점을 차례대로 DFS/BFS 를 실행한다. -> 이때 방문되면 서로 연결되어 있음 해당 visited 배열에 boolean 값 대신, 각각의 부분그래프를 나타낼 요소를 넣는다. visted 배열을 돌려가며 가장 빈도수가 높은 숫자의 요소들을 출력한다. * 아래 연결성분 찾는 메서드는 그래프의 간선이 1-2-3 4-5 이렇게 순차적으로 되어있다고 가정한것. - dfs 메서드를 포함한 graph 클래스 (인접리스트로 구현) class Graph{ private static int vn; //정점개수 private static int[] visited; //방문여부 private static ArrayList graph = new..