728x90
99클럽 5기 | Java | Middler
🗝️ 오늘의 학습 키워드 : 이분 그래프 DFS 브루트포스 알고리즘 Map 문자열
⌛ 회고
이분 그래프가 뭔지 몰라서 한참 고민을 하였다.
권장 시간 초과하면 블로그 검색 해 보기로 했었는데
오늘도 시간을 초과하여 고민하고 말았다.
제출 시간을 넘어서 오늘 아침에야 그냥 다른 블로그 보고 해결해야지라는 마음으로 문제를 풀다가 DFS 풀이가 머릿속에 번뜩이며 스쳐지나갔다.
이번에는 결국 성공!
문제를 혼자 힘으로 해결한 것은 좋았지만 이렇게 하면 나중에 취직해서 코딩테스트 문제를 하루종일 잡고 있을 수도 없는 노릇이고...
시험 친다고 생각하고 제한 시간이 넘으면 풀이를 찾아보고 TIL 작성으로 바로 넘어가야겠다고 다짐하였다.
TIL 작성은 제출 기한 안에 못해서 미들러 문제 풀이를 제출하였는데 그래도 괜찮겠지?😜
설을 맞아 오전 버스로 부모님댁에 내려왔는데 내려오는 길에 멀미와 싸우며 휴대폰으로 비기너 문제도 Clear!😁
나름 자투리 시간을 잘 활용한 기분이 드는데 나중에 돌아보면 이것도 다 추억이 될 것 같다.❓ 오늘 만난 문제
- 🥉 비기너 : 전주 듣고 노래 맞히기
- 🥈 미들러 : 이분 그래프
- 🥇 챌린저 : 비슷한 단어
💦 나의 시도 & 해결 방법👍
- 🥉 비기너 : [백준 | Java] 31562번 전주 듣고 노래 맞히기
- 🥈 미들러 : [백준 | Java] 1707번 이분 그래프
- 🥇 챌린저 :
❗ 무엇을 새롭게 알았는지
이분 그래프(Bipartite Graph)
인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프
- 그래프의 모든 정점이 두 그룹으로 나누어짐
- 서로 다른 그룹의 정점과만 간선으로 연결
- 같은 그룹에 속한 정점끼리는 간선으로 연결되지 않음.
특징
- 탐색 방법 :
BFS,DFS - BFS 사용 시, 같은 레벨의 정점끼리는 같은 색
- 연결 성분의 개수(Connected Component)*를 구하는 방법과 유사
- 시간 복잡도 : O(V + E) (V: 정점의 수, E 간선의 수)
(그래프 탐색 알고리즘과 동일)- 모든 정점을 방문하며 간선을 검사
이분 그래프인지 확인하는 방법
BFS,DFS로 탐색하며 정점을 방문할 때마다 두 가지 색 중 하나를 칠함.- 다음 정점을 방문하면서 자신과 인접한 정점은 자신과 다른 색으로 칠함.
- 탐색을 진행할 때, 자신과 인접한 정점의 색이 자신과 동일하면 이분 그래프가 아니다.
BFS의 경우, 정점을 방문하다가 만약 같은 레벨의 정점을 다른 색으로 칠해야 한다면 무조건 이분 그래프가 아님.
- 모든 정점을 다 방문했는데 위와 같은 경우가 없다면 이분 그래프이다.
브루트 포스 알고리즘(Brute Force Algorithm)
Brute: 무식한
Force: 힘
Brute Force Algorithm : 완전 탐색 알고리즘
가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만들 가져온다.
- 장점 : 예외 없이 100%의 확률로 정답만을 출력
- 선형 구조 탐색 방법
- 순차 탐색
- 비선형 구조를 전체적으로 탐색하는 방법
- 깊이 우선 탐색(DFS; Depth First Search)
- 너비 우선 탐색(BFS; Breadth First Search)
📆 내일 학습할 것은 무엇인지
⏹️ 코딩테스트 문제 풀이
⏹️ TIL 작성
728x90
