728x90 Algorithm (C++ based)70 백준 No.11266 [단절점] BOJ No.11266 [단절점] 문제 11266번: 단절점 (acmicpc.net) 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 설명 * 그래프 * 단절점 단절점 : 어떠한 그래프에서 임의의 정점을 제거했을 때 두 개 이상의 그래프들로 나누어지게 하는 정점 개념 자체는 간단하다. 위 그래프에서 단절점은 3, 5 번째 정점이 될 것이다. 3번 정점을 제거함으로써 3개의 그래프로 나뉘어지고, 5번 정점을 제거함으로써 2개의 그래프로 나뉘어졌기 때문이다. 단절점에 대한 파악은 루트노.. 2021. 8. 21. 백준 No.1261 [알고스팟] BOJ No.1261 [알고스팟] 문제 1261번: 알고스팟 (acmicpc.net) 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 설명 * Dijkstra (다익스트라) * 너비 우선 탐색 (BFS) 주어진 미로의 각 좌표들을 노드라고 생각하고, 좌표에서 이동할 수 있는 방향은 상하좌우로 인접한 네 방향이므로 이 네 방향을 하나의 간선이라고 생각할 수 있다. 좌표의 최대 크기는 100 * 100 이다. 따라서 노드의 최대 개수는 10,000 개가 되며 한 노드당 좌표의 모서리에 위치한.. 2021. 8. 17. 백준 No.1626 [두 번째로 작은 스패닝 트리] BOJ No.1626 [두 번째로 작은 스패닝 트리] 문제 1626번: 두 번째로 작은 스패닝 트리 (acmicpc.net) 1626번: 두 번째로 작은 스패닝 트리 첫째 줄에 그래프의 정점의 수 V(1 ≤ V ≤ 50,000)와 간선의 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 간선으로 연결된 두 정점과 그 간선의 가중치가 주어진다. 가중치는 100, www.acmicpc.net 설명 * 최소 스패닝 트리 / 최소 신장 트리 (MST) * 최소 공통 조상 (LCA) 먼저 최소 스패닝 트리(MST) 를 먼저 구해야 한다. 두 번째로 작은 스패닝 트리는 앞서 구한 MST 보다 총 가중치의 값은 최소한으로 늘어나야 한다. 문제에서 예제 입력을 가지고 최소 스패닝 트리.. 2021. 8. 17. 백준 NO.13537 [수열과 쿼리 1] Baekjoon Online Judge No.13537 [수열과 쿼리 1] 문제 13537번: 수열과 쿼리 1 (acmicpc.net) 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 설명 * 정렬 * 인덱스드 트리 * 세그먼트 트리 (Segment tree) 세그먼트 트리, 인덱스드 트리를 이용하여 풀 수 있으며 이번에는 인덱스드 트리를 통해 풀어보았다. 세그먼트 트리나 인덱스드 트리에서 가장 중점은 트리의 노드를 어떻게 정의하느냐 인 것 같다. 이번 문제에선 각 트리의 노드.. 2021. 8. 14. 백준 No.14427 [수열과 쿼리 15] Baekjoon Online Judge No.14427 [수열과 쿼리 15] 문제 14427번: 수열과 쿼리 15 (acmicpc.net) 14427번: 수열과 쿼리 15 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 www.acmicpc.net 설명 * 세그먼트 트리 (Segment tree) 기본적인 세그먼트 트리 자료구조를 통해 풀 수 있는 문제이다. 1. 트리의 노드들에 그 노드에 해당하는 수열의 영역 내에서 최소값을 가지는 원소의 {값, 인덱스} 를 저장한다. 최소값을 저장하는 조건은 문제의 요구대로 아래.. 2021. 8. 13. 백준 No.8980 [택배] Baekjoon Online Judge No.8980 [택배] 문제 8980번: 택배 (acmicpc.net) 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 설명 * 그리디 알고리즘 (Greedy algorithm) * 정렬 (Sorting) 그리디 알고리즘을 통해 풀 수 있는 문제이다. 그리디 알고리즘으로 이 문제를 푼다면? 택배차는 되는만큼 박스를 싣는다고 생각하면 된다. 단, 택배차의 최대 적재 개수가 있으므로 그 적재 개수를 고려하면서 되는만큼 실어야 한다. 잘 생각을 해 보면, .. 2021. 8. 12. 백준 No.2887 [행성 터널] Baekjoon Online Judge No.2887 [행성 터널] 문제 2887번: 행성 터널 (acmicpc.net) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 설명 최소 스패닝 트리(최소 스패닝 트리 / 최소 신장 트리 (MST)) 를 통해 풀 수 있는 문제이다. 각 정점끼리의 간선의 가중치의 값은 두 정점의 거리에 따른다. 결국 모든 정점 사이에 간선이 존재하게 된다. 정점의 수는 최대 100,000 개 이기 떄문에 이 때 총 간선의 수는 약 (100,000^2) .. 2021. 8. 10. 최소 스패닝 트리 / 최소 신장 트리 (MST) 최소 스패닝 트리 / 최소 신장 트리 (MST : Minimum Spanning Tree) by Kruskal Algorithm & Prim Algorithm 정의 최소 스패닝 트리(최소 신장 트리, MST : Minimum Spanning Tree)란, 모든 노드들이 가중치가 있는 무방향 간선에 연결이 되어있을 때, 모든 노드들을 연결하는 방법 중 사이클이 없으면서 가중치의 합이 최소가 되는 트리를 의미한다. 좌측과 같은 그래프가 있다고 할 때, 최소 스패닝 트리은 우측의 빨간 간선들로 이루어진 그래프가 된다. 완성된 최소 스패닝 트리는 모든 노드들이 전부 연결이 되어있으며, 사이클이 존재하지 않는다. 또한 V개의 정점을 가진 그래프라고 할 때, 최소 스패닝 트리는 V - 1 개의 간선을 가진 트리가 .. 2021. 8. 9. 백준 No.17070 [파이프 옮기기 1] No.17070 [파이프 옮기기 1] 문제 17070번: 파이프 옮기기 1 (acmicpc.net) 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 설명 동적할당(DP : Dynamic programming) 을 이용하여 풀 수 있는 문제이다. 점화식을 위한 dp 배열은 3차원으로 선언을 하였다. dp[ i ][ j ][ k ] == (i, j) 좌표로 오는 파이프가 k 방향에서 올 수 있는 경우의 수 (k == 1 인 경우는 좌측, k == 2 인 경우는 위, k == 3 인 경우는 .. 2021. 8. 8. 백준 No.3830 [교수님은 기다리지 않는다] Baekjoon Online Judge No.3830 [교수님은 기다리지 않는다] 문제 3830번: 교수님은 기다리지 않는다 (acmicpc.net) 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 설명 유니온 파인드 (2021.08.06 - 유니온 파인드 (Union Find, Disjoint set))알고리즘을 이용하여 샘플(노드)을 추가해야 하는 경우엔 추가하고 두 샘플의 무게를 비교할 땐 비교를 해야한다. 유니온 파인드 알고리즘은 노드들간의 그룹 여부를 알 수 있는 알고리즘.. 2021. 8. 6. 유니온 파인드 (Union Find, Disjoint set) 유니온 파인드 (Union Find, Disjoint set) 정의 유니온 파인드(Union Find) 는 서로소 집합(Disjoint-set) 이라고도 불린다. 이는 집합 혹은 그룹 관리를 효율적으로 할 수 있는 알고리즘 이다. 그룹은 트리의 구조로 관리가 된다. 한 트리에 여러 그룹이 있는 것이 아니라 그룹의 개수만큼 트리가 생성이 되는 것 이다. 설명 위 예시의 경우는 두 가지 트리가 존재한다. 그룹이 두 개 존재하는 경우인 것 이다. 두 노드끼리 같은 그룹인지 아닌지 판단하는 기준은 해당 노드의 루트 노드가 같은지 판단하면 된다. 위 예시에서 2, 4번째 노드는 둘 다 루트노드가 1로 동일하다. 따라서 같은 그룹이다. 하지만 3, 6번째 노드는 각각 루트노드가 1, 5번째 노드이다. 따라서 이 두.. 2021. 8. 6. 백준 No.1005 [ACM craft] Baekjoon Online Judge No.1005 [ACM craft] 문제 1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 설명 위상정렬(2021.08.05 - [Algorithm (C++ based)/Algorithm 이론] - 위상 정렬 (Topological Sort))의 기본 개념을 이용하여 풀 수 있는 문제이다. 위상정렬을 통해 각 건물(노드)에 방문을 할 때 마다 그 건물을 짓는데 걸리는 시간을 계속해서 최대값으로 업데이트를 한다. .. 2021. 8. 5. 위상 정렬 (Topological Sort) 위상 정렬 (Topological Sort) 위상정렬 위상정렬은 무향 비순환 그래프 (DAG : Directed Acylic Graph) 에서 정해진 순서에 맞게 나열을 하는 것 이다. 일상에서의 예시로 대학교 과목 이수도 에서 선수과목이 있는 것을 생각해 볼 수 있다. 과목 F 를 듣기 위해선, 과목 D, E 를 들어야 한다. 또 과목 D를 듣기 위해선 과목 A를, 과목 E 를 듣기 위해선 과목 B, C 를 들어야 하고 과목 B를 듣기 위해선 과목 A를 들어야 한다. 이 경우 가장 처음에 들을 수 있는 과목은 선수과목이 없는 과목 A와 과목 C 이다. 위상 정렬은 이러한 선수과목이 없는 경우 즉, 진입 간선이 없는 경우를 따져가면서 정렬을 해 나가는 알고리즘 이다. 설명 1. 주어진 노드와 간선에 대한.. 2021. 8. 5. 유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 유클리드 호제법 이란 두 자연수 사이의 최대공약수(GCD) 를 구하는 알고리즘 이다. gcd(a, b) == a 와 b 의 최대공약수 라고 할 때 알고리즘에 사용되는 식은 다음과 같다. gcd(a, b) == gcd(b, a % b) ... (b 2021. 8. 4. 백준 No.7453 [합이 0인 네 정수] Baekjoon Online Judge No.7453 [합이 0인 네 정수] 문제 7453번: 합이 0인 네 정수 (acmicpc.net) 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 설명 투 포인터 알고리즘을 활용하여 풀었다. 투 포인터를 하기 이전 투 포인터를 할 수 있는 상태를 만들어야 한다. 위와 같이 4개의 배열이 주어졌다고 할 때, 결국 네 배열의 원소의 합이 0인 경우가 몇 번 있는지를 찾는 것 이므로, 각각의 배열들은 다른 배열과 무조건 한 번씩은 더해지는 작업을 거치게 된.. 2021. 8. 2. 이전 1 2 3 4 5 다음 728x90
