[바킹독님 블로그 정리 글입니다!] [실전 알고리즘] 0x19강 - 트리이번 시간에는 트리를 다루어봅시다. 바로 본론으로 들어가겠습니다. 특별히 트리에서의 BFS와 DFS를 또 익힐 예정입니다. 저희는 0x16강에서 이진 검색 트리를 배우며 이미 트리라는 개념을 적당blog.encrypted.gg 트리의 기본적인 특성부터 알고 가자면, 트리의 정의는 무방향이면서 사이클이 없는 연결 그래프이다. V개의 정점에 대해 V-1개의 간선을 가지는 사이클이 없는 연결 그래프라고 생각하면 된다. 트리에서의 BFS는 그래프의 BFS와는 조금 다른 의미를 가진다. 그래프의 BFS는 특정 정점에서 연결된 점을 찾는 용도로도 많이 사용되었는데, 트리는 연결 그래프이므로 방문 순서와 부모 배열, depth 배열을 채울 수 있..

https://www.acmicpc.net/problem/1707 문제를 좀 분석해 보자면 간선의 수는 200000, 정점의 수는 20000, 테스트 케이스 5개이다. 시간 복잡도는 꽤나 여유로워 보이니 문제를 분석해 보았다. 그래프를 두 집합으로 분할하되, 분할된 집합에서 인접하는 노드가 없게끔 분할하면 된다. 가장 먼저 떠오르는건 흐름은 다음과 같았다.시작점 start를 한 집합에 넣고, 인접한 점은 다른 집합에 넣는다.방문하지 않은 점 next에 대해 똑같이 1번을 수행한다.이렇게 떠올랐는데 굉장히 큰 오류들이 있었다.먼저 next는 첫 번째 단계의 start와 연관되어 있을 수 있었다. 즉, 맨 처음 시작점의 인접한 점과 그다음 방문하지 않은 점이 인접하다면? 인접하지 않다면? 모두 다른 방향으로..

3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 예제 2 3 4 3 5 1 1 30 2 3 30 1 2 40 1 2 20 3 1 70 4 4 1 10 1 1 50 2 1 20 1 1 80 3 1 0 1 2 20 2 2 10 4 3 0 2 1 0 2 2 100 1 4 20 ans : 1 2 정렬 기준이 3가지에 팀 번호까지 저장해둬야 한다. 정렬 기준은 다음과 같다. 최종 점수가 높을수록 등수가 낮다. 제출한 횟수가 낮을수록 등수가 낮다. 마지막 제출 시간이 낮을수록 등수가 낮다. 그리고 로그의 수 m이 최대 1000..

20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 7 4 apple ant sand apple append sand sand ans : sand apple append 100,000개의 단어를 기준에 따라 정렬하면 된다. 우선 빈도를 저장해둬야 하는데 최대 O(n log n)으로 저장해야 하므로 맵에 저장을 했다. 그리고 기준에 따라 정렬을 해주면 되는데 우선순위 큐를 사용했다. 정렬 기준을 설정하는 건 항상 헷갈리는데 구조체에 () 연산자 오버..

13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 예제 4 2 3 1 5 2 4 1 ans : 18 4 3 3 4 1 1 1 1 ans : 10 문제를 잘 생각해 보면 기름 값이 가장 싼 도시를 3번 도시라고 하자. 그럼 3번 도시부터 목적지까지의 거리만큼 기름을 3번 도시에서 다 사두고 2번 도시를 다시 목적지로 두고 반복하면 된다. 이렇게 구현한다면 기름 값이 가장 싼 도시를 계속해서 갱신해야 하므로 우선순위 큐를 사용했다. 그리고 목적지를 갱신하는 방법은 좀 번거로워서 방문처리를 하는 방식을 ..

10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 예제 4 1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900 4 918 917 916..