728x90 Algorithm (C++ based)/BOJ51 백준 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. 백준 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. 백준 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. 백준 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. 백준 No.9466 [텀 프로젝트] Baekjoon Online Judge No.9466 [텀 프로젝트] 문제 9466번: 텀 프로젝트 (acmicpc.net) 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 설명 학생들을 노드라고 하고, 학생들이 각각 본인이 팀을 하고 싶은 상대를 간선으로 표현하였다. 결국, 한 팀이 이루어지기 위해선 아래와 같이 싸이클이 이루어져야 한다. 빨간 간선들이 팀을 의미한다. {1, 2, 4} 세 명 이서 한 팀을, {3} 혼자서 한 팀을 이렇게 총 두 팀을 이루었고, {5, 6, 7}은 모두 팀을 이루지 못 했다. 처.. 2021. 8. 2. 백준 No.12015 [가장 긴 증가하는 부분 수열 2] Baekjoon Online Judge No.12015 [가장 긴 증가하는 부분 수열 2] 문제 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 설명 2021.07.28 - [Algorithm (C++ based)/BOJ] - 백준 No.11053 [가장 긴 증가하는 부분 수열] 백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가.. 2021. 7. 28. 백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 설명 Dynamic programming 을 이용하여 Memoization 을 통해 풀 수 있다. 아래와 같이 가장 긴 증가하는 부분수열을 구해야 하는 arr 배열이 있다. 정답을 구하기 위해서 arr 의 첫 번째 수 부터 li.. 2021. 7. 28. 백준 No.1328 [고층 빌딩] Baekjoon Online Judge No.1328 [고층 빌딩] 문제 1328번: 고층 빌딩 (acmicpc.net) 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 설명 핵심 변수 : unsigned long long city[N][L][R]; N개의 빌딩이 있고, 좌측에서는 L 개의 빌딩, 우측에서는 R 개의 빌딩이 보일 때 경우의 수의 값을 의미한다. city[1][1][1] 은 1개의 빌딩이 있고, 좌측에서는 1개의 빌딩, 우측에서는 1개의 빌딩이 보이는 경우의 수의 값을 의미한다. 이 경우엔 그냥.. 2021. 7. 12. 백준 No.1937 [욕심쟁이 판다] Baekjoon Online Judge No.1937 [욕심쟁이 판다] 문제 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 설명 DFS를 활용한 DP문제이다. land[i][j] array 를 입력되는 대나무 숲에 대한 정보이고, dp[i][j] array 를 (i, j) 위치에서 최대로 살 수 있는 일수라고 하자. 백준 사이트에 있는 입력 예시이다. 한 위치를 예로 설명을 해 볼 것이다. 위 경우를 가지고 dp[0][1]의 값을 구하는 과정, 식은 아래와 같다. dp[0][1] = max(dp[0.. 2021. 7. 11. 백준 No.17387 [선분 교차 2] Baekjoon Online Judge No.17387 [선분 교차 2] 문제 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 설명 이전 17386번: 선분 교차 1 (acmicpc.net) 문제에서 조건이 더 추가가 된 문제이다. [선분 교차 1] 문제에선 세 점이 한 직선상에 있는 경우가 없었지만, 이번 문제에선 세 점이 한 직선상에 있는 경우가 있기에 이 조건까지 처리를 해야 한다. 이전에 올린 [선분 교차 1] 게시물에서 더 추가해야 하는 조건을 설명 해 보고자 한다. 백준 No.17386 [선분 교차 1] 설명 Link : 2021.06.28 - [C++ Alg.. 2021. 6. 29. 이전 1 2 3 4 다음 728x90
