알게된 팁-4
2023. 1. 3. 20:49
1. 그래프 DFS (check 기능 추가)
private static void DFS(int start) {
visited[start] = true;
for(int i : A[start]){ // 인접 리스트로 받아서 start에서 연결된 모든 노드를 탐색
if(!visited[i]){
DFS(i);
}else if(check[start] == check[i]){ // 방문한 곳이면 (+ 조건)
IsEven = false;
}
}
}해당 노드(start)에서 DFS를 실행시킨다.
우선 현재 노드의 방문 배열을 true로 한다.
그리고 해당 노드의 인접 리스트를 한바퀴 돌면서 방문 안한곳이면 그 노드로 DFS 를 수행한다.
방문한 곳이면 check로 집합이 배정되어 있을테니 비교 후 같으면 IsEven을 바꾼다.
2. 유니온파인드 (백준 1717)
1. 처음에는 노드가 연결돼 있지 않으므로 각 노드의 대표 노드는 자기 자신입니다. 각 노드의 값을 자기 인덱스 값으로 초기화 한다.
2. find 연산으로 특정 노드의 대표 노드를 찾고, union 연산으로 2개의 노드를 이용해 각 대표 노드를 찾아 연결합니다. 그리고 질의한 값에 따라 결과를 반환
<유니온 파인드에서 자주 실수하는 부분>
find 연산을 수행할 때 재귀 함수에서 나오면서 탐색한 모든 노드의 대표 노드값을 이번 연산에서 발견한 대표 노드로 변경하는 부분과, union 연산에서 선택된 노드끼리 연결하는 것이 아닌 선택된 노드의 대표 노드끼리 연결하는 부분이 유니온 파인드에서 가장 많이 실수하는 부분임.
우선 해당 문제에서는 0일때 union
for(int i = 0 ; i<M;i++){ // 질의 계산하는 부분
int question = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
if(question == 0){ // union
union(a,b);
}else{ // 두 원소 같은지 보기
boolean result = checkSame(a,b);
if(result){
System.out.println("YES");
}else{
System.out.println("NO");
}
}
}
union 메서드 구현할 때 대표노드 끼리 연결해줘야 하는데 대표노드를 찾을때 find 메서드를 쓴다.
만약 대표노드가 같다면 같은 집합이다.
private static void union(int a, int b) {
// 대표노드를 찾아서 연결하기
a = find(a);
b = find(b);
if(a != b){
parent[b] = a; //연결
}
}
find 메서드는 재귀를 이용하여 value와 index가 같은곳까지 들어갔다가 같을때의 값을 return해주는 것이다.
그리고 return parent[a] = find(parent[a])를 통해 바로 경로 압축을 해준다. (**중요**)
private static int find(int a) {
if(a == parent[a]) return a;
else{
return parent[a] = find(parent[a]); // value를 index로 바꿔서 찾아보기
} // 경로 압축 로직
}
3. 위상정렬
"순서가 정해져 있는 작업"을 차례로 수행해야 할 때 그 순서를 결정해 주기 위해 사용하는 알고리즘
우선 그래프를 인접리스트로 표현하고 진입차수배열(indegree)를 선언하고 입력값 받아서 다 넣는다
ArrayList<ArrayList<Integer>> A = new ArrayList<>();
int indegree[] = new int[N+1];
for(int i =0; i < M ; i++){
int S = sc.nextInt();
int E = sc.nextInt();
A.get(S).add(E);
indegree[E]++; // 진입 차수 배열 데이터 저장 부분
}
다음 큐를 사용하여 위상정렬을 실행한다.
Queue<Integer> queue = new LinkedList<>();
for(int i = 1 ; i <=N;i++){
if(indegree[i] == 0){
queue.offer(i);
}
}
while(!queue.isEmpty()){
int now = queue.poll();
System.out.println(now+ " ");
for (int next : A.get(now)){
indegree[next]--;
if(indegree[next] == 0) queue.offer(next);
}
}
4. DP 배열
DP배열에는 항상 의미가 있어야하고 이해해야한다
이 문제에서는 D[i][j]에서 i는 총숫자 갯수, j는 선택수 갯수
즉 i개중 j개를 뽑았을 때 조합 경우의 수를 표현하는 것임
점화식 필요없이 기본적으로 알수있는 것들은 초기화를 함
D[i][1] = i , D[i][0] = 1 , D[i][i] = 1 , 총갯수보다 선택수가 큰 경우는 0으로 setting
다음 구한 점화식을 이용
점화식 구하기
1. 특정 문제를 가정하기
2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기(★)(예를 들어 5개의 데이터중 앞의 4개는 이미 선택이 완료된 데이터로 가정하고 마지막 데이터를 선택함과 선택안함으로 나누어 전체를 표현한다.)
3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출하기 (일반)
5. 점화식 구하기
1. 점화식의 형태와 의미를 도출합니다
D[N] = 2*N 직사각형을 채우는 경우의 수
D[N-1], D[N-2], ... 는 이미 계산되어 있다고 가정하고 인과관계를 생각하면 점화식 구하기 쉬움
2. 점화식을 구합니다.
D[N-1]에서 D[N]을 만드는 경우의 수는 그냥 마지막에 하나만 붙이면 되므로 똑같다
D[N-2]에서 D[N]을 만드는 경우의 수는 2가지 이지만 그중에서 하나는 D[N-1]의 경우와 같은 경우다
결국에는 D[N] = D[N-1] + D[N-2] 이다.
3. 점화식으로 D 배열을 채운 후 D[N]의 값을 출력합니다.
6. 최대공약수 계산 (유클리드 호제법)
두 자연수 A,B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 합시다.
이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다. (재귀로 구현 가능)
def gcd(a,b):
if a % b == 0"
return b
else:
return gcd(b,a%b)
7. 2차원 리스트의 맵정보 입력 받기
for(int i = 0 ; i<n ; i++){
String str = sc.nextLine();
for (int j = 0 ; j<m ; j++){
graph[i][j] = str.charAt(j) - '0';
}
}
8. 그래프 인접리스트
...
static ArrayList<ArrayList<Integer>> A = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
visitedbfs = new boolean[N+1];
visiteddfs = new boolean[N+1];
for(int i=0; i<N+1; i++) {
A.add(new ArrayList<Integer>());
}
for(int i = 0 ; i < M ; i++){
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
A.get(a).add(b);
A.get(b).add(a);
}
...
9. arrayList 정렬하기
for(int i=0; i<N+1; i++) {
Collections.sort(A.get(i));
}
10. StringBuilder 이용하기
StringBuilder sb = new StringBuilder();
sb.append((bit & (1 << (num - 1))) != 0 ? "1\n" : "0\n");
System.out.println(sb);;
