25/02/13 (목)
금요일같은 목요일입니다! 내일 졸업식때문에 휴가를 냈기 때문입니다!
이런 이유 하나만으로도 힘이 납니다!
근데 진짜 하나도 안피곤하고 집중이 잘됩니다
내일 수업을 못듣는만큼 오늘 열심히 들어보겠습니다!
1. 교재 강의
1.1. Ch10 집합
1) 집합과 상호배타적 집합의 개념
활용 분야
- 이미지 분할
- 도로 네트워크 구성
- 최소 신장 트리 알고리즘 구현에 활용이 된다
- 게임 개발
- 클러스터링 작업
2) 집합의 연산
대표 원소 : 집합의 부모 노드 (집합 전체의 대표 원소)
3) 유니온-파인드 알고리즘
파인드 연산
- 부모를 이어서 자기 자신을 찾아가는 과정
경로 압축
- 효율적으로 파인드 연산
- 집합 형태를 유지하면서 트리 높이를 줄임
합치기 연산 (유니온)
- 랭크 : 현재 노드를 기준으로 했을 때 가장 깊은 노드까지의 경로 길이
- 트리가 깊어질수록 커지는 연산비용 개선
강사님> 구구단 외우듯이 외워서 필요할때 바로 써야한다
1.2. Ch11 그래프
1) 그래프의 개념
그래프 : 정점과 간선
으로 표한 비선형 데이터 구조
노드, 간선, 가중치
인접행렬, 인접리스트
2) DFS, BFS
- DFS
- BFS : 가중치가 없는 경우 최단 경로
2. 실습
1) 유니온-파인드 알고리즘
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class UnionFindCycle {
static int v, e;
static int[] parent; // 각 원소(정점 번호)별 집합 관계를 표현하는 1차원 배열
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
v = Integer.parseInt(st.nextToken());
e = Integer.parseInt(st.nextToken());
// 그래프 정점(1 ~ 6) 간 집합 표현
// #1. 1차원 배열 생성
parent = new int[v + 1]; // 0 dummy
// #2. 1차원 배열 초기화
// 각 원소별 자기 자신이 대표원소가 되도록 ( 모든 정점이 각각 서로소인 집합 )
makeSet();
// 최초 parent 배열
System.out.println(Arrays.toString(parent));
// #3. 주어진 테케에 맞게 union() 진행
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
// union 전에 cycle 확인
if( findSet(x) == findSet(y) ) {
// cycle 발생
System.out.println(x + ", " + y + " cycle 발생!!!");
System.out.println(Arrays.toString(parent));
}else {
union(x, y); // findSet(x) == findSet(y) 이 이미 union() 에 포함 <= cycle 처리에 비효율적임. MST 에서 개선!!
System.out.println(x + ", " + y + " union");
System.out.println(Arrays.toString(parent));
}
}
}
static void makeSet() {
for (int i = 1; i <= v; i++) {
parent[i] = i; // 모두가 대표 원소
}
}
// 전달된 x 원소의 대표원소 찾아서 return
// static int findSet(int x) {
// if( parent[x] == x ) return x; // 대표원소이면 x 리턴
// return findSet(parent[x]);
// }
// 전달된 x 원소의 대표원소 찾아서 return
// Path Compression
static int findSet(int x) {
if( parent[x] == x ) return x; // 대표원소이면 x 리턴
return parent[x] = findSet(parent[x]); // 맨 꼭대기 대표원소의 index 값이 리턴되어 돌아오는데 이 중간 과정의 x 의 부모 parent[x] 에 넣는다.
}
// 전달된 두 원소 x, y 에 대해, x가 속한 집합과 y가 속한 집합을 하나의 집합으로 합친다.
static void union(int x, int y) {
int px = findSet(x);
int py = findSet(y);
// px == py 이면 이미 같은 집합
// 그렇지 않은 경우 규칙부여할 수 있다. 아래 코드는 작은 값을 부모로.
if( px < py ) parent[py] = px;
else parent[px] = py;
}
}
/*
7 9
1 2
1 5
5 6
2 3
2 6
3 4
6 4
6 7
4 7
*/
2) DFS, BFS
package basic.DFS_BFS;
import java.util.LinkedList;
import java.util.Queue;
// 2차원 배열 상하좌우 탐생을 통한 dfs, bfs
// 한번 방문한 좌표는 다시 방문하지X
public class DFS_BFS_Test {
static int[][] map = {
{0, 0, 0, 0, 0, 0, 0}, // dummy 각 열, 행의 0번째는 사용 X
{0, 11, 12, 13, 14, 15, 16},
{0, 21, 22, 23, 24, 25, 26},
{0, 31, 32, 33, 34, 35, 36},
{0, 41, 42, 43, 44, 45, 46},
{0, 51, 52, 53, 54, 55, 56},
{0, 61, 62, 63, 64, 65, 66},
};
// 상 - 하 - 좌 - 우 순서
static int[] dy = { -1, 1, 0, 0 };
static int[] dx = { 0, 0, -1, 1 };
// 재방문을 방지를 위한 자료구조
static boolean[][] visit;
public static void main(String[] args) {
visit = new boolean[7][7]; // 0 dummy visit 초기화
// dfs(3, 3);
bfs(3, 3); // Queue 자료구조 필요함
}
static void dfs(int y, int x) {
// 해당 좌표에서 할 일 진행
visit[y][x] = true;
System.out.println(map[y][x] + " ");
for (int d = 0; d < 4; d++) {
int ny = y + dy[d];
int nx = x + dx[d];
if (ny < 1 || nx < 1 || ny >= 7 || nx >= 7 || visit[ny][nx])
continue;
dfs(ny, nx);
}
}
static void bfs(int y, int x) {
// 시작 Node를 queue 에 넣고 출발
Queue<Node> queue = new LinkedList<>();
queue.offer(new Node(y,x));
visit[y][x] = true;
while (!queue.isEmpty()) {
Node node = queue.poll();
// 해당 좌표에서 할 일 진행
System.out.println(node);
// 꺼낸 Node 객체로부터 갈 수 있는
for (int d = 0; d < 4; d++) {
int ny = node.y + dy[d];
int nx = node.x + dx[d];
if (ny < 1 || nx < 1 || ny >= 7 || nx >= 7 || visit[ny][nx])
continue;
queue.offer(new Node(ny,nx));
visit[ny][nx] = true;
}
}
}
static class Node {
int y, x;
Node (int y, int x) {
this.y = y;
this.x = x;
}
@Override
public String toString() {
return "Node [y=" + y + ", x=" + x + "]";
}
}
}
3) G5_7576_토마토
https://www.acmicpc.net/problem/7576
3. WorkShop
- 인접 리스트, 인접 행렬 만들기 (완료)
- https://www.acmicpc.net/problem/2667
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class Main{
//이동
static int[] dy = {1,-1,0,0};
static int[] dx = {0,0,-1,1};
//단지와 방문여부
static int[][] map;
static boolean[][] visited;
//단지 번호와 결과
static int address = 1;
static List<Integer> result = new ArrayList<>();
//변수 정의
static int N, num;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//입력 받고 초기화
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visited = new boolean[N][N];
result = new LinkedList<>();
//단지 입력 받기
for (int i = 0; i < N; i++) {
String str = br.readLine();
for (int j = 0; j < N; j++) {
map[i][j] = str.charAt(j) - '0';
}
}
//DFS
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(map[i][j] == address && !visited[i][j]){
num = 0;
dfs(i, j);
result.add(num);
}
}
}
Collections.sort(result);
System.out.println(result.size());
for (int r: result) System.out.println(r);
}
public static void dfs(int y, int x){
visited[y][x] = true;
num++;
for (int i = 0; i < 4; i++) {
int ny = dy[i] + y;
int nx = dx[i] + x;
if (ny >= 0 && ny < N && nx >= 0 && nx < N) {
if (map[ny][nx] == 1 && !visited[ny][nx]) {
dfs(ny, nx);
}
}
}
}
}
4. 마무리
1) 더 공부할 것
- 토요일 기사시험 합격하기
- 토마토 주말에 풀기
'LG 유플러스 유레카 > 알고리즘' 카테고리의 다른 글
| [15일 차] 알고리즘 (휴가) (0) | 2025.02.17 |
|---|---|
| [13일 차] 알고리즘 (Basic5) (0) | 2025.02.12 |
| [12일 차] 알고리즘 (Basic4) (0) | 2025.02.11 |