profile
꾸준히 성장하는 백엔드개발자
post-thumbnail

[백준/C++]12865번_평범한 배낭

문제는 다음과 같습니다.먼저 배낭 문제는 크게 두 개로 나뉩니다.이 문제는 두 번째에 해당하는 문제입니다.0-1 배낭 문제를 해결하기 위해서는 동적 계획법을 이용합니다.2차원 배열 dp에 문제 예시를 직접 진행해보면 다음과 같습니다.점화식의 규칙은 다음과 같습니다.먼저

2022년 6월 20일
·
0개의 댓글
·
post-thumbnail

[백준/C++]2579번_계단 오르기

문제는 다음과 같습니다.그나마 좀 생각해 볼 만한 지점이 있었던 DP문제입니다.저기 밑줄 친 "연속된 세 개의 계단을 모두 밟아서는 안된다" 조건이 재밌는 것 같습니다.먼저 배열 두개가 필요합니다.배열 a는 계단의 점수를 입력받습니다.배열 dp는 정답을 구하기 위한 배

2022년 4월 27일
·
0개의 댓글
·
post-thumbnail

[백준/C++]9461번_파도반 수열

문제는 다음과 같습니다.나선에서 가장 긴 변의 길이가 N일 때, 그 변에 길이가 K인 삼각형을 추가하며 도형을 계속 이어붙여갑니다.도형을 잘 살펴보면,기본 1~5까지가 초기 조건이고6번째부터는 (정삼각형의 한 변의 길이) = (바로 이전 항 삼각형) + (5번째 이전

2022년 4월 27일
·
0개의 댓글
·
post-thumbnail

[백준/C++]1904번_01타일

문제는 다음과 같습니다.만들어서 붙일 수 있는 타일은 00, 1 총 두 가지 종류입니다.바로 n번째 상황에 대해서 생각을 해보면,n번째 상황에 대해서, 타일은 마지막이"00 으로 끝나거나" 또는 "1 로 끝나는 경우" 두 가지 입니다.00 으로 끝나는 경우 만들 수 있

2022년 4월 27일
·
0개의 댓글
·
post-thumbnail

[백준/C++]1003번_피보나치 함수

문제는 다음과 같습니다.드디어 중간고사가 끝났습니다! (사실 어제^^)이제 조금 맘놓고 백준을 풀 수 있어서 행복함니다 ㅠㅠㅠㅠ첫 DP 문제는 간단합니다!0과 1의 초기 조건이 주어져 있고,간단히 다이나믹 프로그래밍의 bottom-up 방식을 이용하면 됩니다.2차원 배

2022년 4월 27일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 2156번_포도주 시식

문제는 다음과 같습니다.저는 먼저 배열 an와 2차원 배열 dpn를 이용하였습니다.배열 an에는 n번째 포도주의 양을 넣었고,핵심인 배열은 dpn 입니다.그래서 n번째까지 왔을 때, 최대는 max(dpn, dpn)이 됩니다.그리고 각각의 dpn, dpn을 구하는 과정은

2022년 2월 11일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 9495번_스티커

문제는 다음과 같습니다.두 개의 배열이 있는데,먼저 배열 a에는 입력받는 배열을 넣었습니다.ai는 그대로 i행, j열에 있는 항을 의미합니다.그리고 문제를 풀기 위한 핵심인 dp배열은 다음과 같습니다.그리고 N번째 열에서 dpN는 i=0, 1, 2 총 세 가지 경우의

2022년 2월 10일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 1309번_동물원

문제는 다음과 같습니다.일단 문제가 너무 귀엽습니다동물원이라니🐶🙊🐯🐻🐰일단 저는 바로 N번째 상황에 대해 가정하고 바로 점화식으로 접근하였습니다.N번째 상황에서 경우의 수는 3가지입니다.앞의 두 칸이 모두 비어있는 경우앞에서 왼쪽만 차있는 경우앞에서 오른쪽만

2022년 2월 9일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 11057번_오르막 수

문제는 다음과 같습니다.제가 푼 과정은 다음과 같습니다.먼저, 2차원 배열 dpidx을 이용했고,idx: 숫자의 자릿수를 의미함num: 자릿수에 해당하는 수를 의미함789이라는 수를 예로 들면,7-> idx:1, num:78-> idx:2, num:89-> idx:3,

2022년 2월 9일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 10844번_쉬운 계단 수

문제는 다음과 같습니다.일단 이 문제 푸는데 삼일? 걸렸던 것 같다.계속 분명히 맞는데 왜 틀렸지? 이랬는데, 알고보니 마지막 답으로 써서 낸 자료형이 달라서..실환가 long long인데 계속 int로 반환해서 .. 드디어 계속 틀렸던 이유 찾았다.나름 꼼꼼하다고 생

2022년 2월 8일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 2225번_합분해

문제는 다음과 같습니다.점화식을 세우는 데까지 가 어려운 문제인 것 같습니다. ㅠㅠdp문제이고 점화식을 세워야하는 걸 아니까 점화식을 어떻게든 세우게 되네요,,먼저 저는 dpn 인 2차원 벡터를 이용했습니다.이때 이 의미는,계단문제나, 어떤 dp문제이든 일반적인 i번째

2022년 2월 3일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 1699번_제곱수의 합

문제는 다음과 같습니다.일단, 여러번 시도했지만 실패했던 문제입니다.틀린것도 나중에 힌트를 얻고나서 왜 틀렸는지 알게되었습니다. ㅋㅋㅋㅋ분명 쉬워보였는데.. 틀렸습니다🥺제가 푼 풀이는 다음과 같습니다.제가 풀었던 풀이 방식은 다음과 같습니다.먼저, 뺄 수 있는 최대의

2022년 2월 2일
·
0개의 댓글
·
post-thumbnail

[Leetcode/C++] 121_Best Time to Buy and Sell Stock

문제는 다음과 같습니다.이번 스터디 문항중 하나가 이 문제의 업그레이드 버전이더라구요? best time to buy and sell stock2 였나 그런데 작년에 이 문제를 풀었던 기억 이 있어서 복습차원에서 다시 한 번 풀어보았습니다.제가 생각한 이 문제의 조건은

2022년 2월 2일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 15990번_1,2,3 더하기 5

문제는 다음과 같습니다.

2022년 1월 30일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 15988번_1, 2, 3 더하기 3

문제는 다음과 같습니다.문제가 간단하니까 제가 푼 방법을 간단하게 설명하자면,저는 정수 n을 1, 2, 3 의 합으로 나타내는 방법을 배열 an에 저장하였고,이를 bottom-up 방법으로 풀었습니다.전체 코드는 다음과 같습니다.

2022년 1월 30일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 14002번_가장 긴 증가하는 부분 수열 4

문제는 다음과 같습니다.가장 긴 증가하는 부분 수열 문제와 동일한데, 차이점은 이 수열이 무엇인지까지 저장해야한다는 것입니다.제가 가장 먼저 풀었던 풀이 방법은 다음과 같습니다.이 전에는 i까지의 최대 증가 부분 수열의 길이를 벡터에 저장했더라면,이번에는 벡터 배열을

2022년 1월 30일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 1932번_정수 삼각형

문제는 다음과 같습니다.전형적인 DP문제이구요,제가 생각한 핵심은 삼각형의 맨 위에서 한줄 한줄 내려갈때마다그 줄에서의 최댓값을 계속해서 갱신해나가면 됩니다.이때 최댓값을 구할 때 경우가 두 가지로 나뉩니다.즉 아래와 같은 경우입니다.이때에는 최댓값을 구할 필요 없이

2022년 1월 28일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 11054번_가장 긴 바이토닉 부분 수열

문제는 다음과 같습니다.이 문제는 제가 바이토닉 수열을 제대로 이해하지 않은 채 풀어서 처음에 삽질을 좀 했습니다..⚒️항상 문제 제대로 읽기!⚒️바이토닉 수열이란,수열이 증가했다가 감소하는 수열을 의미합니다.저는 증가와 감소를 연속해서 반복하는 수열이라 생각하고 풀다

2022년 1월 28일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 11722번_가장 긴 감소하는 부분 수열

문제는 다음과 같습니다.앞 문제의 증가하는 수열과 원리가 같습니다.i번째 배열을 포함했을 때의 최대 감소 수열의 길이를 벡터 cnt에 담았습니다.그래서 i번째의 cnt는 변수 j가 0부터 i-1까지 돌면서 최대의 cnt를 구하되,이때의 전제조건은 감소수열이므로, aj

2022년 1월 28일
·
0개의 댓글
·
post-thumbnail

[백준/C++] 11055번_가장 큰 증가 부분 수열

문제는 다음과 같습니다.일단 백준 너무 오랜만입니다,,저번주까지 해커톤 준비하느라 막판에 에러가 터져서 에러해결하느라백준 일주일만에 풀게 되었습니다.다시 정신차리고 하루에 한문제 이상씩 꼭 풀겠습니다!계속 이어서 DP입니다.앞 문제 중에서도 이와 비슷한 문제가 많았구요

2022년 1월 28일
·
0개의 댓글
·