Graph
아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현한 자료구조
- 정점(Vertex)의 집합과 이들을 연결하는 간선(Edge)로 구성되어 있다.
- 선형 자료구조나 트리로 표현하기 어려운
M:N관계를 표현하기 위해 주로
사용된다.
종류
무향 그래프(Undirected Graph)
유향 그래프 (Directed Graph)
가중치 그래프(Weighted Graph)
순환 그래프
완전 그래프
Graph의 표현 – 인접 행렬
- 정점의 갯수를 V라 할 때, V * V 크기의 2차원 배열 활용
- 행 번호와 열 번호를 각각 그래프의 정점에 대응
- 두 정점이 인접하면 1, 그렇지 않다면 0
AdjacentMatrix
public class AdjacentMatrix {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer: 입력받은 문자열을 ' ' (또는 지정된 delimiter) 를 기준으로 나누어서
// 한 단어씩 반환해주는 도구
StringTokenizer graphTokenizer // 8 10
= new StringTokenizer(reader.readLine());
// StringTokenizer.nextToken(): 다음 단어를 가져오기
int maxNodes = Integer.parseInt(graphTokenizer.nextToken()); // 8
int edges = Integer.parseInt(graphTokenizer.nextToken()); // 10
// 인접 행렬: 2차원 배열
// 만약 노드가 1부터 N + 1 까지라면
// 계산할때 매번 -1을 해주거나
// 인접 행렬을 한칸 더 늘리거나
int[][] adjMatrix = new int[maxNodes][maxNodes]; // 0 ~ 7 까지 표현 가능한 인접 행렬
// 간선의 갯수만큼 반복해서 입력을 받는다.
for (int i = 0; i < edges; i++) {
// 다음줄을 단어 단위로 나눠주는 Tokenizer
StringTokenizer edgeTokenizer
= new StringTokenizer(reader.readLine());
// 입력 줄의 첫 숫자
int startNode = Integer.parseInt(edgeTokenizer.nextToken());
// 입력 줄의 두번째 숫자
int endNode = Integer.parseInt(edgeTokenizer.nextToken());
// 유향 그래프의 경우 아래줄 만
adjMatrix[startNode][endNode] = 1;
// 무향 그래프의 경우 아래줄도 함께
adjMatrix[endNode][startNode] = 1;
}
for (int[] row: adjMatrix) {
System.out.println(Arrays.toString(row));
}
}
public static void main(String[] args) throws IOException {
new AdjacentMatrix().solution();
}
}// 입력
8 10
0 1
0 2
0 3
1 3
1 4
2 5
3 4
4 7
5 6
6 7// 출력
[0, 1, 1, 1, 0, 0, 0, 0]
[1, 0, 0, 1, 1, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 0, 0]
[1, 1, 0, 0, 1, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1, 0, 1]
[0, 0, 0, 0, 1, 0, 1, 0]Graph의 표현 – 인접 리스트
각 정점마다 다른 정점으로 나가는 간선의 정보를 저장(일반적 그래프)
AdjacentList
public class AdjacentList {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer: 입력받은 문자열을 ' ' (또는 지정된 delimiter) 를 기준으로 나누어서
// 한 단어씩 반환해주는 도구
StringTokenizer graphTokenizer // 8 10
= new StringTokenizer(reader.readLine());
// StringTokenizer.nextToken(): 다음 단어를 가져오기
int maxNodes = Integer.parseInt(graphTokenizer.nextToken()); // 8
int edges = Integer.parseInt(graphTokenizer.nextToken()); // 10
// 안쪽의 List<Integer>가 maxNodes의 길이를 반드시 가지지는 않을 것이다.
List<List<Integer>> adjList = new ArrayList<>();
// 먼저 리스트의 내용물을 초기화 해준다.
for (int i = 0; i < maxNodes; i++) {
adjList.add(new ArrayList<>());
}
// 간선의 갯수만큼 반복해서 입력을 받는다.
for (int i = 0; i < edges; i++) {
// 다음줄을 단어 단위로 나눠주는 Tokenizer
StringTokenizer edgeTokenizer
= new StringTokenizer(reader.readLine());
// 입력 줄의 첫 숫자
int startNode = Integer.parseInt(edgeTokenizer.nextToken());
// 입력 줄의 두번째 숫자
int endNode = Integer.parseInt(edgeTokenizer.nextToken());
// adjList 의 startNode 번째 리스트에 endNode 를 첨부한다.
// 유향 그래프일 경우 아래 줄 만
adjList.get(startNode).add(endNode);
// 무향 그래프일 경우 아래 줄도 함께
adjList.get(endNode).add(startNode);
}
// 선택사항: DFS나 BFS를 할때 이왕이면 방문순서를
// '작은 숫자부터' 와 같은 조건을 붙이고 싶다면
// 정렬해야 한다.
for (List<Integer> adjRow: adjList) {
// 정렬해주는 Collections.sort 메소드
Collections.sort(adjRow);
}
for (List<Integer> adjRow: adjList) {
System.out.println(adjRow);
}
}
public static void main(String[] args) throws IOException {
new AdjacentList().solution();
}
}// 출력
[1, 2, 3]
[0, 3, 4]
[0, 5]
[0, 1, 4]
[1, 3, 7]
[2, 6]
[5, 7]
[4, 6]DFS(깊이 우선 탐색)
public class RecursiveDFS {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
// StringTokenizer: 입력받은 문자열을 ' ' (또는 지정된 delimiter) 를 기준으로 나누어서
// 한 단어씩 반환해주는 도구
StringTokenizer graphTokenizer = new StringTokenizer(reader.readLine());
// StringTokenizer.nextToken(): 다음 단어를 가져오기
int maxNodes = Integer.parseInt(graphTokenizer.nextToken()); // 8
int edges = Integer.parseInt(graphTokenizer.nextToken()); // 10
// 인접 행렬: 2차원 배열
// 만약 노드가 1부터 N + 1 까지라면
// 계산할때 매번 -1을 해주거나
// 인접 행렬을 한칸 더 늘리거나
int[][] adjMatrix = new int[maxNodes][maxNodes]; // 0 ~ 7 까지 표현 가능한 인접 행렬
// 간선의 갯수만큼 반복해서 입력을 받는다.
for (int i = 0; i < edges; i++) {
// 다음줄을 단어 단위로 나눠주는 Tokenizer
StringTokenizer edgeTokenizer = new StringTokenizer(reader.readLine());
// 입력 줄의 첫 숫자
int startNode = Integer.parseInt(edgeTokenizer.nextToken());
// 입력 줄의 두번째 숫자
int endNode = Integer.parseInt(edgeTokenizer.nextToken());
// 유향 그래프의 경우 아래줄 만
adjMatrix[startNode][endNode] = 1;
// 무향 그래프의 경우 아래줄도 함께
adjMatrix[endNode][startNode] = 1;
}
boolean[] visited = new boolean[maxNodes];
List<Integer> visitedOrder = new ArrayList<>();
recursive(0, maxNodes, adjMatrix, visited, visitedOrder);
System.out.println(visitedOrder);
}
// 목적: DFS를 했을 떄 정점 방문 순서 기록
public void recursive(
// 다음 (이번 호출)에서 방문할 곳
int next,
// 원활한 순회를 위한 maxNodes
int maxNodes,
// 인접 정점 정보 (그래프 정보)
int[][] adjMatrix,
// 여태까지 방문한 정점 정보
boolean[] visited,
// 요부분은 구하고자 하는 목적에 따라 다릅니다.
// 방문 순서 기록을 위한 리스트
List<Integer> visitOrder
) {
visited[next] = true;
visitOrder.add(next);
// 반복문에서 재귀호출 한다.
for (int i = 0; i < maxNodes; i++) {
// 연결이 되어있으며, 방문한적 없을 때
if (adjMatrix[next][i] == 1 && !visited[i])
recursive(i, maxNodes, adjMatrix, visited, visitOrder);
}
}
public static void main(String[] args) throws IOException {
new RecursiveDFS().solution();
}
}// 출력
[0, 1, 3, 4, 7, 6, 5, 2]BFS(너비 우선 탐색)
public class ListBreadthFirstSearch {
public void solution() throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer graphTokenizer = new StringTokenizer(reader.readLine());
int maxNodes = Integer.parseInt(graphTokenizer.nextToken());
int edges = Integer.parseInt(graphTokenizer.nextToken());
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < maxNodes; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < edges; i++) {
StringTokenizer edgeTokenizer = new StringTokenizer(reader.readLine());
int startNode = Integer.parseInt(edgeTokenizer.nextToken());
int endNode = Integer.parseInt(edgeTokenizer.nextToken());
adjList.get(startNode).add(endNode);
adjList.get(endNode).add(startNode);
}
for (List<Integer> adjRow: adjList) {
Collections.sort(adjRow);
}
// BFS
// 다음 방문 대상 기록용 Queue
Queue<Integer> toVisit = new LinkedList<>();
// 방문 순서 기록용 List
List<Integer> visitedOrder = new ArrayList<>();
// 방문 기록용 boolean[]
boolean[] visited = new boolean[maxNodes];
int next = 0;
toVisit.offer(next);
// 큐가 비어있지 않은 동안 반복
while (!toVisit.isEmpty()) {
// 다음 방문 정점 회수
next = toVisit.poll();
// 이미 방문 했다면 다음 반복으로
if (visited[next]) continue;
// 방문했다 표시
visited[next] = true;
// 방문한 순서 기록
visitedOrder.add(next);
// 다음 방문 대상을 검색한다.
// adjList.get[next]에 담겨있는 미방문 요소들을 차례대로 다 넣는다.
List<Integer> canVisitList = adjList.get(next);
for (Integer canVisit: canVisitList) {
if (!visited[canVisit])
toVisit.offer(canVisit);
}
}
System.out.println(visitedOrder);
}
public static void main(String[] args) throws IOException {
new ListBreadthFirstSearch().solution();
}
}// 출력
[0, 1, 2, 3, 4, 5, 7, 6]Validation
유효성 검사란 개발자가 유도한 대로 사용자는 데이터를 항상 입력하지 않을 가능성이 있으므로, 원하는 규칙과 조건을 만족하는지를 확인(검사)하는 것을 의미한다.
- 잘못된 데이터로 인한 문제를 방지하고 데이터의 신뢰성과 일관성을 유지하기 위함
Java Vaildation Framework
Jakarta Bean Validation
- 유효성 검증을 위한 기술 명세
- 어떤 항목이 어떠한 규칙을 지켜야 하는지 표시하는 기준
https://beanvalidation.org/2.0/spec/#builtinconstraints
Hibernate Validation
- Jakarta Bean Validation 을 토대로 실제로 검증해주는 프레임워크
프로젝트 생성
UserController
@Slf4j
@RestController
public class UserController {
@PostMapping("/users")
// Map을 열심히 사용할 예정입니다.
public ResponseEntity<Map<String, String>> addUser(
// @Valid: UserDto가 우리가 정의한 요구사항을 지키고 있는지 유효성 검사
@Valid @RequestBody UserDto dto
) {
log.info(dto.toString());
Map<String, String> responseBody = new HashMap<>();
responseBody.put("message", "success!");
return ResponseEntity.ok(responseBody);
}
@ExceptionHandler(MethodArgumentNotValidException.class)
@ResponseStatus(HttpStatus.BAD_REQUEST)
public Map<String, String> handleValidationException(
MethodArgumentNotValidException exception
) {
Map<String, String> errors = new HashMap<>();
for (FieldError error: exception.getBindingResult().getFieldErrors()) {
errors.put(error.getField(), error.getDefaultMessage());
}
return errors;
}
}UserDto
@Data
public class UserDto {
private Long id;
@NotBlank // 비어있지 않다
@Size(min = 8, message = "최소 8글자이어야 합니다. (최댓값도 있는데 그거 다 채워 넣으시진 못할거라 생각해요)")
@Blacklist(blacklist = {"banana.cat", "apple.cat"})
private String username;
@Email // 형식이 이메일이어야
@EmailWhitelist // 이메일이 지정된 도메인(gmail.com 등) 이도록 검증하는 어노테이션 만들기
private String email;
@NotNull
@Phone010
private String phone;
@NotNull
@Min(value = 14, message = "14세 미만은 부모님의 동의가 필요합니다.") // 최솟값
private Integer age;
@Future(message = "미래의 시간까지 유효해야 합니다.") // 미래의 시간만
private LocalDate validUntil;
@NotNull // notNullString이 Null이 아닌지만 검증
private String notNullString;
@NotEmpty // notEmptyString이 길이가 0이 아닌지만 검증
private String notEmptyString;
@NotBlank // notBlackString이 공백 문자로만 이루어지지 않았는지 검증
private String notBlankString;
}Test
성공 시
실패 시
@ExceptionHandler test
constraints, annotations package 생성
EmailWhitelistValidator
public class EmailWhitelistValidator
// 사용자 지정 유효성 검사를 위해 구현해야 하는 인터페이스
implements ConstraintValidator<EmailWhitelist, String> {
private final Set<String> whiteList;
public EmailWhitelistValidator() {
this.whiteList = new HashSet<>();
this.whiteList.add("gmail.com");
this.whiteList.add("naver.com");
}
@Override
public boolean isValid(String value, ConstraintValidatorContext context) {
// 유효한 값일 때 true를 반환
// 유효하지 않은 값일 때 false를 반환
String[] split = value.split("@");
String domain = split[split.length - 1];
// Set whileList에 domain이 추가되어 있는지
return whiteList.contains(domain);
}
}EmailWhitelist
@Target(ElementType.FIELD) // 어노테이션을 어디에 적용할 것인지 (선택)
@Retention(RetentionPolicy.RUNTIME) // 어노테이션이 언제까지 유지될 것인지
@Constraint(validatedBy = EmailWhitelistValidator.class)
public @interface EmailWhitelist {
// Annotation Element
String message() default "email not in whilelist";
Class<?>[] groups() default {};
Class<? extends Payload>[] payload() default {};
}Phone010Validator
public class Phone010Validator
implements ConstraintValidator<Phone010, String> {
@Override
public boolean isValid(String value, ConstraintValidatorContext context) {
boolean withDash = value.startsWith("010-");
boolean withPar = value.startsWith("(010)");
return withDash || withPar;
}
}Phone010
@Target(ElementType.FIELD)
@Retention(RetentionPolicy.RUNTIME)
@Constraint(validatedBy = Phone010Validator.class)
public @interface Phone010 {
// Annotation Element
String message() default "010으로 시작하지 않음";
Class<?>[] groups() default {};
Class<? extends Payload>[] payload() default {};
}whitelist, phone010 test
BlacklistValidator
public class BlacklistValidator implements ConstraintValidator<Blacklist, String> {
private Set<String> blacklist;
@Override
public void initialize(Blacklist constraintAnnotation) {
blacklist = new HashSet<>();
for (String target: constraintAnnotation.blacklist()) {
blacklist.add(target);
}
}
@Override
public boolean isValid(String value, ConstraintValidatorContext context) {
// this.blacklist안에 value가 있으면 실패
return !this.blacklist.contains(value);
}
}Blacklist
@Target(ElementType.FIELD)
@Retention(RetentionPolicy.RUNTIME)
@Constraint(validatedBy = BlacklistValidator.class)
public @interface Blacklist {
String message() default "username in blacklist";
Class<?>[] groups() default {};
Class<? extends Payload>[] payload() default {};
// 추가 Element를 작성
String[] blacklist() default {};
}Blacklist test
인사이트 타임
행렬의 덧셈
https://school.programmers.co.kr/learn/courses/30/lessons/12950
class Solution {
public int[][] solution(int[][] arr1, int[][] arr2) {
int[][] answer = new int[arr1.length][arr1[0].length];
for (int i = 0; i < arr1.length; i++) {
for (int j = 0; j < arr1[0].length; j++) {
answer[i][j] = arr1[i][j] + arr2[i][j];
}
}
return answer;
}
}배열 크기 지정을 못 해서 못 풀다가 태환님의 해설을 듣고 다시 풀었다.
2차원 배열의 특징을 잘 알아야만 풀 수 있었다.
수박수박수박수박수박수?
https://school.programmers.co.kr/learn/courses/30/lessons/12922
class Solution {
public String solution(int n) {
String answer = "";
String su = "수";
String bak = "박";
for (int i = 0; i < n; i++) {
if (i % 2 == 0) answer += su;
else answer += bak;
}
return answer;
}
}review
6월의 마지막 주가 장마와 함께 시작되었다. 어제 더워서 잠을 잘 못자서 그런지 하루종일 비몽사몽인 상태로 수업을 들었다. 알고리즘은 여전히 어렵고 스프링은 유효성 검사에 대해 배웠는데 실습은 나름 할만했다.
매일 TIL 포스팅 하는 것도 점점 지쳐간다. 배운게 많아지고 난이도는 상승하고 현재 나의 컨디션의 반비례하고 있는 중이다. 그래도 복습 차원에서 쓰고 자다보면 머리엔 얼마 들어오지 않아도 하루를 잘 마친 느낌이라 계속 써야겠다. 일단 오늘은 여기까지.
반갑습니다람지