[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include "Q5.h"
template<typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec)
{
os << "[";
for (size_t i = 0; i < vec.size(); i++)
{
os << vec[i];
if (i != vec.size() - 1)
{
os << ", ";
}
}
os << "]";
return os;
}
|
cs |
|
|
// main에서 vector 형태로 출력하기위한 기본 셋팅
|
Q 5.20 파스칼 삼각형에서 행 계산하기
음이 아닌 정수 n이 주어졌을 때 파스칼의 삼각형에 해당하는 첫n개의 행을 출력하는 프로그램을 작성하라.
단순하게 파스칼 삼각형을 왼쪽으로 정렬하고, 첫번째 엔트리의 위치를 0으로 설정하자.
이제 j가 0 혹은 i라면 i번째 행의 j번째 엔트리는 1이 되며,
나머지 엔트리는 i-1번째 행에서 j-1번째와 j번째 엔트리의 합이 되도록 하면된다.
위 내용의 소스코드와 결과는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 5.20 파스칼의 삼각형에서 행 계산하기
#include<vector> std::vector<std::vector<int>> GeneratePascalTriangle(int num_rows)
{
std::vector<std::vector<int>>pascal_triangle;
for (int i = 0; i < num_rows; i++)
{
std::vector<int>curr_row;
for (int j = 0; j <= i; j++)
{
curr_row.emplace_back(0<j && j<i ? pascal_triangle.back()[j-1]+
pascal_triangle.back()[j] : 1);
}
pascal_triangle.emplace_back(curr_row);
}
return pascal_triangle;
}
|
cs |
시간복잡도와 공간복잡도 모두 O(n2)를 가지게 된다.
|
1
|
// main
std::cout << "5-20 " << GeneratePascalTriangle(10) << std::endl;// 5-20 |
cs |
'C++ 학습 > C++ 코딩인터뷰[5장]' 카테고리의 다른 글
| [5. 배열] 5.19 2차원 배열 회전하기 (0) | 2025.01.23 |
|---|---|
| [5. 배열] 5.18 2차원 배열에 나선형으로 원소 배치하기 (0) | 2025.01.22 |
| [5. 배열] 5.17 스도쿠 체크 (0) | 2025.01.22 |
| [5. 배열] 5.16 균등하지 않은 임의의 숫자 생성하기 (0) | 2025.01.22 |
| [5. 배열] 5.15 임의의 부분 집합 만들기 (0) | 2025.01.15 |
