전체 글
백준 19238 스타트 택시(BFS, 구현)
19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 택시가 서있는 위치에서 여러손님들 가운데 최단거리에 있는 손님 먼저 채우고 손님 목적지 까지 태우는 단순한 구현 문제이다. 이 문제가 까다로웠던 이유는 한 손님의 운송이 끝나면 그 손님에 대한 방문처리를 해줘야하는 것과 어떤 손님을 먼저 태울지에 대한 우선순위 조건이 2개나 있어서 조건문을 구현하기 힘들어서 어려웠다. 최단경로를 구할려 할 때 플로이드-와샬을 쓰려고 했지만 가중치가 나오지 않았기 때문에 그냥 BFS를 써서 그..
MVC 패턴
MVC(Model View Controller) patten 어떤 작업을 수행함에 있어 수십 혹은 수백 명의 개발자들이 공통되게 코드를 작성하는 방식 유지보수, 확장성, 프레임워크 사용 용이 Model 데이터를 담거나 데이터베이스로 데이터를 보내는 작업과 관련된 객체(DTO, DAO) Business Logic Encapulation(Service) Persisttance Logic Encapsulation(DAO) Data(VO) View 사용자 입력화면 제공 Model Data 화면 출력 응답화면 출력 Controller MainServlet Model과 View사이를 제어 Client입력 데이터 체크 Model의 business method 호출 Model로부터 응답 받은 Data 일정 범위에 저장..
Coding Test(Topological Sort)
위상 정렬(Topological Sort) 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 선행 조건들을 만족하는 일의 수행 순서 특정 노드를 방문하려면, 조건으로 갖는 다른 노드들이 방문된 상태여야함 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다 위상정렬에서 중요하게 쓰이는 개념인 진입차수와 진출차수 1. 진입차수가 0인 모든 노드를 큐에 넣는다(진입차수가 0이라는건 시작점이라는 뜻) 2. 큐가 빌 때 까지 다음의 과정을 반복한다 2-1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2-2) 새롭게 진입차수가 0이 된ㄷ 노드를 큐에 넣는다 => 결과적으로 각 노드가 Queue에 들어온 순서가 위상 ..
백준 2623 음악프로그램(위상정렬, DFS, BFS)
2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 재미있는 문제였다. 각 PD들이 가수들의 무대순서를 정하고 각각 PD에 요청에 모두 부합하는 완벽한 순서를 만들어내는 것이 문제다. 먼저 문제를 읽고 생각을 해봤을 때 순서라는 점이 가장 Key-Point라는 생각이 들었다. 따라서 순서라는 점을 계속 기억하고 인지하기 위해 Queue, Stack이라는 자료구조를 통해서 기억했으면 좋겠다라는 생각을 했고 더 나아가서 이 자료구조를 통해서 Next step까지 생각하는거니까 DFS, BFS문제구..
JSP Programming
Servlet은 HTML in Java이기 때문에 HTML에 해당하는 모든 태그들에 대해서 out.println()을 해줘야했지만 JSP는 Java in HTML이기 때문에 Java에 해당하는 부분만 script 문법으로 추가해준다. Servlet programming 보다 훨씬 간편하고 간단하게 해결 가능 JSP 스크립팅 요소(Scripting Element) 1. 선언(Declaration) 멤버변수 선언이나 메소드를 선언 하는 영역 2. 스크립트릿(Scriptlet) Client 요청 시 매번 호출 영역, Servlet의 service()에 해당되는 영역, request, response에 관련된 코드 구현 3. 표현식(Expression) 데이터를 브라우저에 출력할 때 사용 Name : 4. 주석..
백준 3967 매직 스타(DFS)
3967번: 매직 스타 매직 스타의 모양이 주어진다. 수가 채워져 있지 않은 곳은 x로, 채워져 있는 곳은 'A'부터 'L'까지 알파벳으로 채워져 있다. i번째 알파벳은 숫자 i를 의미한다. '.'는 매직 스타의 형태를 만들기 www.acmicpc.net 문제는 어렵지 않았지만 시간초과에 대해서 많이 고전한 문제다. 단순히 빈칸에 대해서 사용할 수 있는 알파벳을 하나씩 넣어보고(완전탐색) 합이 26이 되면 종료하는 문제 근데 여기서 문제는 완전탐색을 해버리겠다고 한다면 빈칸에 대해서 넣어볼 수 있는 알파벳 여러개를 한번씩 모두 넣어본다는 것(순열)인데 이 문제는 그런 모든 경우를 구하는 문제가 아니다. 아래 코드에 보면 DFS의 재귀부분에 break;를 넣었는데 이 부분이 매우 핵심적인 부분이다. 문제에..
Servlet Programming
implements Servlet를 하면 여러가지 method가 나온다 service, init, destory ... 여러가지가 있는데 가장 필요한것은 service 따라서, extends GenericServlet라는 추상클래스를 상속하면 우리가 필요한 service만 override가능 그래서 서버의 역할 Data get, logic, response 3가지의 역할을 service에서 하려고하는데 근데 문제가 생김!!! GET방식은 url?key=value&key=value ... 이런식으로 가는데 한글이 데이터로 넘어갈경우 브라우저 url에선 한글 그대로 보이지만 실제 넘어갈때는 https://search.naver.com/search.naver?where=nexearch&sm=top_hty&fb..