'C++' 태그의 글 목록
본문 바로가기
728x90

C++34

백준 No.11400 [단절선] BOJ No.11400 [단절선] 문제 11400번: 단절선 (acmicpc.net) 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 설명 * 그래프 * 단절선 단절선 : 어떠한 그래프에서 임의의 간선을 제거했을 때 두 개 이상의 그래프들로 나누어지게 하는 간선 [단절점]과 거의 비슷하게 생각을 하면 된다. 하지만 간선을 제거하는 경우는 단절점과 같이 정점을 제거하는 경우와 조금 다르게 다뤄지는 부분이 있다. 1. 단절선을 찾는 알고리즘은 단절점을 찾는 알고리즘과는 달리 루트노드를 .. 2021. 8. 29.
백준 No.3190 [뱀] BOJ No.3190 [뱀] 문제 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 설명 * 구현 우선순위 큐 와 셋 을 사용하여 구현을 해서 풀었다. 게임이 끝나는 조건은 두 가지 조건이 있다. 1. 벽과 만나는 경우 -> 현재 위치가 맵을 벗어났을 때 현재 시간을 return 하였다. 2. 몸과 부딪히는 경우 -> 현재 몸이 있는 좌표들을 set 에 추가하여 몸과 부딪히는 여부를 파악하였다. 2-1) 현재 좌표에 해당하는 set 이 이미 있다면, 몸과 부딛힌 경우이므로 현재.. 2021. 8. 26.
백준 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.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.
백준 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.
유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 유클리드 호제법 이란 두 자연수 사이의 최대공약수(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.
백준 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.
728x90