재원블로그 재원블로그

이 문제는 dp를 이용한 문제이다. 처음에는 이 문제를 1원부터 10000원까지 루프를 돌리면서 동전을 루프를 돌려 계산하였는데, 이렇게 하면 순서가 뒤바뀐 경우의 수가 모두 포함되게 된다. 순서가 뒤바뀐 경우를 없애려면 코인에 대해서 루프를 돌리고, 그 안에서 금액에 대한 dp 테이블을 갱신해야 한다. 주의해야 할 점은 0원을 만드는 경우의 수가 1이라는 것이다. 애초에 이 값을 0으로 해놓으면 값이 제대로 나오지 않는다. #include #include #include using namespace std; #define MAX 10000 int dp[MAX + 1]; int main() { int n, k; vector coin; cin >> n >> k; for (int i = 0; i < n; i..

이 문제는 dp를 이용해서 푸는 문제이다. dp 배열을 해당 금액을 만들 수 있는 최소의 코인 개수로 설정하면 쉽게 풀 수 있는 문제이다. 시간 제한이 1초이므로, 1억번의 연산만으로 끝내야 한다. for 문마다 최대 100번의 루프가 돌아야 하므로, 탐색할 수 있는 금액의 최대 한도는 1,000,000원이다. 따라서 MAX를 백만으로 설정해서 문제를 풀었다. #include #include using namespace std; #define MAX 1000000 int dp[MAX + 1]; void init() { for (int i = 0; i > n >> k; i..

이 문제는 프로그래머스 level 3 문제이다. 이 문제를 처음에는 백트래킹을 이용해서 풀었으나, 당연히 시간 초과가 났다. dp를 이용해서 푸는 문제임을 알았지만, 방법을 떠올리지 못했다. 이 문제는 dp 배열을 i번째 스티커까지 왔을 때 최댓값으로 생각하면 풀 수 있다. 여기서 중요한 것은 0번째 스티커를 뜯으면 마지막 스티커를 뜯을 수 없고, 1번째 스티커를 뜯으면 마지막 스티커를 뜯을 수 있다는 것이다. 따라서 루프를 두번 돌려 값을 비교한 뒤 최댓값을 출력하면 된다. #include #include #include using namespace std; int dp[100001]; int solution(vector sticker) { int answer = 0; int N = sticker.si..

이 문제는 프로그래머스 level 3 문제이다. 이 문제는 입력이 2억이므로 O(n)으로도 약 2초가 걸린다. 따라서 배열을 사용한 방식으로는 불가능하다. now를 1로 하고, 입력으로 주어진 stations 를 활용해서 문제를 풀어야 한다. 이 생각을 하지 못하면 풀기 힘들 것 같다. #include #include using namespace std; int solution(int n, vector stations, int w) { int answer = 0; int now = 1; int stationIndex = 0; while (now = stations.size() || now < stations[stationIndex] - w) { answer++; now = now + 2 * w + 1; ..

이 문제는 프로그래머스 level 3 문제이다. 나는 처음에 이 문제를 이분 탐색을 통해서 풀려고 했다. 그래서 upper_bound를 이용한 뒤 erase를 하는 방식으로 구현했는데, 이런 식으로는 답은 나오나 시간 초과가 떴다. 내가 생각했을 때에는 vector 내의 erase 함수가 내부적으로 O(n) 이 걸리기 때문에 입력이 100000까지 나오는 경우 O(n^2)은 불가능하기 때문이라고 생각했다. 그래서 다른 풀이를 보니 투 포인터를 이용해서 간단하게 풀 수 있었다. 요즘 문제를 풀다 보면 이분 탐색이 가능한 문제는 보통 투 포인터로도 풀린다는 연관성이 보인다. 물론 입력이 O(n) 으로도 안될 정도로 큰 문제는 이분 탐색밖에 안되겠지만, O(n) 으로도 가능한 입력은 투 포인터도 사용 가능하다..

이 문제는 시뮬레이션과 BFS를 이용한 문제이다. 이 문제는 그렇게 어렵지 않은 문제였으나 두가지 주의해야할 점이 있었다. 첫번째는 solve() 안에서 녹을 얼음을 고르는 로직에서 한번에 A 배열에 결과를 반영하면 다음 반복문에서 그 영향을 받아 연쇄적으로 값이 줄어든다. 그러므로 녹을 얼음을 체크만 해놓고 모든 체크가 끝나면 한꺼번에 1을 감소시켜야 한다. 두번째는 저렇게 로직을 짜도 시간 초과가 떴는데, 이는 로직의 문제가 아니라 cmath 내장 함수 pow를 쓰면 시간 초과가 난다. 직접 만들어서 쓰면 시간 초과가 안 뜬다. 애초에 배열의 크기도 매우 작고, 시간 복잡도를 계산해봐도 절대 1초를 넘기지 않는다. 수학 내장 함수는 조심해서 써야할 것 같다. #include #include #incl..

이 문제는 SQL 고득점 kit에서 join 카테고리에 있는 level 4 문제이다. 어려운 SQL 문제를 풀면서 느끼는 건 처음부터 요구사항을 모두 만족하는 쿼리를 짜려고 하면 문제가 더욱 어렵게 느껴진다는 것이다. 복잡한 join 문제를 풀때는 우선 하나의 테이블 당 요구 조건을 만족하는 단일 쿼리를 짜보고, 그 다음에는 두개의 테이블을 join하는 쿼리를 짜고, 그 다음의 요구사항을 맞추는 방식으로 풀면 결국 풀리게 된다. 이 문제를 처음 제출할 때에는 틀렸습니다가 나왔는데, 아무리 생각해도 논리 구조가 맞아서 혹시 날짜 범위에 문제가 있나 싶어 수정하니 바로 정답이 나왔다. 처음에는 start_date와 end_date가 11월 1일과 11월 30일 사이인 걸 not in 안의 서브쿼리로 넣었는데..

이 문제는 시뮬레이션 문제이고, 최댓값을 구하는 문제이다. 최댓값을 구할 때 브루트 포스로 가능한가 싶었지만, 말이 4개이고 10번의 주사위 결과만 있으므로 아무리 크게 잡아도 4^10 = 1,048,576 이므로 가능하다. 나는 게임판을 보고 그래프와 비슷한 형태라고 떠올렸고, node 구조체를 만들어 게임판의 한 칸을 정의했다. solution 함수 부분은 브루트 포스, 백트래킹으로 모든 경우의 수를 구하는 것인데, 이 때 주의할 점은 말이 현재 칸에서 다음 칸으로 이동하면 현재 칸의 visited는 false로 해주고, 다음 칸의 visited 는 true로 해줘야한다는 것이다. 처음에는 next에 대한 visited만을 신경썼는데, 그런식으로는 정답이 안 나온다. 또한 주의할 점은 재귀 호출이 끝..