목록분류 전체보기 (259)
차근차근
0. 제목 백준 2193 이친수 BOJ 2193 이친수 C++ 2193 이친수 1. 문제 https://www.acmicpc.net/problem/2193 2. 풀이 DP 방식을 이용하였다. dp[i][0]은 i 단계에서 0일때, dp[i][1]은 i 단계에서 1일때의 이친수 개수를 뜻한다. 이친수의 규칙에 의하면 1은 연속으로 나올수 없고, 0은 처음에 나올수 없다. 1단계에서의 dp[1][0], dp[1][1]은 각각 0, 1 로 초기화한다. i 단계에서 0일때, i-1 단계에서는 0, 1 둘다 올 수 있다. 따라서, dp[i-1][0] + dp[i-1][1]의 값과 같다. i 단계에서 1일때, i-1 단계에서는 0만 올 수 있다. 따라서, dp[i-1][0]의 값과 같다. N단계에서 이친수의 개수는..
0. 제목 백준 11057 오르막 수 BOJ 11057 오르막 수 C++ 11057 오르막 수 1. 문제 https://www.acmicpc.net/problem/11057 2. 풀이 DP 방식을 이용하였다. dp[i][j]는 i단계에서 값이 j일때 오르막 수의 개수를 의미한다. 먼저 처음에 1자리 수일 경우에 대한 초기화를 한다. 즉, 1단계일때 오르막 수는 1개씩(0~9) 뿐이다. 예를 들어, 5단계에서 값이 7일때 오르막 수의 개수를 구하고 싶다면 5단계의 6일때 오르막 수의 개수와 4단계의 7일때 오르막 수의 개수를 합하면 된다. 다음과 같이 써보니 규칙 찾기가 수월하였다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..
0. 제목 백준 10844 쉬운 계단 수 BOJ 10844 쉬운 계단 수 C++ 10844 쉬운 계단 수 1. 문제 https://www.acmicpc.net/problem/10844 2. 풀이 DP 방식을 이용하였다. dp[i][j]는 i단계에서 값이 j일때 계단 수의 개수를 의미한다. 계단 수란 인접한 모든 자리수의 차이가 1이 나는 수이다. 만약 5단계에서 6일때의 계단수를 알고 싶다면 4단계에서 5일때의 계단 수와 4단계에서 7일때의 계단 수를 합하면 된다. 주의해야할 점이 있는데, 마지막 수가 0, 9일때는 그 전단계의 수가 각각, 1, 8일때만 가능하다. 마지막에 답을 구하기 위해서는 N단계에서의 0일때부터 9일때까지의 계단 수들을 더하면 된다. 3. 코드 1 2 3 4 5 6 7 8 9 10..
0. 제목 백준 9095 1,2,3 더하기 BOJ 9095 1,2,3 더하기 C++ 1,2,3 더하기 1. 문제 https://www.acmicpc.net/problem/9095 2. 풀이 DP 방식을 이용하였다. 초기값 3개(dp[1], dp[2], dp[3])를 먼저 설정하였다. 1, 2, 3 을 이용하여 어떻게 기존의 값을 재사용할 수 있을까 dp[8]을 예로 들어보면 1을 사용했을때 dp[7], 2를 사용했을때 dp[6], 3을 사용했을때 dp[5], 이 값들을 더하면 된다. dp[i] = dp[i-1] + dp[i-2] + dp[i-3] 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using namespace std;..
0. 제목 백준 11726 2xn 타일링 2 BOJ 11726 2xn 타일링 2 C++ 2xn 타일링 2 1. 문제 https://www.acmicpc.net/problem/11727 2. 풀이 DP 방식을 이용하였다. 초기값 2개(dp[1], dp[2])를 먼저 설정하고 가로의 길이가 1씩 증가할 때 어떻게 변할지 생각해보았다. 가로의 길이가 1 증가했을 때 dp[i]라고 놓으면 1칸이 남았을때 채우는 방법 dp[i-1] 과 2칸이 남았을때 채우는 방법(2x2타일로 채우는 방법, 1x2타일 2개로 채우는 방법) 2xdp[i-2] 의 합으로 구할 수 있다. 따라서, dp[i] = dp[i-1] + 2*dp[i-2] 로 정리할 수 있다. 반복문을 다 돌고 10007로 나누려면 수가 너무 커지기 때문에 dp..
0. 계기 지금껏 한 프로젝트에서는 서버를 다룬적이 없어서 서버에 대한 개념이 부족하였다. 또한 AWS를 공부해보고 싶었고 서버부터 클라이언트까지 개발해보고 싶었다. 서버, 웹, 안드로이드, 크롤링에 대한 지식을 얻을 수 있을 것같다. 학식앱을 만들고 앱스토어에 올리는 것까지가 이 프로젝트의 목표이다. 1. 계획 [Client ---> Server] Http Request [Server --> Database] SQL Query [Database --> Server] Data [Server --> Client] Http Response(JSON) 중간중간 필요한 것이 달라질 수 있지만 사용할 것들을 살짝 정해보자면 다음과 같다. 이렇게 방식을 미리 정해놓고 하는 것보다 다양한 방법(더 좋은 효율을 가질수..
0. 제목 백준 11726 2xn 타일링 BOJ 11726 2xn 타일링 C++ 2xn 타일링 1. 문제 https://www.acmicpc.net/problem/11726 2. 풀이 DP 방식을 이용하였다. 초기값 2개(dp[1], dp[2])를 먼저 설정하고 가로의 길이가 1씩 증가할 때 어떻게 변할지 생각해보았다. 가로의 길이가 1 증가했을 때의 답은 마지막에 세로로 타일 한개를 놓는 방법(dp[i-1])과 마지막전까지 해서 가로로 타일 두개를 놓는 방법(dp[i-2])를 합한 값이 방법의 수가 된다. 반복문을 다 돌고 10007로 나누려면 수가 너무 커지기 때문에 dp[i]를 구할때 마다 10007로 나눈 나머지를 구해준다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..
0. 제목 백준 1463 1로 만들기 BOJ 1463 1로 만들기 C++ 1로 만들기 1. 문제 https://www.acmicpc.net/problem/1463 2. 풀이 DP 방식을 이용하였다. Top-down방식과 Bottom-up방식 중에 Top-down방식을 사용하였다. Top-down방식을 이용할 땐 dp 배열을 10^6 보다 큰 수로 채워놓으면 된다. 먼저 초기값을 설정한 후, dp[i] = 1 + dp[i-1], dp[i] = min(dp[i], 1 + dp[i/3]), dp[i] = min(dp[i], 1 + dp[i/2]) 와 같은 방법으로 연산횟수의 최솟값을 구한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #inclu..