DP (동적 프로그래밍, Dynamic Programming)

1. 소개동적 프로그래밍이란? 동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 중복 계산를 방지하는 최적화 기법입니다. 언제 사용할까?DP는 다음과 같은 경우에 사용된다. 부분 문제가 반복적으로 등장하는 경우 최적 부분 구조 (Optimal Substructure): 부분 문제의 최적해를 이용해 전체 문제를 해결할 수 있을 때예를 들어, 피보나치 수열을 재귀로 구현하면 동일한 값이 여러 번 중복 계산된다.DP를 사용하면 이를 방지할 수 있다. 분할 정복과의 차이점 동적 프로그래밍분할 정복부분 문제 중복 여부OX대표 예제피보나치 수열, 배낭 문제, LCS병합 정렬, 퀵 정렬해결 방식저장하여 재사용독립적인 작은 문제로 나눠 ..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 3. 1.
• textsms

[JAVA] 석유 시추

석유 시추링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 2유형 : BFS, DP코딩테스트 연습 > PCCP 기출문제 > 석유 시추 풀이열 하나를 관통할 때 통과하는 석유 덩어리들의 크기의 합이 가장 큰 경우의 수를 구하는 문제석유 덩어리의 크기는 BFS로 구했다.그리고 통과할때마다 덩어리 크기를 구하면 시간초과가 나기때문에 DP개념을 이용해 이미 크기를 구한 덩어리의 정보를 저장하며 시간복잡도를 줄였다.처음 보는 석유 덩어리를 만나면 id, 크기를 map에 저장해놓고 석유 덩어리에 포함되는 x, y 좌표에 id를 저장해놓는 식으로.그리고 각 열을 순회하면서 해당 좌표에 id가..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 4.
• textsms

[JAVA] 붕대 감기

붕대 감기링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 1유형 : 구현, 배열코딩테스트 연습 > PCCP 기출문제 > 붕대 감기 풀이문제 설명대로 구현만 잘하면 되는 문제였다.if문이랑 배열만 잘 다루면 문제 없을 것 같다. 코드class Solution { public int solution(int[] bandage, int health, int[][] attacks) { int answer = 0; int curH = health; int index = 0; int stack = 0; for(int i =..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 3.
• textsms

[알고리즘] A* 알고리즘

A* (A star algorithm) 알고리즘이란??그래프의 한 정점에서 다른 한 정점까지의 최단거리를 각각 구하는 알고리즘목적지까지의 거리를 계산하는 휴리스틱 추정값을 이용해 다익스트라를 개선한 알고리즘휴리스틱 함수의 성능에 따라 알고리즘 성능이 달라진다. 시간복잡도O(b^d) (완전 탐색) ~ O(E log V) (최적화 시)b는 분기 계수 (한 노드에서 이동할 수 있는 평균 갈래 수)d는 최단 경로의 깊이(시작점에서 목표까지의 단계 수)E는 그래프의 간선 수, V는 노드 수 공간복잡도O(b^d) (최악) ~ O(V) (일반적인 경우)   다익스트라와의 차이점 다익스트라출발점에서 모든 노드에 대한 최단거리를 탐색함단순히 현재 지나온 거리가 가장 짧은 노드를 선택해 탐색A*출발점에서 도착점까지의 최단..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 2. 3.
• textsms

[JAVA] 양궁대회

양궁대회링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3유형 : dfs, 백트래킹코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 양궁대회 풀이라이언이 어피치를 가장 큰 점수 차이로 이기기 위한 n 발의 화살의 경우의 수를 구하는 문제.근데 가장 큰 점수 차이의 경우의 수가 여러 가지일 경우, 낮은 점수를 더 많이 맞힌 경우가 정답. 각 점수대 마다 라이언이 점수를 가져가냐, 안 가져가냐 둘 중에 하나니까 이걸 그래프로 생각을 해서 dfs로 모든 경우의 수를 보고가장 큰 점수 차이면서 낮은 점수가 더 많이 맞은 경우를 result에 저장하며 풀었다. ..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 3.
• textsms

[JAVA] 신고 결과 받기

신고 결과 받기링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 1유형 : 구현코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 신고 결과 받기 문제 설명신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다.무지가 개발하려는 시스템은 다음과 같습니다.각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다. 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다. 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다. k번 이상 신고된 유저는 게시판 이..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 1.
• textsms