![]()
문제 https://www.acmicpc.net/problem/28082 28082번: 기계오리 연구 인하대학교 기계공학과의 기계오리 연구실에서는 2023년 버전 기계오리를 완성하기 위해 실험을 진행하고 있다. 실험 도중, 기계오리에 1개 이상 $K$개 이하의 배터리를 삽입하면 기계오리가 언 www.acmicpc.net 문제 풀이 대표적인 DP유형 중의 한 문제였던 것 같다. 나는 항상 DP 문제를 풀 때 처음에는 dp 배열을 2차원으로 접근하려고 한다. N개의 배터리중에서 배터리를 최대 k개 사용해서 만들 수 있는 전력량의 합을 목표로 점화식을 세워보기 전에 그림으로 그려보자. 주어진 예제를 바탕으로 간단하게 그림을 그려보았다. 최대 k개를 사용해서 구할 수 있는 전력량의 합을 계산하기전에 배터리를 통..
![]()
문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 풀이 사실 대표적인 DP문제이다. DP 문제는 차근차근 손으로 할 수 있는 만큼 해보는 것이 좋다고 생각한다. n = 0인 경우 3*0의 크기의 벽을 채우는 경우의 수는 공집합이라는 느낌으로 1로 생각했다. n = 1인 경우 3*1 크기의 벽은 주어진 도형을 통해서 채울 수 없다. 직접 그려보면 알 수 있다. n = 2인 경우 3개의 모양으로 채울 수 있다. n = 3인 경우 dp 문제이기 때문에 그 전에 구했던 도형들을 최대한 이용해보려고 했다. 3*3의 사각형인 경우 3*2 사각형과 3*1 사..
![]()
📕문제 https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 🔎문제 풀이 해당 문제는 문제를 읽고 어떤 알고리즘을 사용해서 접근해야 할지 바로 알아야 한다. 친구들의 사탕을 모조리 뺏어버린다 해당 문구를 통해서 유니온 파인드를 통해서 모든 노드의 부모 노드를 설정해야 함을 알 수 있다. 주어진 친구들의 관계를 통해서 묶음으로 친구들을 분류해야 한다. 그리고 얻을 수..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 처음 볼 때 DP 문제라고 생각을 하지 못했는데, 손으로 써 내려가면서 DP문제라는 것을 깨달았다. 우선 우리는 목표 숫자를 N이라는 숫자를 여러번 사용해서 표현해야 한다. 여기서 왜 DP이냐에 대해서 생각을 해보자. 만약 5를 3번 쓸 경우 만들수 있는 숫자의 조합은 무엇일까? 이걸 구하기 위해서는 5를 1번 쓸 경우, 5를 2번 쓸 경우에 대해서 구해야 한다. 이유는 써 내려가..
![]()
문제 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 문제 풀이 골드 3이라는 난이도 치고는 접근방법을 빨리 생각해 낸 문제였던 거 같다. 배낭문제와 비슷하다고 생각하고 접근했었는데, 문제를 풀고 다른사람의 풀이과정을 보니 다들 배낭과 비슷하다고 생각했던 것 같다. 그 정도로 접근하기가 쉬웠던 문제였던것 같다. 추를 사용해서 만들 수 있는 모든 무게를 검사해 주면 된다. 추를 사용해서 만들 수 있는 무게에 대한 방법은 크게 3가지 방법이 있을 것..
![]()
문제 https://www.acmicpc.net/problem/20542 20542번: 받아쓰기 세계적인 기업 CTP(Chickens Threaten Programming)에 입사하기 위해서는 영어 받아쓰기 테스트를 통과해야 한다. 영어 받아쓰기는 채용 담당자가 불러주는 단어를 지원자가 받아쓰는 시험이다. CTP에서는 www.acmicpc.net 문제 풀이 우선 문제가 굉장히 길고 비슷한 말이 많아서 문제에 대한 정확한 파악이 필요하다. 입력은 크게 답변과 정답이다. 이 두 가지를 구분하는 것이 굉장히 중요하다. 우리는 답변을 수정,삭제,변환을 통해서 정답과 같은 문자열을 만들어야 한다. 그리고 날려쓰기라는 정보가 등장한다. i를 날려썼다면 i, j, l v를 나르였으면 v, w로 인식된다. 즉 우리가 ..
![]()
문제 https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 문제 풀이 문제는 정말 간단하다. 주어진 순서에서 최소한의 변경을 통해 오름차순으로 정렬하는 문제이다. 접근방법에 대해서 정말 많은 고민을 했었다. 최소한의 변경을 위해서는 기존 배열에서 최대한 고정시켜야 하는 부분을 길게 해야 한다고 이해했다. 그렇다면 고정시키는 번호를 어떻게 정할까? 문제 보기에서만 봐도 움직이는 번호들은 정해져 있는것을 보면 유추할 수 있다. 3 7 5 2 6 1 4 -> 1..
![]()
문제 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 풀이 DP의 대표적인 유형이다. DP는 항상 DP 배열이 무엇을 의미하는지 정하는 것이 가장 중요하다. 내가 정한 DP 배열은 다음과 같다. DP[i]는 i일에 벌 수 있는 최대 금액 1일 2일 3일 4일 5일 6일 7일 3 5 1 1 2 4 2 10 20 10 20 15 40 200 문제에서 주어진 예시는 다음과 같다. 우리는 N일까지의 상담을 바탕으로 ..
![]()
문제 https://www.acmicpc.net/problem/1106 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 문제 풀이 처음에 그리디인 줄 알고 접근했다가, 도저히 그리디로 할 수가 없어서 DP로 접근방식을 수정했다. DP문제에서 가장 중요한 점은 DP 배열을 어떤 식으로 설계하느냐이다. 다양한 방법으로 설계할 수 있지만, 문제에서는 최소한의 비용으로 목표 인원수를 모을 수 있느냐에 초점을 맞추기 때문에 DP배열의 index를 비용으로 잡았다. 그 부분이 나중에 최소 비용을 찾기 편하다고 생각했..
