L.O.K

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net ◎ 문제풀이 두 개의 노드에서 공통 부모를 찾는 문제이다. 1) 부모테이블을 만든다. 2) 루트를 찾는다. 3) While문 안에 While문을 넣어 이중for문처럼 하나씩 비교하여 공통부모를 찾는다. ◎ 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..

2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net ◎ 문제풀이 아직 투포인터 알고리즘에 대학 숙련도가 낮아 처음에 투포인터를 어디에 위치시켜야 할지를 몰랐다. [BOJ] 백준 2230번 : 수 고르기 (JAVA) 문제 N(1≤N≤100,000)개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하 steady-coding.tistory.com 위 블로그에..

[Network] 서브넷 마스크 이해하기 ( Subnet Mask ) IP는 장비에 부여되는 가변적인 주소이다. 동일한 영역에 모여있는 장비는 연결되어 네트워크를 형성하는데, 이를 LAN(Local Area Network)이라 부른다. LAN의 입구 역할은 라우터가 하는데, 이를 게이 lordofkangs.tistory.com 지난 포스팅에서 서브넷 마스크를 29로 하여 6개의 장비에 IP를 부여해보았다. 네트워크주소 브로드캐스트주소 호스트주소 부여 가능한 IP 203.230.8.0 203.230.8.7 203.230.8.1 ~ 203.230.8.6 할당완료(0개) 203.230.8.8 203.230.8.15 203.230.8.9 ~ 203.230.8.14 6개 203.230.8.16 203.230.8...

IP는 장비에 부여되는 가변적인 주소이다. 동일한 영역에 모여있는 장비는 연결되어 네트워크를 형성하는데, 이를 LAN(Local Area Network)이라 부른다. LAN의 입구 역할은 라우터가 하는데, 이를 게이트웨이(Gateway)라 부른다. 그러므로 한 LAN에서 다른 LAN으로 데이터를 전송하려면 우선 게이트웨이가 위치한 네트워크에 도착해야 한다. 집주소를 떠올리면 이해가 쉽다. 경복궁을 간다고 가정해보자. 경복궁 주소는 아래와 같다. 서울특별시 종로구 / 사직로 161 경복궁에 가려면 우선 서울특별시 종로구(네트워크 주소)에 가야한다. 그리고 상세주소인 사직로 161(호스트 주소)을 찾아가야 한다. IP도 마찬가지이다. 우선 네트워크를 찾아가야 되고 게이트웨이에 입성하면 호스트 주소로 장비를 ..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net ◎ 문제풀이 가장 기본적인 플로이드-워셜 알고리즘 문제이다. [Algorithm] 플로이드-워셜(Floyd-Warshall) 알고리즘이란? [Algorithm] 다익스트라 알고리즘(Dijkstra)이란? 다익스트라 알고리즘(Dijkstra) 다익스트라 알고리즘은 특정지점에서 다른지점으로 가는 최단경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 그 lordofkangs.tistory.com 알고리..

12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net ◎ 문제 풀이 [PS] BOJ12015 가장 긴 증가하는 부분수열2 ( LIS ) with JAVA 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net ◎ 문제풀이 DP는 lordofkangs.tistory.com (위 문제와 풀이는 똑같다. ..

[SpringMVC] API 예외처리하기(2) - HandlerExceptionResolver 컨트롤러에서 에러가 발생하면 복잡해진다. 클라이언트 요청 -> WAS -> 컨트롤러 (에러발생) -> WAS -> 컨트롤러 -> 클라이언트 응답 [SpringMVC] API 예외처리하기(1) - BasicErrorController 위 그림은 Spring에서 lordofkangs.tistory.com 지난 포스팅에서 API 호출에서 발생하는 에러를 처리하기 위해, ExceptionResolver를 직접 만들어 구현해보았다. Controller에서 에러가 발생하면 디스패처 서블릿으로 전파된다. 디스패처 서블릿은 에러가 WAS로 전파되지 않도록 에러를 핸들링 할 수 있는 ExceptionResolver를 탐색한다...

컨트롤러에서 에러가 발생하면 복잡해진다. 클라이언트 요청 -> WAS -> 컨트롤러 (에러발생) -> WAS -> 컨트롤러 -> 클라이언트 응답 [SpringMVC] API 예외처리하기(1) - BasicErrorController 위 그림은 Spring에서 에러가 발생했을 때 처리되는 과정이다. 에러가 발생했을 때 try-catch문으로 Exception을 잡지 않으면 에러는 WAS까지 전달된다. WAS는 에러의 종류를 확인하고 그에 따른 요청을 lordofkangs.tistory.com 그래서 지난 포스팅에서는 위 과정을 자동화 해주는 스프링부트의 BasicErrorController에 대해서 알아보았다. 그러나 API 요청은 다양하고 그에 따라 다양한 에러 응답이 필요하다. BasicErrorCon..

위 그림은 Spring에서 에러가 발생했을 때 처리되는 과정이다. 에러가 발생했을 때 try-catch문으로 Exception을 잡지 않으면 에러는 WAS까지 전달된다. WAS는 에러의 종류를 확인하고 그에 따른 요청을 서블릿에게 재요청한다. 서블릿은 요청과 매핑되는 컨트롤러를 호출하여 오류에 대한 응답을 클라이언트에게 전송한다. 이때 클라이언트가 HTML 응답을 원한다면 에러페이지를 렌더링하여 응답하면 된다. 그런데 클라이언트가 application/json과 같이, HTML이 아닌 다른 방식으로 에러를 응답하기를 바란다면 어떻게 해야 할까? 우선 오류가 발생했을 때, 오류 종류에 따른 WAS 설정을 해보자. WebServerFactoryCustomizer 구현체 @Component public cla..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net ◎ 문제풀이 처음에는 대부분 DFS로 풀었다가 시간초과를 마주한다. 한 경로가 위처럼 이동했다고 해보자. 경로가 지나간 노드는 모두 방문된 노드가 된다. 보통의 DFS 풀이처럼 한번 방문한 노드를 다시 방문하지 못하도록 조건을 건다면 DFS의 시간복잡도는 O(N+E)가 된다. ( N은 노드의 개수, E은 간선의 개수 ) N은 최대 2,500개이고 간선은 노드 하나당 4개를 갖는다고 가정하면 10,000개이다. 시간복잡도가 O(N+E)면 충분히 시간제한 2초안에 풀 수..