전체 글
BOJ 11057 · 오르막 수
알고리즘 분류 : 다이나믹 프로그래밍 오르막 수를 DP로 구현하는 문제다. 오르막 수란 각 자리의 수가 오름차순을 이루는 숫자를 말한다. 0으로 시작할 수 있으며, 인접한 자리의 숫자가 같아도 오르막 수이다. D[N][M] : M으로 끝나는 N자리 오르막 수D[1][0] = 1, D[1][1] = 1, ‥‥ , D[1][9] = 1D[N][0] = D[N-1][0] : 0으로 끝나는 N자리 오르막 수D[N][1] = D[N-1][0] + D[N-1][1]D[N][2] = D[N-1][0] + D[N-1][1] + D[N-1][2]‥‥D[N][9] = D[N-1][0] + D[N-1][1] + ‥‥ + D[N-1][9] C++ 소스코드 #include int n, ans; int d[1001][10]; c..
삼성 SW 역량 테스트 문제 리스트
+ 삼성 소프트웨어 역량 테스트란? 삼성(삼성전자, 삼성 SDS 등) 채용 단계에서 S직군이 보는 오프라인 코딩 테스트(직무적성검사)이다.SW 개발 직무에 지원한다면, GSAT 대신 소프트웨어 역량테스트를 봐야 한다. + SW 역량테스트 준비 프로그래밍 언어를 익힌다. C/C++, Java, Python3 중 (C++ 추천)자료구조(큐, 스택, 덱, 그래프 등)와 알고리즘 이론(DFS, BFS, 힙, 백트래킹 등)을 배운다.알고리즘 스킬(재귀 구현, 비트 연산, STL 사용법 등)을 익힌다.백준 온라인 저지와 SW Expert Academy에서 알고리즘 문제를 풀면서 연습한다.역대 기출은 시뮬레이션, BFS, DFS, 브루트 포스 등의 문제로 출제되었으므로, 이러한 유형을 집중적으로 푼다.SWEA에서 모..
BOJ 16194 · 카드 구매하기 2
알고리즘 분류 : 다이나믹 프로그래밍 DP를 통해 카드를 구매하기 위해 지불하는 금액의 최솟값을 구해야 한다. BOJ 11052번 '카드 구매하기'에서 최댓값 대신 최솟값을 구하면 된다. D[N] : 카드 N장을 구입하기 위한, 지불 금액의 최솟값D[0] = 0, D[1] = P[1]D[N-1] + P[1] : 카드 1개 들어있는 카드팩을 구매하고, 카드 N-1장을 구매한 지불 금액의 최솟값D[N-2] + P[2]‥‥D[0] + P[N] : 카드 N개 들어있는 카드팩을 구매하고, 카드 0장을 구매한 지불 금액의 최솟값 C++ 소스코드 #include #include using namespace std; int n, d[1001], p[1001]; void solve() { d[0] = 0, d[1] = ..
BOJ 11052 · 카드 구매하기
알고리즘 분류 : 다이나믹 프로그래밍 DP를 통해 카드를 구매하기 위해 지불하는 금액의 최댓값을 구해야 한다. D[N] : 카드 N장을 구입하기 위한, 지불 금액의 최댓값D[0] = 0, D[1] = P[1]D[N-1] + P[1] : 카드 1개 들어있는 카드팩을 구매하고, 카드 N-1장을 구매한 지불 금액의 최댓값D[N-2] + P[2]‥‥D[0] + P[N] : 카드 N개 들어있는 카드팩을 구매하고, 카드 0장을 구매한 지불 금액의 최댓값 C++ 소스코드 #include #include using namespace std; int n, d[1001], p[1001]; void solve() { d[0] = 0, d[1] = p[1]; for (int i=2; i
BOJ 10844 · 쉬운 계단 수
알고리즘 분류 : 다이나믹 프로그래밍 DP를 통해 계단 수의 총개수를 구하는 문제다. D[N][M] : M으로 끝나는 N자리 계단 수의 총개수D[1][1] = 1, D[1][2] = 1, ‥‥ , D[1][9] = 1 (한 자릿수)D[N][0] = D[N-1][1] : 0으로 끝나는 N자리 계단 수의 총개수D[N][1] = D[N-1][0] + D[N-1][2] : 1로 끝나는 N자리 계단 수의 총개수‥‥D[N][8] = D[N-1][7] + D[N-1][9]D[N][9] = D[N-1][8] C++ 소스코드 #include const int mod = 1000000000; int n; long long ans, d[101][10]; void solve() { for (int i=1; i 0: d[i][..
BOJ 15988 · 1, 2, 3 더하기 3
알고리즘 분류 : 다이나믹 프로그래밍 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 한다. BOJ 9095번 '1, 2, 3 더하기'에서 범위가 확장된 문제다. D[N] : 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수D[1] = 1D[2] = 2 (1+1, 2)D[3] = 4 (1+1+1, 1+2, 2+1, 3)D[N-1] : 마지막에 1을 더한 방법의 수D[N-2] : 마지막에 2를 더한 방법의 수D[N-3] : 마지막에 3을 더한 방법의 수 C++ 소스코드 #include int n; long long d[1000001]; void solve() { d[1] = 1, d[2] = 2, d[3] = 4; for (int i=4; i
BOJ 9095 · 1, 2, 3 더하기
알고리즘 분류 : 다이나믹 프로그래밍 기초적인 DP 문제이다. 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 한다. D[N] : 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수D[1] = 1D[2] = 2 (1+1, 2)D[3] = 4 (1+1+1, 1+2, 2+1, 3)D[N-1] : 마지막에 1을 더한 방법의 수D[N-2] : 마지막에 2를 더한 방법의 수D[N-3] : 마지막에 3을 더한 방법의 수 C++ 소스코드 #include int n, d[11]; void solve() { d[1] = 1, d[2] = 2, d[3] = 4; for (int i=4; i
BOJ 11727 · 2×n 타일링 2
알고리즘 분류 : 다이나믹 프로그래밍 기초적인 DP 문제이다. BOJ 11726번 '2×n 타일링'에서 살짝 변경해주면 된다.D[N] : 2xN 사이즈의 직사각형을 2x2, 2x1 사각형으로 채우는 방법의 수D[0] = D[1] = 1D[N-1] : 마지막 조각을 2x1 사각형으로 채운 방법의 수D[N-2] : 마지막 조각을 2x2 사각형 또는 2x1 사각형 2개로 채운 방법의 수 C++ 소스코드 #include int d[1001]; int solve(int n) { d[0] = d[1] = 1; for (int i=2; i