21.01.11. (월) 20시 ~ 23시
문다연 wikidocs.net/103937 에 게시된 내용들을 보여 파이썬의 기초적인 문법, 함수 선언 방식, 반복문 사용법 등에 대해 학습했다. 데이터 타입의 튜플은 자바에서도 사용해보지않은 자료형이라 더 학습할 내용이 많을 것 같고, 여러 모듈과 파일을 다루는 내용까지 학습했다.
문혜림 『결과』
- K번째로 큰 수와 대표값을 구하는 알고리즘 문제 이해하며 풀기 완료
박형기
1. SCC 강한연결요소 기본문제를 풀어보았다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static ArrayList<TreeSet<Integer>> graph = new ArrayList<>(); // 그래프
static ArrayList<TreeSet<Integer>> revgraph = new ArrayList<>(); // 역방향 그래프
static boolean[] check; // 지나간 노드인지 확인하는 배열
static Stack<Integer> stacking = new Stack<>(); // 첫 DFS를 저장할 스택
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
check = new boolean[V + 1];
for (int i = 0; i < V + 1; i++) {
TreeSet<Integer> set = new TreeSet<>();
graph.add(set);
TreeSet<Integer> set2 = new TreeSet<>();
revgraph.add(set2);
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
graph.get(start).add(end);
revgraph.get(end).add(start);
}
// 첫 DFS
for (int j = 1; j < V + 1; j++) {
if (check[j] == false) {
dfs(j);
}
}
Arrays.fill(check, false); // 재사용을 위해 확인용 배열을 초기화 해준다
TreeSet<SCC> scc = new TreeSet<>(); // SCC묶음들을 저장할 집합
// 오름차순 정렬을 위해 treeset 사용
// SCC 묶기 시작
while (!stacking.isEmpty()) {
int poll = stacking.pop(); // 이전에 저장한 스택순서대로 노드를 탐색한다
if (check[poll] == true) { // 탐색했던 노드일 경우 넘어간다
continue;
}
SCC comp = new SCC(poll); // SCC를 하나 만들어준다
// 최솟값과 SCC노드들을 가지고 있다
dfs2(poll, comp);
scc.add(comp); // SCC가 만들어지면 SCC묶음에 저장해준다
}
// SCC 묶기 끝
// 출력
System.out.println(scc.size()); // 총 SCC의 개수 출력
for (SCC index : scc) {
for (int i : index.set) {
System.out.print(i + " ");
}
System.out.println(-1);
}
}
private static void dfs(int start) {
check[start] = true;
for (int i : graph.get(start)) {
if (check[i] == false) {
dfs(i);
}
}
stacking.add(start); // DFS탐색이 끝나는 순으로 스택에 저장
}
private static void dfs2(int start, SCC comp) {
check[start] = true;
comp.set.add(start); // 탐색된 노드들은 모두 한 SCC묶음이 된다
if (comp.min > start) { // 최솟값은 계속 갱신해 준다
comp.min = start;
}
for (int i : revgraph.get(start)) { // 역방향 그래프탐색
if (check[i] == false) {
dfs2(i, comp);
}
}
}
private static class SCC implements Comparable<SCC> {
int min; // 최솟값
TreeSet<Integer> set = new TreeSet<>(); // 노드들은 오름차순 정렬
public SCC(int m) {
min = m;
}
@Override
public int compareTo(Main.SCC o) { // treeset안에서 최솟값을 기준으로 오름차순 정렬
return min - o.min;
}
}
}코사라주 알고리즘을 사용하였다
알고리즘의 순서
-
정방향 그래프를 1번 노드부터 DFS탐색을 시작한다. DFS가 끝나는 순으로 Stack에 넣어준다.
-
만약 탐색이 되지 않은 노드가 있을경우 그 노드부터 다시 DFS를 돌려준다.
→ 1에서 V까지의 모든 노드를 시작으로 잡아서 탐색해주면 된다, 이미 탐색된 노드일경우 넘어간다.
-
그렇게 저장이 된 Stack에서 하나씩 pop한 노드를 시작으로 역방향 그래프를 탐색한다.
-
pop이 된 노드를 기준으로 탐색된 노드들은 모두 한 SCC가 되는것이다.
5.그렇게 Stack에서 계속 꺼내주되, 이미 탐색이 된 노드가 pop이 될경우 넘어간다.
알고리즘을 구현하는데 있어서 큰 어려움은 없었으나 SCC노드들은 모두 저장하되, 오름차순을 고집하여 약간의 까다로움이 있었다.
유정균
백준 1629 곱셈 (분할정복)
이문제는 a b c 세수가 주어지면 a를 b번 곱하고 c 로나눈 나머지를 구하는것이다
분할정복이 어떻게 적용되냐면 3을 100번 곱하는 과정을 보자 이는 단순히
100번 곱해주는것도 가능하겠지만 3을 제곱해주고 나온9를 다시제곱해준다 그러면
계산은 2번했지만 실제론3번한효과와같다 이를 극대화시키는 알고리즘이다
이는 재귀를 이용하여 구현할수있다 제곱 메소드를 써준뒤
b가 0이면 1 반환 1이면 a를 c로 나눈나머지 반환 그리고 2로 나누어떨어지면
b를 2로나누어 함수를 재호출해준다 또한 2로 나누어떨어지지않으면 1을빼주어
다음호출때 나누어떨어질수있게해준다
위를반복하면 목표하는 값을 얻을수있다
문다연 https://github.com/dayo2n/MGK_winter_2020/projects/1#card-52573423
문혜림 https://github.com/moo-nerim/20_Winter-Mogakco/blob/main/Lecture_03.py
박형기 https://blog.naver.com/qkrgudrl0324/222204366471
유정균 https://blog.naver.com/kyun1229/222204350647
