L.O.K

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net ◎ 문제풀이 A지점에서 B지점으로 최소비용으로 이동하는 문제는 BFS로 풀어야 한다. 그러나 나는 최근에 DP 문제를 하나 풀어서 그런지, 이 문제를 보고 DP 발상을 했다. N에서 K까지 가는 경우를 모든 고려하는 문제이다. 이동하는 방법은 3가지이다. 1) x2 2) +1 3) -1 N이 5이고 K가 17이라고 가정해보자. 위 그림 같이, 경우의 수가 기하급수적으로 증가하니 DP로 풀기는 어려운 문제이다. 1) x2 2) ..

[SpringMVC] 검증(Validation)(3) - BindingResult ( rejectValue 메소드 ) [SpringMVC] 요청데이터 검증(Validation)하기(2) - BindingResult [SpringMVC] 요청데이터 검증(Validation)하기(1) 클라이언트로부터 요청(Request)이 들어오면, 요청 데이터는 가장 먼저 Controller에 도착한다. 그러 lordofkangs.tistory.com 지난 포스팅에서 BindingResult의 rejectValue 메소드로 코드를 단순화 해보았다. Controller @PostMapping("/add") public String addItem(@ModelAttribute Item item, BindingResult bin..

[SpringMVC] 요청데이터 검증(Validation)하기(2) - BindingResult [SpringMVC] 요청데이터 검증(Validation)하기(1) 클라이언트로부터 요청(Request)이 들어오면, 요청 데이터는 가장 먼저 Controller에 도착한다. 그러므로 Controller에서 적합한 데이터인지 검사해야 한다. 적 lordofkangs.tistory.com 지난 포스팅에서 BindingResult를 다루어 보았다. BindingResult는 오류 메시지를 담는 그릇으로, FieldError와 ObjectError에 담긴 에러 메시지를 저장한다. 그러나 개발자가 FieldError와 ObjectError를 직접 생성하면 코드가 복잡해지고 길어진다. 그래서 BindingResult는..

[SpringMVC] 요청데이터 검증(Validation)하기(1) 클라이언트로부터 요청(Request)이 들어오면, 요청 데이터는 가장 먼저 Controller에 도착한다. 그러므로 Controller에서 적합한 데이터인지 검사해야 한다. 적합하지 않은 데이터가 서버 내부로직으로 lordofkangs.tistory.com 지난 포스팅에서 HashMap으로 요청데이터 검증을 구현해보았다. 이번 포스팅에서는 Spring에서 제공하는 BindingResult 객체를 이용하여 요청데이터 검증을 구현해 보겠다. BindingResult 객체는 오류 메시지를 담는 그릇이라고 보면 된다. HashMap 자료구조에 오류 메시지를 담으면 Controller 외부에서 발생하는 오류를 핸들링하지 못한다. BindingRe..

2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net ◎ 문제풀이 문제가 복잡해 보이나 이해를 하면 어려운 문제는 아니다. 복잡한 개념이 들어가 있지는 않으나 구현력이 필요한 문제였다. 크게 두 가지 과정이 있다. 1) 로마 숫자를 십진법 숫자로 만들기 2) 십진법 숫자를 로마숫자로 만들기 - 로마 숫자를 십진법 숫자로 만들기 1) 로마문자와 십집법 숫자가 매핑된 Map 자료구조를 만든다. 2) 로마숫자를 좌측부터 한 문자씩 읽어온다. 3) 현재 문자는 이전 문자보다 작아야 한다. 4) 현재 문자가 이전 문자보다 크다면 XL, XC , CD ,CM ... 이런 문자..

https://www.acmicpc.net/problem/14675 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net ◎ 문제풀이 뭔가 맥이 빠지는 문제였다. 단절점과 단절선을 없애면 트리가 그래프가 두 개 나와야 한다. 단절선은 무엇을 없애든 그래프가 2개 나온다. 그러므로 무조건 yes이다. 단절점은 단절점의 자식노드가 2개 이상이면 yes이다. 그러므로 트리를 인접리스트로 구현하여 리스트의 크기가 2이상이면 yes를 출력한다. ◎ 코드 package org.example.tree;..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net ◎ 문제풀이 특정 노드를 삭제하면 자식 노드들도 삭제가 될 때, 리프노드의 개수를 구하는 문제이다. 풀이는 3단계로 이루어 진다. Step1) 트리를 그래프의 인접리스트 구조로 구현 각 노드의 자식노드를 List에 저장한다. 그래프의 인접리스트 방식으로 트리를 구현하는 것이다. Step2) DFS 탐색으로 노드 삭제 특정 노드를 삭제하면 자식노드와 자식의 자식노드도 삭제해야 한다. DFS탐색으로 자식의 자식까지 삭제하고 삭제 여부를 테이블 자료구조에 저장한..

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net ◎ 문제풀이 전위순회 결과를 가지고 이진트리를 만든 후 후위순회를 하는 문제이다. 전위순회는 ROOT -> LEFT -> RIGHT 순으로 탐색한다. 그러므로 가장 위에 있는 값이 ROOT이고 다음 값은 LEFT이다. 그리고 그 다음 값은 LEFT의 LEFT이다. LEFT의 LEFT가 없다면 ROOT의 RIGHT이다. 이 구조는 객체참조구조를 이용하면 쉽게 구할 수 있다. ◎ 코드 package org.example.tree; import java...

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ◎ 문제풀이 위상정렬의 교과서 같은 문제이다. 문제풀이의 순서를 정해야 한다. 그러나 순서에는 우선순위가 있다. 즉, 각 문제는 위상이 서로 다르다. 문제A는 문제B 앞에 와야하고 문제C는 문제D 앞에 와야한다. 이렇듯, 정렬되는 순서에 어떠한 위상이 존재할 때, 위상정렬 알고리즘을 사용한다. [Algorithm] 위상정렬 (Topology Sort)이란? 위상정렬은 방향그래프를 한 정렬이다. 위 그래프는 작업 간 의존관계를 표현한..

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 www.acmicpc.net ◎문제 풀이 문자열 s가 주어질 때, 주어진 여러 개의 문자열 조합으로 s를 만들 수 있는지를 묻는 문제이다. 조합을 만드는 문제는 재귀호출로 풀면된다. 적절한 가지치기 조건을 두어 DFS 탐색을 하면 문제를 풀 수 있다. ◎코드 import java.util.Scanner; //BOJ165000 문자열 판별 ( 백트래킹 ) public class Main { public s..