[항해99 취업 리부트 코스 학습일지] 22일차

이번 주 목표 

📢 이번주 목표는 백준 골드2까지 승급하는 것이다. 현재 골드4이다.
     마이크로서비스 구축 가이드 책 완독하기(252/697)

오늘 스케줄

09:00~09:20 모닝 스크럼
09:30~10:30 완전탐색 강의 수강
10:30~12:00 데일리 과제 문제 풀이
12:00~13:00 점심 식사
13:00~16:30 데일리 과제 문제 풀이
16:30~18:00 병원 진료
18:40~19:10 기술매니저님과 팀 코드 리뷰
19:10~20:10 저녁 식사
20:10~20:40 산책
21:00~22:30 마이크서비스 구축 가이드 책 읽기
22:30~00:00 JPA 프로그래밍 책 읽기

오늘 목표

👉 데일리 과제 모두 풀기

👉 TIL 빠지지 않고 작성하기

👉 북 스터디 참여

👉 인프런 마이크로서비스 강의 수강하기

오늘 한 것

• TIL 빠지지 않고 작성하기
• 북 스터디 참여

오늘 못한 것

• 인프런 마이크로서비스 강의 수강하기
• 데일리 과제 모두 풀기

알게된 것

완전 탐색이란?

모든 경우의 수를 시도하는 방법
Exhaustive search, Brute force

• 상대적으로 구현이 간단하고, 해가 존재하면 항상 찾게 됨
• 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용.

완전 탐색 알고리즘

• 단순 Brute-Force
  • 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법.
  • 이 방법만을 사용하는 문제는 거의 나오지 않음.
• 비트마스트 (Bitmask)
  • 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하게 사용
  • ex) '원소가 n개인 집합의 모든 부분 집합'을 구한다면, 각 원소가 포함되는지 포함되지 않는지를 0, 1로 구분하여 배열에 저장해둘 수 있음
• 재귀함수
  • 비트마스크와 마찬가지로 각 원소가 두 가지 선택지를 가질 때 유용하게 사용.
  • 포함이 되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 등의 식
  • ex) 피보나치 수열
  • 시간 복잡도 O(N)
• 순열
  • 순열(permutation)은 서로 다른 N개를 일렬로 나열하는 방법(경우의 수)를 말함.
  • 순열의 경우의 수는 N!으로 완전 탐색을 이용하기 위해서는 N이 한자리 수는 되어야 함.
  • 순열에 원소를 하나씩 채워가는 방식.
  • 재귀함수 이용 or C++의 next_permutation() 함수 이용.
  • 시간복잡도 O(N!)
• 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)
  • 너비우선탐색(Breadth-First Search, BFS)는 하나의 요소를 방문하고 그 요소에 인접한 모든 요소를 우선 방문하는 방식
  • 깊이우선탐색(Depth-First Search, DFS)는 트리의 한 요소(노드)와 다음 수준(level)의 자식 노드를 따라가는 방향으로 탐색하는 방식
  • 길 찾기 등에 주로 쓰이는 알고리즘
    : 단순 길찾기에는 BFS/DFS만 써도 무방하지만,
    장애물이 존재하는 등 추가적 연산이 필요할 때 완전탐색 병용하기도 함.
  • ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현하고 A와 B 사이에 존재하는 경로 찾을 때
    - DFS : 모든 친구 관계 다 살펴야한다.
    - BFS : A와 가까운 관계부터 탐색한다.
    

    

• 너비 우선 탐색(BFS, Bread-First Search)
  • 재귀적으로 동작하지 않음
  • 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사
    (검사하지 않으면 무한루프)
  • BFS는 방문한 노드들을 차례로 저장하고 꺼낼 수 있는 큐 사용(FIFO)
  • 넓게 탐색
  • 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용.

// bfs, 큐 사용, 인접행렬, i 정점부터 시작
public static void bfs(int i) {
	Queue<Integer> q = new LinkedList<>();
	q.offer(i);
	visit[i] = true;
	while(!q.isEmpty()) {
		int temp = q.poll();
		for(int j=1; j<n+1; j++) {
			if(map[temp][j] == 1 && visit[j] == false) {
				q.offer(j);
				visit[j] = true;
			}
		}
	}
}

• 깊이 우선 탐색(DFS, Depth-First Search)
  • 재귀적으로 동작(재귀, 스택)
  • 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사
    (검사하지 않으면 무한루프)
  • 모든 노드 방문하고자 할 때 사용
  • BFS 보다 간단, BFS 비해서 검색 속도 느림
  • 모든 노드 방문하고자 할 때 사용.

// dfs, 재귀, 인접 행렬, i 정점부터 시작
public static void dfs(int i) {
	visit[i] = true;
	for(int j=1; j<n+1; j++) {
		if(map[i][j] == 1 && visit[j] == false) {
			dfs(j);
		}
	}
}

---

Tip

• 하나도 빠짐없이 모든 경우의 수를 확인하고 있는지만 확인하면 됨

---

문제 예시

프로그래머스 - 소수찾기

• 숫자 카드 7장으로 만들 수 있는 모든 숫자를 만들었는지
• 만든 모든 숫자가 소수인지

// 모든 숫자 조합 만들기 (dfs)
public void dfs(String numbers, String tmp, int depth) {
	if (tmp.length() == depth) {
		int number = Integer.parseInt(tmp);
        if(!arrNum.contains(number)) arrNum.add(number);
        return;
	}
    else {
		for(int i = 0; i < numbers.length(); i++) {
			if(!visit[i]) {
				visit[i] = true;
                tmp += numbers.charAt(i);
                dfs(numbers, tmp, depth);
                isit[i] = false;
                tmp = tmp.substring(0, tmp.length() - 1);
            }
        }
    }
}
    
// 소수찾기
boolean isPrime(int number) {
	if(number == 0 || number ==1) return false;
	for(int i = 2; i <= Math.sqrt(number); i++){
		if(number % i == 0) return false;
	}
    return true;
}

 

출처: https://velog.io/@hyehyes

🤔오늘의 반성

- 데일리 과제를 처음으로 모두 다 못 풀었다 문제가 어렵다ㅠ
- 마이크로서비스 강의 못 들은 점

 

👍 오늘의 칭찬

1. 깃헙 1일 1커밋 달성
2. TIL을 빠지지 않고 작성했다.
3. 북 스터디 참여
4. 병원 다녀옴

❗ 항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.
https://hanghae99.spartacodingclub.kr/reboot