백준

[baekjoon 11725] 트리의 부모 찾기- 트리, 그래프, BFS, DFS (C++)

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 루트는 1로 고정되어있고, 각 노드들의 부모를 출력하면 되는 문제이다. 일단 벡터를 통해 양 노드의 값을 저장해주고, DFS탐색을 노드 1부터 해준다. 트리의 특성상 리프 노드를 제외하고 연결되어 있으므로 연결된 노드를 통해 탐색해주면서, 부모를 저장해준다. 현재 x노드를 방문한 상태에서 x와 연결된 y가 아직 방문되지 않았다는 것은 y는 x의 자식 노드라는 의미이다. 방문하지 않았다면 DFS(연결된 다음 노드)를 진행해주면서 parent [연결된 다음 노드] = 현재 노드..

[baekjoon 1916] 최소비용 구하기 - 그래프, 다익스트라 (C++)

www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net #include #include #include using namespace std; #define INF 1e9; vector v[1001]; priority_queue pq; int dist[1001]; int n, m, from, to, fromToCost, start, dest; int main() { ios::sync_with_stdio(false); cin.tie(0..

[baekjoon 18870] 좌표 압축 - 정렬, 값 압축 (C++)

www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 여기서 압축은 전체 좌표에서 해당 좌표값보다 작은 좌표의 개수(중복 제거)로 줄이는 것을 의미한다. 그래서 벡터를 두 개 이용해서 하나의 벡터에 중복된 값을 제거, 정렬을 해준 후, 이분 탐색을 통해 개수를 구했다. #include #include #include using namespace std; vector v, v1; int N, num; int main..

[baekjoon 11726] 2xN 타일링- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 기본 유형의 DP 문제이다. DP는 수학적인 접근이 필요해서 연습이 많이 필요한 것 같다. 또한, 주어진 문제를 작은 문제로 나눠서 푼 뒤, 결과를 통해 문제를 해결하는 것은 분할 정복과 비슷하다. 하지만 분할 정복은 문제를 분할 시 겹치는 문제가 발생하지 않지만 DP는 겹치는 문제들이 발생한다. 따라서 보통 메모이제이션을 이용해서 같은 문제에 대한 결과가 나오는 함수의 호출을 줄여준다. #include using namespace..

[baekjoon 7662] 이중 우선순위 큐 - Map, MutliMap (C++)

www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 이중 우선순위 큐라는 문제로 값을 insert, delete 하되 최댓값과 최솟값에 접근해야 한다. 최대 힙, 최소 힙을 구현해서 푸는 방법도 있지만 난 STL을 연습하기 위해서 Map STL의 MutliMap을 사용했다. Map의 멤버 함수에서 m.begin()과 m.rbegin()을 통해 Map의 앞과 뒤에 접근할 수 있었다. Map은 균형 이진트리로 기본값은 오름차순이다. 즉, m.begin()을 통해..

[baekjoon 10816] 숫자 카드2 - Hashmap, 이분탐색 (C++)

www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 입력 수들을 받고, 찾고자 하는 수에 해당하는 수가 몇 개가 있는지 출력하는 문제다. 입력 개수는 50만 개, 찾는 수 또한 50만 개로 일반적인 배열에 넣고 선형 탐색을 하게 되면 O(N^2)로 시간제한 1초를 넘기게 된다. 보통 c++기준 N = 1억이면 1초라고 한다. 따라서 보통의 시간 복잡도가 O(1)인 HashMap을 이용하거나 O(logN)인 이분 탐색을 이용해야 ..