[프로그래머스/JAVA] Level 2, 땅따먹기개발/DS&Algorithms / 2023. 5. 22.https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 문제의 자세한 내용은 링크를 확인해 주세요. (Nx4) 크기의 이차원 배열에서 마지막 행까지 모두 내려왔을 때 얻을 수 있는 점수의 최댓값 구하기 단, 같은 열을 연속해서 밟을 수 없습니다. 제한사항 행의 개수 N : 100,000 이하의 자연수 열의 개수는 4개이고, 땅(land)은 2원 배열로 주어집니다. 점수 : 100 이하의 자연수 문제 풀이 1. 첫 번째 풀이, 잘못된 접근 (..
[백준] 포도주 시식_2156_자바개발/DS&Algorithms / 2022. 8. 10.안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘 포스팅은 백준의 2156번 포도주 시식 문제를 정리하려고 합니다. 이 문제는 동적 계획법에 해당하는 문제로, 동적 계획법 풀이 전략을 이해하고 있으면 어렵지 않게 풀 수 있습니다. 반대로 말하면, 동적 계획법의 개념을 제대로 알 수 있는 문제라 할 수 있겠습니다. 저 또한 해당 문제를 풀면서 동적 계획법에 대해서 다시 이해할 수 있게 되었습니다. 문제의 자세한 내용은 아래 링크를 참고해주세요. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 ..
[백준] 평범한 배낭 (DP)_12865_자바개발/DS&Algorithms / 2022. 7. 3.안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘은 백준의 문제 풀이를 포스팅하려고 합니다. 12865번에 해당하는 문제로, 동적 계획법의 대표적인 문제인 평범한 배낭입니다. 자세하게는 배낭 안에 어떤 물건들을 넣었을 때 최고의 가치를 갖는지 알아보는 문제입니다. 이러한 배낭 문제는 풀이법이 두 가지로 나뉩니다. 첫 번째는 물건을 쪼갤 수 있다고 가정했을 때입니다. 이때는 gready(탐욕) 알고리즘을 통해서 최적의 방법을 찾을 수 있습니다. 두 번째는 물건을 쪼갤 수 없을 때 사용하는 풀이 전략인 동적 계획법 전략입니다. 두 번째 풀이가 오늘 설명할 방식이죠. 이제 문제를 보면서 자세하게 설명하도록 하겠습니다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배..
[알고리즘] 동적 계획법(Dynamic Programming) 알아보기개발/DS&Algorithms / 2022. 5. 7.안녕하세요😎 백엔드 개발자 제임스입니다 :) 이번에는 동적 계획법과 관련해서 포스팅하려고 합니다. 사실 동적 계획법은 어떠한 문제를 풀기 위한 전략 또는 기법에 가깝습니다. 따라서 추후 알고리즘을 다룰 때 해당 기법을 응용하여 개념을 정의하는 경우가 종종 있습니다. 이제 자세하게 알아보도록 하겠습니다. 동적계획법(Dynamic Programming, DP) DP라고도 불리는 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 각 결과들을 저장한 뒤, 다시 큰 문제를 해결하는 방법입니다. 이것을 '상향식 접근법'이라고 하며, 가장 최하위 해답을 구한 후 이것을 활용하며, 상위 문제를 풀어가는 의미입니다. 캐시(cache) : 이미 계산한 값을 저장해 두는 메모리 중복되는 부분 문제(overla..
[프로그래머스/JAVA] Level 2, 땅따먹기
개발/DS&Algorithms
/ 2023. 5. 22.
https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 문제의 자세한 내용은 링크를 확인해 주세요. (Nx4) 크기의 이차원 배열에서 마지막 행까지 모두 내려왔을 때 얻을 수 있는 점수의 최댓값 구하기 단, 같은 열을 연속해서 밟을 수 없습니다. 제한사항 행의 개수 N : 100,000 이하의 자연수 열의 개수는 4개이고, 땅(land)은 2원 배열로 주어집니다. 점수 : 100 이하의 자연수 문제 풀이 1. 첫 번째 풀이, 잘못된 접근 (..
[백준] 포도주 시식_2156_자바
개발/DS&Algorithms
/ 2022. 8. 10.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘 포스팅은 백준의 2156번 포도주 시식 문제를 정리하려고 합니다. 이 문제는 동적 계획법에 해당하는 문제로, 동적 계획법 풀이 전략을 이해하고 있으면 어렵지 않게 풀 수 있습니다. 반대로 말하면, 동적 계획법의 개념을 제대로 알 수 있는 문제라 할 수 있겠습니다. 저 또한 해당 문제를 풀면서 동적 계획법에 대해서 다시 이해할 수 있게 되었습니다. 문제의 자세한 내용은 아래 링크를 참고해주세요. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 ..
[백준] 평범한 배낭 (DP)_12865_자바
개발/DS&Algorithms
/ 2022. 7. 3.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 오늘은 백준의 문제 풀이를 포스팅하려고 합니다. 12865번에 해당하는 문제로, 동적 계획법의 대표적인 문제인 평범한 배낭입니다. 자세하게는 배낭 안에 어떤 물건들을 넣었을 때 최고의 가치를 갖는지 알아보는 문제입니다. 이러한 배낭 문제는 풀이법이 두 가지로 나뉩니다. 첫 번째는 물건을 쪼갤 수 있다고 가정했을 때입니다. 이때는 gready(탐욕) 알고리즘을 통해서 최적의 방법을 찾을 수 있습니다. 두 번째는 물건을 쪼갤 수 없을 때 사용하는 풀이 전략인 동적 계획법 전략입니다. 두 번째 풀이가 오늘 설명할 방식이죠. 이제 문제를 보면서 자세하게 설명하도록 하겠습니다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배..
[알고리즘] 동적 계획법(Dynamic Programming) 알아보기
개발/DS&Algorithms
/ 2022. 5. 7.
안녕하세요😎 백엔드 개발자 제임스입니다 :) 이번에는 동적 계획법과 관련해서 포스팅하려고 합니다. 사실 동적 계획법은 어떠한 문제를 풀기 위한 전략 또는 기법에 가깝습니다. 따라서 추후 알고리즘을 다룰 때 해당 기법을 응용하여 개념을 정의하는 경우가 종종 있습니다. 이제 자세하게 알아보도록 하겠습니다. 동적계획법(Dynamic Programming, DP) DP라고도 불리는 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 각 결과들을 저장한 뒤, 다시 큰 문제를 해결하는 방법입니다. 이것을 '상향식 접근법'이라고 하며, 가장 최하위 해답을 구한 후 이것을 활용하며, 상위 문제를 풀어가는 의미입니다. 캐시(cache) : 이미 계산한 값을 저장해 두는 메모리 중복되는 부분 문제(overla..