[묘공단] 코딩 테스트 합격자 되기 5주차

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다.

 

집합

 

개념

• 순서와 중복이 없는 원소들을 갖는 자료구조
• 상호 배타적 집합(교집합이 없는 집합 관계)

상호 배타적 집합 특성을 활용하는 분야

• 이미지 분할 : 서로 다른 부분으로 나누는 데 사용
• 도로 네트워크 구성: 각 도로가 교차하지 않도록 설계-> 교차로 혼잡을 줄임
• 최소 신장 트리 알고리즘 구현 -> 간선을 추가할 때마다 사이클을 형성하는지 여부
• 게임 개발: 캐릭터 동작을 자연스럽게 구현 ex) 두 캐릭터가 겹치지 않도록 함
• 클러스터링 작업 -> 각 작업이 서로 겹치지 않도록 구성 할 수 있다 

 

연산

 

유니온 - 파인드 알고리즘

 

• 집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색이다
• 합치기 -> 유니온 union
• 탐색 -> 파인드 find
• 병합과 탐색

파인드

• 특정 노드의 루트 노드가 무엇인지 탐색하는 방법
• 특정 노드가 같은 집합에 있는지 확인
  1. 현재 노드의 부모 노드를 찾는다.
  2. 노드가 루트이면 종료
  3. 계속해서 올라가면서 부모 노드가 루트인지 확인
• 트리가 깊어 질 수록 연산 비용 문제 → 경로 압축으로 해결

유니온

• 합치는 방법
  1. 두 집합에서 찾기 연산을 통해 루트 노드를 찾는다
  2. 찾은 두 루트 노드의 값을 비교
  3. 루트 노드를 하나로 합친다 -> 두 집합의 루트 노드를 같게 하는 것이다 (이때 루트 노드는 두 집합 중 어떤 루트 노드로 해도 상관 없음)
• 트리가 깊어 질 수록 합치기 연산 비용 문제 → 랭크로 해결
  • 랭크란 ? : 현재 노드를 기준으로 가장 깊은 노드까지 경로의 길이
  • 노드 1 을 기준으로 노드 4가 있는 만큼 떨어진 길이 = 2
• 랭크 기반으로 합치기 연산
  1. 두 노드의 루트 노드를 구함
  2. 루트 노드의 랭크를 비교
     1. 랭크 값이 다르면 -> 랭크 값이 큰 루트 노드를 기준으로 삼음 즉, 랭크가 더 큰 루트 노드를 랭크가 작은 루트 노드의 부모 노드로 바꿈
     2. 랭크 값이 같으면 -> 루트 노드를 아무거나 선택해서 바꾸고 최종 루트 노드의 랭크에 1을 더함

---

그래프 탐색

 

깊이 우선 탐색 Depth-first search (DFS)

• 가장 깊은 노드까지 방문한 후에 더이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음, 해당 노드에서 방문할 노드가 있는지 확인한다.
• 방법으로는 스택, 재귀를 활용해서 구현 할 수 있다

진행

1. 스택이 비어있는지 확인 -> 비었다는건 방문할 수 있는 모든 노드를 방문했음을 의미한다 탐색을 종료함
2. 스택에서 노들르 pop 한다
3. pop 한 노드의 방문 여부를 확인 -> 방문하지 않았다면 노드를 방문 처리함
4. 방문한 노드와 인접한 모든 노드를 확인 -> 아직 방문하지 않은 노드를 스택에 push 함

핵심

가장 깊은 노드까지 방문한 후에 더 이상 방문할 노드가 없으면 최근 방문한 노드로 돌아온 다음 해당 노드에서 노드가 있는지 확인한다

 

 

너비 우선 탐색 Breadth-first search (BFS)

• 시작 노드부터 인접한 노드를 모두 방문한 후 그다음 단계의 인접 노드를 방문(먼저 발견한 노드)
• 방법으로는 큐를 이용해서 구현 할 수 있다

진행

1. 시작 노드를 큐에 add 하고 방문 처리한다
2. poll한후에 인접한 노드를 확인한다 -> 아직 방문하지 않았다면 방문 처리하고 큐에 add 한다
3. 이런식으로 큐가 비어있을때까지 반복하면 된다

 

 

깊이 우선 탐색과 너비 우선 탐색 차이

 

• 깊이 우선 탐색 : 깊게 탐색 후 되돌아오는 특성
• 너비 우선 탐색 : 가중치가 없는 그래프에서 최단 경로를 보장함

 

 

 

출처

 

https://goldenrabbit.co.kr/product/javapass/

[되기] 코딩 테스트 합격자 되기(자바 편) - 골든래빗