공부 기록장

0/1 knapsack, 배낭채우기 문제는 DP에서 유명한 문제 중 하나이다. 1) N개의 물건에 각각 무게 정보와 가치 정보가 주어지고 2) W의 무게까지 담을 수 있는 가방이 있을 때, 3) 가방의 가치를 가장 높게 만들어 줄 물건들을 담아야 한다. 보통은 도둑이 물건을 훔쳐갈 때, 들고갈 수 있는 무게는 제한적이니 그런 것들을 이용해서 알고리즘 문제가 나오더라. 하지만 오늘은 특정 문제를 포스팅 하는게 아니라, 알고리즘 자체를 올려보려고 한다. 이 알고리즘의 로직은 1) 첫 물건부터 끝 물건까지, 가방의 무게를 1부터 W까지 모두 고려해서 2) 물건의 무게가 현재 가방의 무게보다 작거나, 같으면 넣어본다. 2-1) 이번 아이템을 넣지 않았을 때와, 넣었을 때를 비교해서 더 큰 값을 저장해주는 방식이..

MySQL에는 진짜 수많은 내장함수들이 있다. 너무 많아서 다 못 외울 것 같아서 내가 찾아서 보려고 만들었다. 숫자 관련 함수 문자 관련 함수 날짜 관련 함수 날짜 형식 - 주의해야 할 점이 있다면 분은 i라는 것! (오라클에서는 mi로 알고 있다) 논리 관련 함수 그룹함수 / 집계함수

RDBMS란? 관계형 데이터베이스 시스템을 말한다. RDBMS는 테이블 기반의 DBMS로, - 데이터를 테이블 단위로 관리하며, 하나의 테이블은 여러개의 컬럼으로 구성되어 있다. - 같은 데이터가 여러 컬럼 또는 테이블에 존재하면 데이터를 수정할 때 문제가 발생할 가능성이 높아진다. - 따라서, 정규화를 진행해 중복 테이터를 최소화 시킨다. - 여러 테이블에 분산되어 있는 데이터를 검색 할 때, 데이블 간의 관계를 이용해 데이터를 검색한다. 가장 중요한 점은, 다른 테이블과의 관계를 갖고 있다는 것이다. SQL은 DV에 있는 정보를 사용할 수 있도록 지원하는 언어이다. 모든 DBMS에서 사용이 가능하며, 대소문자를 구별하지 않는다. SQL 구문은 DCL, DDL, DML, TCL로 구분할 수 있다. DD..

사용자 입장에서, 웹 브라우저와 인터넷만 있으면 인터넷에 접속해서 뭐든지 할 수 있다. 하지만 개발자의 입장에서는, 사이트를 사용하기 위해 프론트엔드와 백엔드를 처리해주어야 한다. 프론트엔드에 쓰이는 html, css, js 등은 웹 서버에서 처리해주고, DB를 사용하기 위해 사용하는 java는 어플리케이션 서버에서 처리해준다. Web Application Architecture JSP 를 이용하여 구성할 수 있는 웹 어플리케이션 아키텍트는 크게 model1과 model2로 나뉜다. 1) JSP 가 클라이언트의 요청에 대한 logic처리와 response page(view) 에 대한 처리를 모두 하는지, 2) response page(view) 에 대한 처리만 하는지가 가장 큰 차이점이다. Model1 ..

JSP(Java Server Page) - JSP는 HTML 내에 자바 코드를 삽입하여 웹 서버에서 동적으로 엡 페이지를 생성하여 웹 브라우저에 돌려주는 언어이다. Java EE 스펙 중 일부로, 웹 애플리케이션 서버에서 동작한다. JSP는 실행시에는 자바 서블릿으로 변환된 후 실행되므로 서블릿과 거의 유사하다고 볼 수 있다. 하지만 서블릿과는 달리, HTML 표준에 따라 작성되므로 웹 디자인하기에 편리하다. 아파치 스트럿츠나 자카르다 프로젝트의 JSTL 등의 JSP 태그 라이브러리를 사용하는 경우에는 자바 코딩없이 태그만으로 간략히 기술이 가능하므로 생산성을 높일 수 있다. JSP는 이런식으로 흘러간다. JSP의 특징 jsp는 1. 선언 - 멤버변수나 메소드 선언시에는 에 자바코드와 동일하게 선언해준다..

이 알고리즘은 Floyd-Warshall 알고리즘이라고 불리기도 하고, 줄여서 floyd 알고리즘이라고 불리기도 한다. 이 알고리즘도 다익스트라와 비슷하게, 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치의 합이 최소인 경로를 찾는 것이다. 하지만 다익스트라와는 다르게 가중치가 음의 값을 가지고 있어도 되고, 모든 쌍의 최단경로를 구하는 알고리즘이기 때문에 계산이 끝난 후에는 내 마음대로 출발점과 끝나는 점을 잡아도 최소 거리를 알려준다. 이 알고리즘은 점화식을 통해 계산을 하는데, 간단하게 생각해야 이해하기 쉽다. 1) 출발지에서 경유지를 거쳐, 도착지 까지 간다. 2) 출발지에서 도착지로 바로 가는 경우와 출발지에서 경유지를 거쳐 도착지로 가는 경우 중 더 빠른 길을 담아둔다..

다익스트라 알고리즘은 DP를 활용한 최단경로 탐색 알고리즘이다. 흔히 인공위성 GPS SW등에서 많이 사용되며, 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 하지만 그 간선중에 음수가 있어서는 안된다. 다익스트라 알고리즘이 DP인 이유는 여러개의 최단거리를 모아서 최종 최단거리를 만들기 때문이다. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단거리들의 정보를 활용해서 구한다. 다익스트라 알고리즘을 구현하기 위해 1) 시작점, 끝점(start, end) 2) 간선의 정보가 담겨있는 배열(adjMatrix) 3) 최단거리가 담겨있는 배열(distance) 이 필요하다. 다익스트라 알고리즘은 1) 하나의 기준점 잡기 2) 기준점으로부터 가장 가까운 점 찾아서 그리로 이동 3) ..

PRIM 알고리즘 또한 크루스칼과 비슷하게 최소신장트리 알고리즘 중 하나이다. 프림 알고리즘은 하나의 정점을 시작점으로 하여 cycle을 생성하지 않는 범위 내에서, 최소 가중치를 가지는 정점을 하나씩 포함하여 N-1개의 간선까지 확대하는 알고리즘이다. 1) 임의의 정점을 시작 정점으로 택해서 최소 신장트리의 루트 노드로 삽입하기. 2) 최소 신장트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사하여 이 가중치가 가장 작은 간선을 골라 최소 신장트리에 삽입 3) 모든 점이 다 연결될 때 까지 반복. public class MST_PRIM { public static void main(String[] args) throws IOException{ BufferedRe..