c++
[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 2225] 합분해- DP(동적 프로그래밍) (C++)
www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제의 조건은 N, K가 주어졌을 때 N을 K개의 숫자로 구성하는 경우의 수를 구하는 것이다. 예시로 N이 2이고 K 또한 2이면 경우의 수는 3개로 (0,2), (1,1), (2,0)이다. (0을 포함하고, 1-2, 2-1은 각각 카운트된다.) DP 배열은 2차원 배열로 구성되며, DP[N][K]로 N을 K개로 구성하는 경우의 수를 저장해주었다. 또한 순서가 있는 경우의 수이므로 순열의 경우로 생각해야 하며, 세 자릿수의 순열은 3!이다. 네 자릿수는 4! DP[0][2] ~ DP[N][2]배열엔 각각 2개로 0부터 N까지 구하는 경우..
[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 9095] 1, 2, 3 더하기 - DP(동적 프로그래밍) (C++)
www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #include using namespace std; int arr[12] = {0, 1, 2, 4, }; int T,n; int dp(int n) { if (n > T; for (int i = 0; i > n; cout
[프로그래머스] 3진법 뒤집기 (n진법, bitset) [C++]
programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 기본적인 진법 변환과 비트 연산 문제이다. n진법으로 바꾸고 싶으면 주어진 수를 n으로 나눈 나머지를 차곡차곡 저장해주면 된다. 비트 순서가 역순이니 온전히 변환한 비트를 보고 싶으면 나머지를 스택에 저장한 뒤, 스택에서 pop 해주면 원래 비트 순서로 출력이 될 것이다. 이 문제는 문제 제목처럼 뒤집기이므로 나머지를 스택에 저장..
[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..