전체 글 226

다이나믹 프로그래밍 - 기초

다이나믹 프로그래밍에 대해서 알아봅시다. 기초 단계에서 다이나믹 프로그래밍은 브루트 포스(완전탐색법)으로 구현하였을때 너무 오래걸리는 문제를 풀기위하여 이전에 구한 답을 기억하였다가 활용하는 것을 뜻합니다. (메모이제이션) 일단 문제와 함께 이해해 봅시다. https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 요약을 하자면 N을 나누기 3을 하던 N / 2를 하던 N - 1 해서 1로 만들어야 합니다. 1로 만들 때의 최소 계산 횟수가 몇 번인가를 구해야 합니다. 푸는 방법을 생각해 보면 처음에는 'N을 최대한 작게 만들기 위해서는 N / 3, N / 2, ..

[C/C++] 백준 1463번 - 1로 만들기, 다이나믹 프로그래밍(동적계획법)

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 완성된 코드: #include #include // min을 쓰기 위한 헤더 파일#define fastio() ios::sync_with_stdio(0),cin.tie(0); // 빠른 입출력을 위한 코드#define INF 100000000using namespace std;int dp[1111111]; // 이전에 나온 값을 기억할 배열, 전역변수 이므로 0으로 초기화 되어있다.int solve(int n, int cnt) { if (n == 1) return cnt; // n이 1이 된다면 cnt를 리턴한..

SQL/MySQL의 기초 - WHERE, SubQuery

https://leetcode.com/problems/second-highest-salary/ Second Highest Salary - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제를 해석 하자면 두 번째로 높은 임금을 구하여라. 그러나 두 번째 높은 값이 없을 경우에는 null을 출력하라라는 뜻입니다. 그러나 문제를 풀 것은 아니고, 이 문제로 WHERE과 SubQuery를 배워봅시다. 일단 아래의 코드가 위에 링크 문제의 답입니다. SELECT MAX..

[C/C++] 백준 14500번 - 테트로미노, 삼성 코딩 테스트 문제를 두 가지 방법으로 풀어보자

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 매우 간단한 문제입니다. 1. 문제요약 테트로미노를 놓아서 나올 수 있는 최대값을 구하자 2. 생각의 흐름 그냥 다 하면 되겠는데? 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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43..