Problem Solving with Algorithms

백준 알고리즘 강의 후기(코드플러스): 기초2 - 그래프1, 중급3 - 그래프2

[한글사이트] 백준 BOJ 코드플러스/백준 코드플러스 알고리즘 강의후기
2021. 1. 21. 02:06
반응형

백준 알고리즘 기초 강의 후기 - 기초1은 여기에서 보실 수 있습니다.

https://inner-game.tistory.com/256

 

백준 알고리즘 강의 후기(코드플러스): 기초1

알고리즘 기초 1/2 프로그래밍 언어 (C++, Java)를 할 줄 알고, 기초 알고리즘을 배우는 강의입니다. 전체 강의 구성은 https://code.plus/notice/16 를 참고해주세요. 알고리즘 기초1 강의 링크: https://code..

inner-game.tistory.com

 

 

 

 

 

 

백준 코드플러스 알고리즘 강의 기초2 개요

알고리즘 기초2 강의 후기입니다.

코드플러스의 전체 강의 구성은 https://code.plus/notice/16 를 참고해주세요.

알고리즘 기초2 강의 구성은 https://code.plus/course/42 를 참고해주세요.

 

백준 알고리즘 강의 기초2를 수강하는데는 약 5시간이 걸립니다.

 

 

 

백준 코드플러스 알고리즘 강의 기초2 구성

알고리즘 기초2 강의는 다음과 같이 구성되어 있습니다.

 

개요

프로그래밍 언어 (C++, Java)를 할 줄 알고, 기초 알고리즘을 배우는 강의입니다.

500 - 브루트 포스

모든 경우의 수를 다 시도해보는 알고리즘인 브루트 포스에 대해서 알아봅니다.

경우의 수를 만들기 위해 순열, 재귀, 비트마스크 방법을 알아보고, 여러가지 문제를 해결해봅니다.

600 - 그래프 1

그래프와 그래프를 저장하는 방법인 인접 행렬, 인접 리스트를 알아봅니다. 그 다음, DFS와 BFS 알고리즘도 알아보고 여러가지 문제에 적용해봅니다.

610 - BFS

문제를 그래프로 모델링해 BFS로 풀어봅니다.

620 - 트리 1

트리와 관련된 기본적인 내용을 알아봅니다.

 

 

 

백준 코드플러스 알고리즘 강의 기초2 동영상 구성

 

 

[기초2] 600 - 그래프 1

그래프와 그래프를 저장하는 방법인 인접 행렬, 인접 리스트를 알아봅니다. 그 다음, DFS와 BFS 알고리즘도 알아보고 여러가지 문제에 적용해봅니다.

강의로 듣는다면 한시간 반정도의 분량이다.

● 600 - 그래프 1

  • ABCDE
    • 첫 문제 부터 이해를 못해서 넘나 당황스러운것;;
    • 특정숫자 5개가 A->B->C->D->E 순서로 이어져있기만 하면 되는것이다.
    • a->b 의 쌍을 map[a].add(b), map[b].add(a)로 만들어준다.
    • dfs를 모든 시작점에 대해서 출발하고, 전역변수 ans가 1로 바뀌었으면 break하고 프로그램을 종료한다.
    • 방문하지 않은것을 방문하다가, 출발지 부터 도착지까지 노드의 개수가 5개이면 ans를 1로 바꿔주고 리턴한다.
      • 이걸 모든 n노드를 방문하도록 프로그래밍 하면 시간초과가 나고, 5개만 방문하면 종료하도록 해야한다.
import java.util.*;

public class Main {
    static ArrayList<Integer>[] rel;
    static boolean[] v;
    static int ans = 0;
    
    private static void dfs(int cur, int n) {
        if(n == 5) {ans = 1; return;}
        
        v[cur] = true;
        for(int node: rel[cur]) {
            if(v[node] == false)
                dfs(node, n+1);
        }
        v[cur] = false;
    }
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int T = sc.nextInt();
        rel = new ArrayList[n];
        for(int j = 0; j < n; j++) {
            rel[j] = new ArrayList<Integer>();
        }
        v = new boolean[n];
        int i = 0;
        while(i++ < T) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            rel[a].add(b);
            rel[b].add(a);
        }
        
        ans = 0;
        for(int j = 0; j < n; j++) {
            if(ans == 0) dfs(j, 1);
        }
        System.out.println(ans);
    }    
}
  • DFS와 BFS
    • 접점중 숫자가 작은것먼저 방문하고 방문가능한것까지만 출력하는 프로그램
    • 그냥 DFS와 BFS
  • 연결 요소의 개수
    • 연결요소의 개수, 즉 쉽게말하면 유니온파인드에서 그룹의 개수를 출력
    • 구현은 DFS/BFS에서 시작하면서, 방문한적 없는 새로운노드에서 출발할때 카운트++
  • 이분 그래프
    • 정점들을 탐색하며 두가지 색으로 번갈아가며 색칠할때, 같은 간선으로 연결된 정점끼리는 같은 색 끼리 연결되지 않는 그래프를 의미한다.
    • 메인함수는 1. 그래프 구성, 2. 순회하며 색칠하는 부분 그리고 3. 체크하여 답호출 이렇게 구성된다.
  • 단지번호붙이기
    • 연결된 집들을 그룹화하고 각 그룹에 속하는 집의 수(그룹의 크기)를 오름차순으로 출력하면 된다.
    • 위의 연결 요소의 개수와 비슷하기 때문에 풀어보지 않았다.
  • 섬의 개수
    • 이것도 그룹의 개수를 구하는 것이라 풀어보지 않았다.
    • DFS/BFS 모두 가능
  • 미로 탐색
    • 출발지부터 목적지까지 DFS/BFS를 이용하여 최단거리 탐색하는것이다.
    • 풀어보지 않았다.
  • 토마토
    • 세균맨 같은건데, 모두 오염시킬수 있으면 최소날짜 출력, 없으면 -1출력이다.
    • bfs가 끝났을때, 모든 토마토를 체크하여 오염되지 않았다면 -1을 출력, 아니면 날짜 출력
    • 풀어보지 않았다.
  • 나이트의 이동 실버2
    • 갈수있는곳을 미리 구조화한뒤 bfs로 돌면서 엔드에 도착하면 종료.
    • 풀어보지 않았다.

● 601 - 그래프 1 (연습)

  • Two Dots 골드4
    • 사이클을 찾으면 되는데, 사각형을 찾아야하기때문에 꺾일때마다 카운트 해줘서 선분이 4개인지 확인하면 된다.
    • 풀어보지 않았다.
  • 서울 지하철 2호선 골드3
    • 순환선을 먼저 찾고(사이클) - DFS
    • 순환선과의 거리를 출력 - BFS
    • 이건 풀어보면 좋을것 같다.

● 602 - 그래프 1 (도전)

풀어보기

[중급3] 1200 - 그래프 2

위상 정렬, 크루스칼, 프림, 벨만 포드, 다익스트라, 플로이드 알고리즘과 관련 문제를 풀어봅니다.

● 1200 - 그래프 2

'DAG와 위상정렬' 강의

위상정렬알고리즘은 BFS, 가장 중요한건 인디그리, 인디그리가없으면 시작점으로 선택할 수 있다.

위상정렬 반복하는 부분 자주 봐야겠다.(7분)

i의 인디그리를 배열에 먼저 저장해놓고, 이게 0인것을 먼저 시작점에 넣는다.

인접행렬은 괜찮은데, 인접리스트는 간선 지우는게 까다롭다. 그리고 굳이 지울 필요도 없다. 그냥 차수만 낮추면 된다.

DFS로 짰을때는, visited[]를 true false로 해서 사용하면 된다.

1. 간선을 먼저 반대로 한다. <-방향으로. 다 방문을 해본다. 그리고 나올때 처리를 하면 된다. 왜냐하면 이게 우리가 처음부터 하고싶었던 -> 이 방향이기 때문.

 

줄 세우기 A->B, 소스코드는 문제집에서 설명


문제집 먼저풀면 좋은문제<-위상정렬조건 ( u->v )

가능하면 쉬운문제부터 풀어야 한다. 민힙을 이용하여 정렬해준다. 맥스힙에는 음수를 붙여서 넣으면 민힙이 된다.

BFS에서 시간복잡도는 O(E)인데, 여기서는 프라이어리티 큐를 쓰기 때문에 logv 모든 정점이 큐에 들어갔다가 나오면 vlogv가 됨.


작업 모든 작업을 완료하는 가장 빠른시간 구하기.

d[i] = i를 마치는 가장 빠른 시간을 기록해둠.

BFS 시작점, 그냥 큐를 쓴다. 시간비교하는 부분이 들어가야함. 시간복잡도는 O(E)

'MST' 강의

새로운 간선을 추가 하면 안되고, 원래 있던 간선을 선택해서 만든것을 스패닝트리.

여기서 간선의 가중치의 합이 최소인 트리를 최소스패닝트리(MST)라고 한다.

알고리즘 두가지는 1. 프림 2. 크루스칼 가장 중요한점은 싸이클을 만들지 않는다는 원칙

 

프림 알고리즘

1을 선택하고 난 후 V-1번을 선택한다. O(VE),

1-&amp;amp;gt;2 선택하고 난 후 후보의 간선은 3개가 아닌 4개(3번간선 포함)

 

네트워크 연결 5분부터 진행

선-선

선-선x <- 이게 중요하다, 우선순위큐에 유지, 간선이 모두 큐에 들어갔다 나오기때문에 O(ElgE)

선x-선x

 

(1,5,3)(1,2,2) -> 가장작은게 빠지고 (1,5,3) (2,5,1)(2,4,3)(2,3,4) 추가-> 작은거 2,5,1빠짐 ->그다음에 1,5,3을 보면 이미 1,5가 선택되어 무효함. 무시함, 그다음인 2,4,3을 큐에서 빼내서 진행->

근데 윗줄에서 사실 맨첫번째 요소는 필요없음. 출발점은 중요한게 아니기 때문, 그래서 두번째,세번째로 이루어진 페어로만 프로그래밍한다. 

크루스칼 알고리즘 (14분부터)

유니온파인드로 같은 그룹인지 확인해서, 사이클이 생기는지 체크한다. 


최소 스패닝 트리

유니온파인드를 이용한 크루스칼로 하기 때문에 ElgE의 수행시간을 갖는다.

루프는 엔번만 돌지만 정렬이 있어서 이로그이

'벨만포드' 강의

벨만포드는 과정으로 이해하는건 크게 의미가 없는것 같고 식으로 이해하는것이 더 깔끔하다.

느려서 잘 사용하지 않지만, 가중치가 음수일때 사용할 수 있는 유일한 알고리즘 이다.

간선(N-1)개 까지만 하도록 되있는데, 만약에 여기서 한번 더 해서 (n)개 까지 해봤을때, 최단거리에 변화가 생기면 음수사이클이 있다는것이다.

 

타임머신

?

 

웜홀

? 졸았나..

다익스트라 강의

V^2혹은 ElgE에 구할수 있는 알고리즘, 증명은 한번 읽어보시면 좋구요,

두가지가 필요함

dist[i]: 시작->i까지의 최단거리

check[i]: i를 검사했으면 True 아니면 False

dist가 가장 작으면서, 아직 체크가 안된 정점부터 시작한다.

 

최소비용 구하기

일단 v^2걸리는 방법으로 한번 시작해본다.


최소비용 구하기 2

역추적방법으로 경로를 구해본다. 역추적에서는 하나의 값이 왜 바뀌었는지 기록하면된다.

어떤 알고리즘에서 시간을 줄일때는 최소나 최대나 그런것을 포인트로 잡는다.

프림에서는 우선순위를 썼고, 어떤 범위에 대해서 하는것이면 세그먼트 트리를 쓴다.

다익스트라에서는 힙에다가 넣는다. 같은 값이 들어가도 최대 정점개수만큼 밖에 안들어가서 문제는 안된다. 이렇게 하면 ElgE <-민힙

같은 정점을 유지하지 않게 또 다른 자료구조를 사용하면 ElgV로도 가능하다. <-BST (Set)

근데 V와 E의 크기가 대회에서는 큰 차이가 없어서, 힙이 조금 더 빠른것 같은 경험이 있다.

이것도 참 좋은 강의네...

플로이드와 SPFA 강의

모든 쌍의 최단거리구하기, 소스코드가 간단하다는 장점이 있다. O(V^3)의 다이나믹 프로그래밍.

어디를 거쳐가는게 더 빠르다면, 그냥 그렇게 한걸로 바꿔버리는 알고리즘 스타일.

유도는 3차원 다이나믹이지만 실제로는 2차원다이나믹으로 풀수있다. 배낭문제 같은것을 풀어보면 비슷한 원리를 터득할 수 있다.

이 강의를 찾아서 들어보세요. 문제번호 12865

역추적 할 경우에는 next[i][j] 배열이 필요해지게 된다. 다른 모든 알고리즘은 역추적이 거의 똑같은데 플로이드만 유일하게 굉장히 독특하다.

 

SPFA 알고리즘(Shortest Path Faster Algorithm)

벨만포드의 어떤 단계에 t에 대한 값이 안바뀌었다고 가정해보면..? 벨만포드는 그래도 모든 간선을 검사하지만, 이 알고리즘은 검사하지 않는다.

큐를 이용해서 해준다. 하지만 결국 O(VE) 지만, 해보면 O(E) 나온다. 하지만 최단거리할때는 다익스트라 해서 할필요없다.

음수가중치 나올때 쓸수도있는데,  MCMF할때 그런일이 일어난다. 하지만 MCMF자체도 많이 안씀.

 

강의는 여기서 끝남. 아래는 뭐지(?)

 

최단경로

경로 찾기

플로이드

플로이드 2

케빈 베이컨의 6단계 법칙

● 1201 - 그래프 2 (연습)

임계경로 작업이라는 문제랑 비슷. 풀이도 비슷함.

가장 긴 경로에 포함된 간선의 수 구하기, 가장 긴 경로의 가중치를 먼저 구하고 역추적하면서 그 차이랑 간선 가중치를 비교해서 구하면 된다.

그런데 여기서 아랫쪽 5,3은 계산에 맞기 때문에 아니라는걸 6에서 부터 주의하고 있어야함.

인디그리 배열이 두개 필요함. 역방향도 하기 때문이다.

 

특정한 최단 경로 v1,v2를 꼭 거쳐서 가는 최단경로

다익스트라를 세번해서 1,v1,v2해서 합치면된다. 1->v1->v2->n, 1->v2->v1->n 중에 최단경로를 하면된다.

여기서 중요한 아이디어가 있는데, 무한대를 1억으로 했다. 왜냐하면 원래 하던대로 10억쯤 하면 몇번 더하다가 20억 넘어버릴수있어서 오버플로우 날까봐.


도로포장 u->v로 갈때 포장할 수도 있고, 포장하지 않을수도 있는데 k번 포장해서 최단시간을 찾는 문제(포장하면 시간0)

지금까지 몇번 포장을 해서 u에 왔는지를 먼저 알아야 한다. u->v가 포장할수 있는지 없는지 보려면..

정점은 (v,t)로정의한다. 정점v에 도착할때 까지 포장t번.

변한 이유를 정점의 정의에 추가해서 구현하면 된다. 다익스트라만 그런게 아니고, 다른 문제나 알고리즘에서도 동일하다.

K번째 최단경로 찾기 - 플래티넘5 www.acmicpc.net/problem/1854

아이디어는 이해하기 쉽지만 구현이 복잡하다...

기존처럼 1가지 최단경로만 하지말고,(dist[i]) 최단거리 k개를 모두 구할수있는 배열을 만들자.

1. k개 미만, 2.k개인 경우가 나올것이다. k개인경우에는 넣을지 말지 결정해야하는데, 맥스힙을 이용하면 자동으로 할수있다.

궁금한 민호 모든 쌍의 도시에 대해서 최소 이동 시가늘 구해놓았다. <- 플로이드 알고리즘을 사용했다는 뜻이다.

???


운동 그래프에서 사이클 길이중 최소 길이를 찾는 문제. 여러 풀이가 있지만 플로이드를 써보겠다.

d[i][j] = 0 간선이 없다고 하고 시작.

 


길의 개수

이런 행렬 제곱같은 생각을 해낼수있을까;

다시 풀어보자.


두 가중치

 


일방통행

위상정렬 아이디어를 언급했지만, 이 문제에서는 필요없다.


역사

먼저일어난사건에서 나중에 일어난 사건으로 경로가 있는지 체크만 해주면됨

모든 정점의 최단경로를 구한 다음에 그게 문제에있는지 검사하면된다.


도시 분할 계획

MST를 구한다음에 가중치가 가장 큰것을 빼면 두그룹으로 나누어짐

크루스칼로 점점 추가하다가 마지막에 멈추면 됨.


The game of death

 

● 1202 - 그래프 2 (도전)

배열 A 찾기

3번 조건만 있다고 생각하고 위상정렬로 먼저 접근한다.

2번조건을 추가한다.

 

 
반응형
반응형

공유하기

facebook twitter kakaoTalk kakaostory naver band

'[한글사이트] 백준 BOJ 코드플러스/백준 코드플러스 알고리즘 강의후기' 의 관련글

티스토리툴바