TIL_230202
오늘 한 일 [DONE]
- 싱글톤 패턴부터 프록시 패턴까지 복습! - 몰라도 일단 따라 읽을 것!
- 프로젝트 PR 완료, 앱 중복 클릭 현상 고민.
- 추상 클래스와 인터페이스 개념 확인. - 코드 읽을 때 조금이라도 막히면 기초로 다시 돌아가는 습관! 중요! 그럼 다시 잘 읽힌다.
- 알고리즘 순열 문제 풀면서 복습 (Code)
- 알고리즘 DFS, BFS 개념 정리 및 실제 문제 풀이 (Code)
📝오늘 배운 내용 간단 요약
1️⃣ 추상 클래스와 인터페이스 (객체지향)
추상 클래스 (abstract class)
상속 전용 클래스라고 말할 수 있으며,
자식 클래스에서 "반드시 부모 메서드를 재정의"해서 사용하는 상황에 쓰인다.
클래스 앞에 abstract 키워드가 붙는 클래스를 추상 클래스라고 하는데
이는 클래스 내부에 구현부가 없는 abstract 메서드가 있어서 인스턴스화할 수 없음을 표시해주기 위해 abstract 키워드를 클래스 앞에 붙이게 되는 것이다.
인터페이스 (interface)
인터페이스는 interface 키워드로 선언하며,
모든 필드는 public static final이며, 이를 생략할 수도 있고,
모든 메서드는 public abstract이며, 이를 생략할 수 있다. 그래서 선언부만 작성되는 메서드 형태를 띈다.
인터페이스를 사용하면 구현을 강제로 할 수 있고 (abstract 메서드만 존재하므로)
인터페이스를 통한 간접적 클래스 사용으로 모듈 교체를 쉽게 하며,
서로 상속 관계가 없는 클래스에게 관계 부여를 해 다형성을 확장할 수 있다.
2️⃣ DFS와 BFS (Algorithm)
DFS (Depth First Search)
시작 정점의 한 방향으로 갈 수 있는 곳까지 깊이 탐색하다 더 이상 갈 곳이 없게 되면,
가장 마지막에 만났던 갈림길로 되돌아와 가지 않았던 다른 방향으로 탐색을 계속 반복하는 순회 방법.
이 갈림길로 "되돌아가는" 과정이 있기 때문에 후입선출 구조의 Stack을 사용한다.
Stack을 사용하는 방식이므로,
DFS는 재귀(시스템 Stack) 또는 Stack 자료구조를 활용한 반복문으로 구현할 수 있다.
DFS는 방문 체크를 Stack에서 pop되는 시점에 한다.
BFS (Breadth First Search)
시작 정점과 인접한(연결된) 정점들을 모두 방문한 후에,
방문했던 정점을 시작점으로 하여 다시 인접한 정점을 차례로 순회하는 방법.
인접한 부분을 발견한 "차례대로 탐색"하므로 선입선출 구조의 Queue를 사용한다.
Queue에 저장된 노드가 없어질 때까지 탐색을 이어간다.
BFS는 방문 체크를 Queue에 저장하는 시점에 한다.