공부 기록장

일반적으로 웹사이트 가서 기사를 누르거나, ID,비밀번호 입력 후 로그인 버튼 누르기 등, 무언가 클릭하면 동작이 일어난다. 이런 동작을 수행하려면 어디엔가 저장되어 있는 정보를 불러다가 검사해야 하는데, 정보를 저장해두기 위해서는 DB가 필요하다. 하지만 프론트엔드는 DB와 직접 통신할 수 없다. 따라서 Backend는 Front-End 와 DB를 연결해주는 역할을 한다. java에서 웹을 지원해주는 API는 Servlet / JSP 등이 있는데, 이번에는 Servlet을 다뤄볼 것 이다. 기본적으로 웹 브라우저(클라이언트)만 있으면 웹을 실행할 수 있다. 웹 브라우저는 html, java script, css등 으로 이루어져 있는데, 이 친구들은 결과적으로 사용자한테 화면을 보여주고 무언가를 입력 받..

크루스칼 알고리즘은 대표적인 최소신장트리 알고리즘 중 하나이다. 간선을 하나씩 선택해서 MST(최소신장트리)를 찾는 알고리즘이다. 1) 최초로 모든 간선을 가중치에 따라 오름차순으로 정렬한 뒤, 2) 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다. 이때, 사이클이 존재하면 다음으로 가중치가 낮은 간선을 택한다. 3) 간선이 모두 선택될 때 까지 2를 반복한다. 지난번 포스팅에서 다뤘던 Union-Find 알고리즘을 응용해서 만드는데, 새로운 자료형을 선언해 주는 것이 편하기 때문에 Edge라는 자료형을 만들어주었다. 간선이 어디에서 와서 어디로 가는지, 가중치가 얼마인지에 대한 정보가 담겨있다. static class Edge implements Comparable{ int from,to,we..

Union-Find 알고리즘은 최소신장트리 알고리즘에 많이 쓰이지만 사실은 서로소 집합을 찾는 알고리즘이다. 서로소 집합은 서로 중복 포함된 원소가 없는 집합들, 즉 교집합이 없는 집합이다. 따라서 집합에 속한 하나의 특정 멤버인 대표자를 이용해 각 집합들을 구분한다. 서로소 집합을 표현하는 방법에는 대표적으로 연결 리스트와 트리가 있다. 연결 리스트 - 같은 집합의 원소들은 하나의 연결리스트로 관리하고, 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. - 즉, 연결리스트의 헤드가 대표자가 되는 것이다. - 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다. 트리 - 트리도 연결리스트와 비슷하다. 자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다. 이런 서로소 집합들을 서로 연결 ..

이 문제는 백준 골드5 레벨의 문제이다. 이 문제는 벽 부수고 이동하기랑 비슷한 문제이다. 벽 부수고 이동하기보다 조금 더 어려운 것 같은데, 레벨은 더 낮다. 왜지... 근데 벽 부수고 이동하기 문제 풀기 전에 이 문제를 만났다면 못 풀었을 것 같다. 이 문제의 포인트는 평상시처럼 4방향만 도는게 아니라 말처럼 움직이는 것 까지, 총 12 방향으로 움직이는 것을 고려해 주어야 한다는 것이다. 델타 배열을 사용해서 움직일건데 인덱스가 0부터 3일때 까지는 왼쪽부터 시계방향으로, 4-11까지는 대각선으로 움직이게 만들었다. bfs를 돌 떄, 1) 칸을 넘어가거나, 방문 할 수 없는 곳이라면 pass. 2) 말 처럼 움직일 건데 점프 횟수가 남아있지 않아도 pass. 3) 벽 부수고 이동하기 때 처럼 같은 ..

이 문제는 백준 골드 4 레벨의 문제이다. 등산로 조성이라는 문제와 비슷하다고 생각했는데, 뭔가 조금 달랐다. 생각해보니 등산로 조성은 포스팅을 한 적이 없는데, '가장 높은 봉우리에서 출발해서 낮은 곳으로 내려오며 가장 긴 등산로의 길이를 찾으면 된다. 이 때, 주어진 K만큼 혹은 그 이하로 딱 한번 자를 수 있다' 라는 문제 였던 것으로 기억한다. 그래서 비슷하게 풀어보려고 했는데, 그렇게 풀었더니 왕창 꼬여서 실패했다. 결국 아예 다른 방법으로 풀었다. 보통 bfs를 돌릴 때, boolean 형 visited 배열을 이차원 배열로 설정해주는데 이번에는 3차원 배열로 설정해 주었다. 그 배열을 방문했는지/안했는지에 추가로 벽 부수기를 사용 했는지/안했는지로 나누어서 생각해주었다. 보통의 bfs와 다른..

이 문제는 swea D6 레벨 문제이다. 이 문제는 플로이드-마샬, Floyd 알고리즘을 가지고 풀었다. 1) 모든 경유지에 대해서 2) 출발지부터 도착지까지 가는데, 경유지를 거쳐서 가는 것과 바로 가는 것 중에 작은 값을 저장해준다. 라는 어찌보면 간단한 완전탐색 알고리즘이다. 근데 만약 이 알고리즘을 배우지 않았다면 좀 많이 헤맸을 것 같다. import java.util.Scanner; public class 사람네트워크2 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int tc=1; tc

이 문제는 백준 골드 5 레벨의 문제이다. 처음에는 어떻게 풀어야 할 지 감도 안오고 막막했는데, 단계를 하나씩 나누어서 생각해 보았다. 1) 벽은 무조건 3개를 놓아야 하니까, 벽을 설치할 3곳 찾기. 2) 벽 설치할 곳 찾았으면 벽 설치. map에서 벽 부분 1로 바꿔주기 (순열 짜는 코드 이용) 3) 바이러스 퍼트리기 (bfs 이용, 바이러스가 갈 수 있는 모든 곳에 다 보내기) 4) 안전영역 세주기 5) 다음 번을 설치해 주기 위해 원상복구 시키기. 이 과정을 완전탐색으로 반복했다. 원래는 혼자서 bfs 짜는 법도 몰랐는데 조금씩 늘어가고 있는 것 같다. 갈 길이 아직 멀긴 하지만, 천천히 하다보면 조금씩 늘겠지 뭐.. import java.util.Arrays; import java.util.L..

Greedy 알고리즘을 사용하면 눈 앞에 보이는 최적의 해답을 찾아서 이동하기 때문에 빠르게 답을 구해낼 수 있지만, 그리디 알고리즘만으로는 해결하지 못하는 경우가 있다. 그럴때는 완전탐색 기법을 사용해서 해결한다. 완전 탐색 혹은 완전 검색이라고 불리는 이 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. 이 방법은 Brute-force 혹은 generate-and-test 기법으로도 불리는데 모든 경우의 수를 테스트 한 후 최종 해법을 도출해낸다. 장/단점으로는 모든 경우의 수를 생성하고 테스트하기 때문에 수행속도가 느리다고 오래걸린다는 단점이 있다. 하지만 모든 경우의 수를 다 검색해 보기 때문에 해답을 찾아내지 못할 확률이 적다. 느리긴 하지만, 크기 제한이 ..