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 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

[JAVA] 로또의 최고 순위와 최저 순위

로또의 최고 순위와 최저 순위링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 1유형 : 구현코딩테스트 연습 > 2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 로또의 최고 순위와 최저 순위 문제 설명 로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다.민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변..

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