본문 바로가기

DP5

99클럽 코테스터디 42일차 TIL 프로그래머스- 코딩테스트 공부 코딩 테스트 공부프로그래머스 Level 3 2022 KAKAO TECH INTERSHIP문제 링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명당신은 코딩 테스트를 준비하기 위해 공부하려고 합니다. 코딩 테스트 문제를 풀기 위해서는 알고리즘에 대한 지식과 코드를 구현하는 능력이 필요합니다.알고리즘에 대한 지식은 알고력, 코드를 구현하는 능력은 코딩력이라고 표현합니다. 알고력과 코딩력은 0 이상의 정수로 표현됩니다.문제를 풀기 위해서는 문제가 요구하는 일정 이상의 알고력과 코딩력이 필요합니다.예를 들어, 당신의 현재 알고력이 15, 코딩력이 10이라.. 2024. 9. 1.
99클럽 코테스터디 41일차 TIL 프로그래머스- 도둑질 도둑질프로그래머스 Level 4 DP문제링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명원형의 형태로 집들이 위치해 있고, 연속된 두 집을 방문하지 않으면서 최대로 가질 수 있는 값을 구하는 문제문제 풀이Buttom-up 방식으로 풀이했다.첫번째 집을 방문하냐 안하냐로 두개의 dp 로 나눠 진행했다.코드#include #include #include using namespace std;int dp1[1000000 + 30];int dp2[1000000 + 30];int solution(vector money){ int answer = 0; .. 2024. 8. 31.
99클럽 코테스터디 40일차 TIL 프로그래머스- 등굣길 등굣길프로그래머스 Level 3 DP문제 링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명배열이 주어지고, 시작점은 1,1 끝점은 n,m 일 때중간에 갈 수 없는 지점이 있고,시작점으로부터 끝점까지 도달할 수 있는 최단 경로의 갯수를 구하면 되는 문제문제 풀이Buttom-Up 방식으로 풀이했다.puddles 에 주어지는 부분들은 미리 -1로 처리했고해당 부분을 만나면 0으로 처리해주며 진행했다.코드#include #include #include using namespace std;int dp[101][101];int solution(int m, .. 2024. 8. 30.
99클럽 코테스터디 22일차 TIL Maximal Rectangle Maximal RectangleLeetCode Hard DP문제 설명Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. 문제 풀이문제 설명을 보면 굉장히 간단하다. 주어진 배열에서 가장 큰 직사각형을 뽑아내면 되는 문제다. 처음에는 직사각형을 고려하지 않고 정사각형의 형태가 연속으로 있는 경우만 고려해서 틀렸다.class Solution {public: bool arr[201][201] = {false, }; int dir[3][2] = {{0, 1}, {1, 0}, {1, 1}}; int col, row, ret=.. 2024. 8. 12.
99클럽 코테스터디 21일차 TIL 정수 삼각형 정수삼각형프로그래머스 level 3 DP문제링크문제설명문제풀이DP를 푸는 것이 익숙하지 않아서, BruteForce 방식으로 우선적으로 풀이하고, DP로 바꾸는 작업을 거쳐 풀이했다.int brute (int cur, int prev, int lim, vector>& tri) { if (cur == lim) { return 0; } if (memo[cur][prev] != -1) { return memo[cur][prev]; } int tmp1 = brute(cur+1, prev, lim, tri); int tmp2 = brute(cur+1, prev+1, lim, tri); memo[cur][prev] = tri[cur][prev] + ma.. 2024. 8. 11.

티스토리툴바