기억을 위한 기록들

www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include using namespace std; int n; vector info[100001]; bool checkArr[100001]; int result[100001]; void D(int _n) { for (int i = 0; i < static_cast(info[_n].size()); i++) { int target = info[_n][i]; if (checkArr[target] == false) { checkArr[target] = true;..

www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net #include #include #include #include using namespace std; int main() { int n; int dp[46][2]; cin >> n; memset(dp, 0, sizeof(dp)); dp[0][0] = 0; dp[0][1] = 0; dp[1][0] = 0; dp[1][1] = 1; dp[2][0] = 1; dp[2][1] = 1; dp[3][0] = 1; dp[3][..

www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net #include #include #include using namespace std; int main() { int n; long long dp[91][2] = { {0, 0} //0 ,{0, 1} //1 ,{1, 0} //2 }; cin >> n; for (int i = 3; i

www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net #include #include #include using namespace std; int main() { long long n; cin >> n; long long dp[91]; dp[0] = 0; dp[1] = 1; dp[2] = 1; dp[3] = 2; for (int i = 4; i

acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net #include #include #include using namespace std; int main() { int n = 0; cin >> n; vector info[500]; int dp[500][500]; int input; for (int i = 0; i > input; info[i].push_back(input); } } dp[0][0] = info[0][0]; int result = dp[..

1. malloc은 라이브러리 제공함수로 함수 콜을 요청한다. new는 C++언어에서 제공하는 기본 키워드로, 별도의 라이브러리 추가 없이 바로 사용가능 2. malloc은 사이즈를 매개변수로 받고, 리턴타입이 void* 형 이므로 캐스트 연산자의 도움을 받아야한다. new는 할당할 타입을 지정하면, 알아서 할당할 타입의 포인터로 넘어온다. 그래서 할당할 타입의 포인터 변수로 받아오면 된다. 3. malloc은 메모리를 동적으로 할당하는 것만이 목적이라 초기값 지정 불가능. new는 할당과 동시에 초기화 가능 4. new키워드는 생성자를 자동으로 호출. 생성자는 객체를 자동으로 초기화 해주는 함수로, malloc과 new의 가장 큰 차이점이다. * new가 좋아보이긴하지만 malloc의 경우 reallo..

www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net #include #include #include using namespace std; #define MAX 301 int DP[MAX]; int stair[MAX]; int main() { int n = 0;; cin >> n; for (int i = 0; i > stair[i]; DP[0] = stair[0]; DP[1] = max(stair[1], stair[0] + stair[1]); DP[..

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net #include #include #include #include #include using namespace std; int map[100][100]; int visited[100][100]; int cnt = 0; int dir[4][2] = { {0,-1}, {1,0}, {0,1}, {-1,0} }; int main() { int n; cin >> n; int high = 1; int input; for (int ..

www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net #include #include #include #include #include using namespace std; #define MAXSIZE 50 int map[MAXSIZE][MAXSIZE]; bool visited[MAXSIZE][MAXSIZE]; int dir[8][2] = { {-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,1}, {1,-1}, {1,0}, {1,1} }; in..

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #include #include using namespace std; int dp[3][1000]; int rgb[3][1000]; int main() { int n; //집 갯수 cin >> n; for (int index = 0; index > rgb[0][index]; //R값 cin >> rgb[1][index]; //G값 cin >> rgb[2..

www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net #include #include using namespace std; int dp[1001]; int find(int n) { if (n == 1) return 1; if (n == 2) return 2; const int DIVIDE = 10007; for (int i = 3; i > n; cout

www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #include #include using namespace std; int dp[12]; int find(int n) { if (n == 1) return 1; if (n == 2) return 2; if (n == 3) return 4; int& target = dp[n]; if (target != -1) { return target; } return target = find(n - 1) + find(n - 2) + find(n - 3); } int main() { int testCase; cin >> t..