[TIL] 2월 19일
아침 학습 - 이코테 그래프 탐색 알고리즘 DFS/BFS
-
DFS : 깊이 우선탐색 (Depth-First Search)
- 그래프에서 깊은 부분을 우선적으로 탐색
-
DFS는 스택 자료구조 이용
-
동작과정
-
탐색 시작 노드를 스택에 삽입, 방문처리한다.
-
스택의 최상단 노드에 방문하지 않은 인접노드가 있으면 그 인접노드를 스택에 넣고 방문처리한다.
방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
-
2번 과정을 더이상 수행할 수 없을때까지 반복한다.
-
-
O(N)의 시간 소요
-
재귀 함수를 이용하면 간결하게 구현가능
-
-
DFS 예제
public class DFSExam {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
// DFS 함수 정의
public static void dfs(int x) {
// 현재 노드 방문처리
visited[x] = true;
System.out.print(x + " ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited[y]) dfs(y);
}
}
public static void main(String[] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
graph.get(2).add(1);
graph.get(2).add(7);
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
graph.get(4).add(3);
graph.get(4).add(5);
graph.get(5).add(3);
graph.get(5).add(4);
graph.get(6).add(7);
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
graph.get(8).add(1);
graph.get(8).add(7);
dfs(1);
}
}
</> 실행 결과
1 2 7 6 8 3 4 5-
각 노드가 방문된 정보를 표현하는 배열 visited
-
크기가 9인 이유?
→ 인덱스 0은 사용하지 않고, 1번 부터 8번까지의 노드가 있으니 하나 더 큰 크기로 9개 크기의 배열을 생성
-
-
graph의 0번 인덱스는 비운다.
- DFS 문제 출제시 노드 번호가 1번부터 시작되는 경우가 많다.
Value Object
어제 호눅스 수업과 아래의 두 블로그 참고
https://velog.io/@livenow/Java-VOValue-Object%EB%9E%80
VO 란?
- 객체의 값이 같으면 같은 객체로 보는 것
- 객체를 값처럼 쓸 수 있다.
- 객체의 인스턴스 변수가 생성자를 통해 설정된 이후에는 절대 변하지 않음을 보장
- value를 담는게 주 목적이다.
- ==로 비교할 수 있다. 값이 같으면 같은 객체라고 본다.
- 고유하게 갖고있는 unique한 값(식별할수 있는 값)이 없다.
The bad practice of using primitive types to represent an object in a domain is so common that has even a name : primitive obsession.
- 3가지 특징 : immutability, value equality and self validation
Immutability(불변성)
No setters allowed.
한번 파라미터 값을 주고 생성자를 통해 생성하면 바꿀 수 없다.
객체는 GC에 의해 사라지기 전까지 같은 값으로 유지되어야한다.
-
immutability 로 인한 장점
-
Hassle-free Sharing (번거로움 없는 공유)
코드의 다른부분에서 수정되지 않기때문에 참조로 Value Object를 공유할 수 있다.
버그를 피하기위해 작성되는 코드의 복잡성과 부하를 감소시킨다.
멀티 스레드 환경에서 이점이 된다.
-
Improved Semantics (향상된 의미)
무의미한 getter를 추가하지 마라
나중에 필요할거 같아서 메소드를 추가하는 것을 자제하라
초기 클래스는 생성자와 private 속성들로만 구성되어야한다.
-
-
Value Object를 다루는 방법
- 생성자나 static 메소드를 통해 인스턴스를 생성한다.
- 현재 객체에서 다른 객체 생성한다.
- 내부 데이터를 추출해 다른 유형으로 변환한다.
Value Equality(값 동등성)
나랑 친구가 다른 카드 덱에서 카드를 한장씩 뽑았다. 친구의 카드가 내 카드와 같은지 알아야 하는 상황이다.
친구의 카드, 내카드가 같은 숫자와 무늬라면 두장의 카드는 같은 속성을 가진 거라고 볼 수 있다.
이제 친구와 내가 카드를 교환해도 친구와 나의 카드는 동일하다.
두장의 카드가 Value Object 인 것이다.
Value Object는 값이 동일한 두개의 객체는 동일한 것이라고 본다. → 객체들의 내부 값이 같은지 확인하는 것을 통해서 동등성을 테스트할 수 있다.
Self Validation(자가 유효성 검사)
Value Object는 문맥에서 유효한 값만 허락한다.
유효하지 않은 값을 가진 객체는 생성할 수 없다.
생성자에 값을 넣을때 값의 유효성을 확인해야한다.
유효하지 않으면 예외가 발생시킨다.
모든 유효성 검사는 생성 시간에 이루어진다.
- 예시
final class Rand {
private int value;
public Rand(int value) {
if (value < 1 || value > 13 {
throw new InvalidRankValue(value);
}
this.value = value;
}
}미션4 코드리뷰 by 호눅스
PR 설명은 핵심만
distinguish()라는 메소드명이 다른 메소드에서 호출된걸 봤을때 무슨 역할을 하는지 잘 모르겠다. List를 반환하는 메소드이기 때문에 getPieceList()와 같은 이름이 더 좋을것이다.
private 메소드는 public메소드 뒤에 위치하는 것이 좋다.
관련 내용 학습
표준 자바 관례에 따른 클래스 안에서의 순서
- static public 상수
- static private 변수
- private instance 변수 (public 변수가 필요한 경우는 거의 없음)
- public method
- private method는 자신을 호출하는 public method 직후에 위치
- 테스트를 위해 private method나 변수를 protected로 공개해야 할 경우가 있다. 이런 경우 공개하지 않을 방법을 충분히 생각한 이후에 캡슐화를 푸는 것이 좋다.
블로그에 나와있는 SOLID 원칙과 예제코드도 더 살펴봐야겠다. 개구리책이랑 같이 봐야지
String과 StringBuilder의 문자결합
String empty = appendNewLine(getEmptyResult());
return appendNewLine(getBlackPieceResult()) +
appendNewLine(getBlackPawnResult()) +
empty + empty + empty + empty +
appendNewLine(getWhitePawnResult()) +
appendNewLine(getWhitePieceResult());호눅스가 StringBuilder 로 바꿔서 바이트 코드를 비교해보라고 하셨다.
비교해보니 위의 코드(String에서 + 연산자 사용)의 바이트 코드에 StringBuilder.append라고 쓰여있다. 바이트 코드를 잘 모르지만 내부적으로 StringBuilder를 사용하는건가 하고 찾아보니 Java 1.5부터는 +연산자를 사용해도 StringBuilder로 변환해서 처리한다고 한다.
: 참고한 블로그
intelliJ에서 byte 코드 확인하기
View → ShowByteCode
try-with-resources문
자바의 정석(437p)
try의 괄호()안에 객체를 생성하는 문장을 넣으면 이 객체는 try블럭을 벗어나는 순간 자동으로 close() 해준다.
대신 AutoCloseable이라는 인터페이스를 구현한 클래스여야 try-with-resources문을 사용 가능하다.
자바 API 문서를 보니 Scanner도 AutoCloseable 인터페이스를 구현한 것이다.
Chess 클래스에서 사용자 입력받는 부분에서 try-with-resources 구문을 사용하려고 했으나 try의 괄호 안에 Scanner 객체를 생성해줘서 catch에서 스캐너 참조변수에 접근하지 못해서 다시 입력받는것을 실패해서 그냥 close() 해주었다.
Scanner sc = new Scanner(System.in);
while (true) {
try {
String input = sc.nextLine();
if (input.equals("y")) {
startChess();
}
if (input.equals("n")) {
System.out.println("체스를 종료합니다.");
break;
}
if (!input.equals("y") && !input.equals("n")) {
throw new NoSuchElementException();
}
} catch (NoSuchElementException e) {
System.out.println("잘못된 값입니다. y 또는 n을 입력해주세요.");
sc = new Scanner(System.in);
}
}
sc.close()- 이렇게 catch문에서 스캐너 객체를 다시 생성해서 while문을 실행시키고 싶었다.
오늘 한일
- 아침에 이코테 책 DFS에 대해 학습했다.
- Value Object란 무엇인가? VO의 특징, 장점
- 메소드 이름지을때 더 고민해보자, String을 +연산자로 결합해도 내부적으로 StringBuilder로 변환해서 append를 수행한다, Scanner 사용시 꼭 close() 해주자, try-with-resources 사용 방법
- PR에 너무 자세한 설명보다는 핵심 내용만 적기, 구현할때 무조건 요구사항만 따라하기 보다는 왜 이렇게 코드를 짜는지 더 생각해보기
- 이번주에 git, VO 정의하기, 정적 팩토리 메소드 등 조원들 덕분에 많이 배우고 조원들의 의견을 들으면서 그냥 넘어갈 법 했던 것도 더 공부할수 있었다.
Todo
(내일)
- VO 우테코 사이트에 있는 내용 보기
- enum 수업 복습
- 참조변수와 함수호출 복습
- 사용자 정의 예외 만들기 학습
Author And Source
이 문제에 관하여([TIL] 2월 19일), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yeon/TIL-2월-19일저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
