분류 전체보기
BaekJoon 11659번: 구간 합 구하기 4
풀이법 arr 배열이 100,000까지 있기에 시간 초과를 방지하기 위해서는 DP를 사용해야 한다. 입력과 동시에 모든 배열의 합을 구해서 합의 배열을 만들어두고 arr[j] - arr[i-1]을 이용하면 쉽게 풀 수 있는 문제이다. #include #include #include using namespace std; int n, m; int arr[100001]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; arr[0] = 0; int temp = 0; for (int i = 1; i > a; temp += a; arr[i] = temp; } vector ans; for (int k = 1; k > i >> j; ans.pu..
BaekJoon 1912번: 연속합
풀이법 1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 메모이제이션을 활용하여 현재까지의 최대 합을 구하고 이를 ret이라는 변수에 담아 최대를 반환하게 했다. max(직전까지 최대 합+ 현재 값, 현재 값) #include #include using namespace std; int n; int c[100001]; int d[100001]; int res = -100000000; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i > a; c[i] = a; } d[0] = c[0]; for (int i = 1; i < n; i++) { d[i] ..
BaekJoon 11726번: 2xn 타일링
풀이법 1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 방법만 안다면 쉽게 풀 수 있는 문제이나 정답률이 낮은 이유는 여러 번 시도한 사람이 많아서일 것이다. 1차원 배열을 선언 한 후 규칙을 찾아 보았다. n=1 : 1개 n=2 : 2개 n=3 : 3개 n=4 : 5개 위의 요소를 토대로 규칙을 찾아보니 일종의 계차수열임을 알 수 있었다. 점화식을 구해보니 arr[i]=arr[i-1]+arr[i-2]를 도출할 수 있었다. 10007로 나눈 나머지를 구해야 하므로 최종 점화식은 arr[i] = arr[i-1]%10007 + arr[i-2]%10007 이 된다. 최총 출력 값: arr[n]%10007 #include #include using namespace std; int fix ..
BaekJoon 1149번: RGB거리
풀이법 1) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 단순한 1차원 배열로는 해당 문제에 대한 점화식을 도출하는 것이 쉽지 않을 것이라 생각한다. 나올 수 있는 경우의 수를 구현하되 DP의 메모이제이션을 활용하여 시간 제한인 0.5초의 벽을 뚫는 것이 핵심이다. arr[i][0] : i번째 집을 빨간색으로 칠하는 비용 arr[i][1] : i번째 집을 초록색으로 칠하는 비용 arr[i][2] : i번째 집을 파란색으로 칠하는 비용 ans[i][0] : i번째 집을 빨간색으로 칠했을 때까지의 최소비용 ans[i][1] : i번째 집을 초록색으로 칠했을 때까지의 최소비용 ans[i][2] : i번째 집을 파란색으로 칠했을 때까지의 최소비용 해당 배열을 이용하여 재귀 식을 만들면 다음과..
SQLD 합격 후기
제 40회 SQL 개발자(SQLD) 시험에 합격했다. 가채점 했을 때 아슬아슬하다고 생각했는데 생각보다 점수가 잘 나와서 놀랬다. 시험 준비기간은 약 2주였으나 공부 시간은 하루 2시간 정도로 많지 않았다. 학기 초였기에 학교 공부와 병행하면서 할 수 있었다. 유사전공자기에 DB관련 수업은 들어본 적이 있으나, 큰 도움이 되었다고 생각하지는 않는다. 오히려 웹사이트를 만들면서 DB를 건드려 본 것이 더 큰 도움이 되었다고 말할 수 있다. 추후 이 글을 읽는 SQLD 합격자들에게 짧은 시간에 SQLD를 합격할 수 있는 팁 정도를 남기고자 한다. ※ 책에 대해서는 어떠한 홍보도 받지 않았으며, 주관적 기준으로 작성한 리뷰입니다. 1. 비전공자 / 유사전공자 합격을 간절하게 원한다면 많이들 사용하는 SQL 전..
Programmers_SQL Select 1:모든 레코드 조회하기
SELECT * FROM ANIMAL_INS ORDER BY ANIMAL_ID 풀이법 1) SELECT 문에 ORDER BY를 이용해서 정렬하면 문제를 쉽게 풀 수 있다. (ASC : 생략 가능하며 오름차순 / DESC :내림차순)
데이터구조와알고리즘 과제_회문
풀이법 1) 재귀를 통해 맨 끝과 맨 앞을 비교하며 회문인지 판단한다. #include #include using namespace std; int is_panlindrome(string input_str) { if (input_str.size()0) { cout
데이터구조와알고리즘 과제_후위연산식(Stack)
학교 교과목인 데이터구조와알고리즘 과제로 Stack을 이용하여 중위 연산식을 후위 연산식으로 구현해 보았다. 풀이법 1) Class에 stack에서 필요한 isEmpty size clear peek(top) push pop 함수를 정의한다. 2) 결과 값을 반환할 char 배열을 만들어 둔다 3) '(' 의경우 Stack에 바로 넣어 준다. 4) '*' 나 '/'이 새로운 값으로 들어오는 경우 기존 stack에서 '*'나 '/'가 나올때 까지 계속 pop 해준 후 값을 넣는다. 5) '+'나 '-'가 새로운 값으로 들어오는 경우 기존 stack에서 '('이 나올때 까지 계속 pop 해준 후 값을 넣는다. 6) ')'이 새로운 값으로 들어 오는 경우 기존 stack에서 '('이 나올 때까지 계속 pop 해..
데이터구조와알고리즘 과제_Polynomial 구현
학교 교과목인 데이터구조와알고리즘 과제로 다항식의 계산을 구현해보았다. 풀이법 1) Class를 주어진 조건에 맞게 정의하고 vector를 이용한다면 쉽게 구현 가능하다. #include #include #include #include using namespace std; class polynomial { public: vector coef; polynomial(vectorcoef) { this->coef = coef; } int degree(); int evaluate(int scalar); polynomial add(polynomial expr); polynomial substract(polynomial expr); void display(); }; int polynomial::degree() { i..
BaekJoon 2579번: 계단 오르기
풀이법 1) n의 수가 작다면 Backtracking으로 풀 수 있는 문제이지만 현재 n이 300까지 나올 수 있기에 DP로 푸는 것이 좋다. 2) 점화식을 구현한다면 누구나 쉽게 풀 수 있는 문제라고 생각한다. 단순한 1차원 배열로는 해당 문제에 대한 점화식을 도출하는 것이 쉽지 않을 것이라 생각한다. 해당 값이 연속된 계단인지 아닌지를 확인할 수 있는 점화식을 도출하는 것이 핵심이다. arr[i] : i번째 계단에 대한 입력 값 ans[i][0] : i 번째 계단을 밟았지만 연속된 계단이 아닐 때 ans[i][1] : i 번째 계단을 밟았는데 연속된 계단일 때 ans[i][0] = max(ans[i - 2][0], ans[i - 2][1]) + arr[i]; ans[i][1] = ans[i - 1][..