본문 바로가기

DP19

[프로그래머스 Lv3] : GPS 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/1837 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 다양한 원인으로 인해 오류가 발생할 수 있는 GPS로 파악한 지나온 거점의 정보가 주어졌을 때, 최소한의 경로만 수정해서 가능한 경로가 되도록 만들어보자. 풀이 내가 떠올린 아이디어 일단 노드와 간선에 대한 정보가 주어졌기 때문에 나는 당연히 그래프 탐색을 이용해야한다고 생각했다. 나는 DFS를 이용해서 깊이가 k인 경로를 파악한 다음, 탐색한 경로와 주어진 GPS 경로가 같아지려면 몇 .. 2022. 7. 8.

[프로그래머스 Lv4] : 도둑질 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 도둑이 원형으로 배치되어있는 집을 털 때, 털고자하는 집과 인접한 집은 털지않는다. 이때 도둑이 훔칠 수 있는 돈의 최대값을 리턴하는 문제. 풀이 먼저 우리가 가장 간단하게 떠올릴 수 있는 방법은 집을 터는 모든 경우의 수를 다 떠올려보는 방법이다. 하지만 집은 최대 1000000개가 있을 수 있으므로 1000000개의 집 중에 이웃하지 않고 1개부터 .. 2022. 6. 29.

[프로그래머스 Lv3] : N으로 표현 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 숫자 N으로 특정한 수 number을 만드는데 필요한 N의 최소 개수 리턴 풀이 먼저 주어진 예제를 보자. 5를 이용해서 12를 만드는 방법에는 3가지가 있다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 첫번째, 두번째, 세번째 방법은 각각 5를 6번, 5번, 4번 이용해서 만들었다. 우리가 5를 이용해서 숫자를 만드는 방법은 5가지가 있다. 1. 5를 이어붙인다. ex) 55, 555, 5555, ... 2. +연산 사용. ex) 5 + 5, 55 .. 2022. 6. 28.

[BOJ] 16639 : 괄호 추가하기 3 문제 링크 https://www.acmicpc.net/problem/16639 16639번: 괄호 추가하기 3 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 곱하기의 연산자 우선순위가 더하기와 빼기보다 높기 때문에, 곱하기를 먼저 계 www.acmicpc.net 주어진 식에 괄호를 추가해서 가장 큰 값을 만들어내는 문제. 풀이 DP를 이용해서 구간별로 가장 큰 값을 계속 구한다음 마지막에 1부터 N까지 범위에서 가장 큰 값을 출력해주면 된다. 수식에 들어가는 숫자는 0~9사이의 숫자이므로 음수는 식에 입력되지 않는다. 먼저 내가 했던 실수는 "가장 큰 값" 을 출력한다는 키워드에만 집중해서 구간별로 최대값만 계속 구하고 있었다... 2022. 4. 19.

[BOJ] 18858 : 훈련소로 가는 날 문제 링크 https://www.acmicpc.net/problem/18858 18858번: 훈련소로 가는 날 1 이상 M 이하의 정수로 이루어진 길이 N의 수열 중 논산인 것의 개수를 998,244,353으로 나눈 나머지를 출력한다. www.acmicpc.net 논산(Non-산)인 수열이 몇 개인지 출력하는 문제. 풀이 논산이란 Non-산 즉 산이 아닌 수열을 의미한다. a1 a3 처럼 올라갔다 내려가는 형태의 수열을 산이라고 부르기로 한다. 여기서 DP배열을 어떻게 선언할지가 관건인데, 수열의 i번째 수에 대해서 3가지의 경우로 나누어서 생각할 수 있다. 1. i-1번째 수와 비교했을 때 i번째 수가 더 큰 경우. 즉, 올라온 경우(오르막) 2. i-1번째 수와 비교했을 때 i번째 수가 .. 2022. 4. 6.

[BOJ] 5582 : 공통 부분 문자열 문제 링크 5582번: 공통 부분 문자열 (acmicpc.net) 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 두 문자열이 가지고 있는 공통 문자열의 최대 길이를 출력하는 문제. 풀이 주어진 문자열을 각각 A, B 라고 하겠다. 나는 A 문자열의 문자를 돌면서 각각을 시작점으로 B 문자열과 비교하는 방식으로 탐색했다. A[0] 부터 A[length - 1] 까지 돌면서 각 문자를 시작점으로 B의 문자열과 비교했다. 모든 A의 문자마다 B문자열 첫 인덱스인 0번째부터 비교를 계속 해나가면 시간이 .. 2022. 4. 5.

[BOJ] 2533 : 사회망 서비스(SNS) 문제 링크 2533번: 사회망 서비스(SNS) (acmicpc.net) 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 트리로 이루어진 사회관계망에서 모두가 새로운 것을 받아들이기 위해 필요한 최소 얼리어답터 수를 구하는 문제. 풀이 기존의 DP문제와는 다르게 트리와 DP가 합쳐진 문제. 하나의 정점에 대해서 우리는 2가지 경우로 나눠서 볼 수 있다. 해당 정점이 얼리어답터이거나 얼리어답터가 아니거나. 0을 얼리어답터인 경우, 1을 얼리어답터가 아닌경우로 생각하고 DP배열을 .. 2022. 4. 5.

[BOJ] 1915 : 가장 큰 정사각형 문제 링크 1915번: 가장 큰 정사각형 (acmicpc.net) 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 0,1로 이루어진 배열에서 1로된 가장 큰 정사각형의 크기를 구하는 문제. https://jk6722.tistory.com/entry/BOJ-1028-%EB%8B%A4%EC%9D%B4%EC%95%84%EB%AA%AC%EB%93%9C-%EA%B4%91%EC%82%B0 [BOJ] 1028 : 다이아몬드 광산 문제 링크 1028번: 다이아몬드 광산 (acmicpc.net) 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수.. 2022. 4. 4.

[BOJ] 24887 : 최대한의 휴식 문제 링크 24887번: 최대한의 휴식 (acmicpc.net) 24887번: 최대한의 휴식 Amel은 SKH 회사 내에서 일을 잘하기로 소문난 유능한 사원이다. 그러나, 체력이 매우 안 좋은 Amel은 하루 동안 일하고 나면 빠르게 지쳐버리기 때문에 한 번 일하고 난 후 가능한 오랜 기간 동안 www.acmicpc.net 숭고한 대회 DIvision2 E번 문제. 대회 당일엔 앞에서 막히는 바람에 읽어보지도 못했다 ㅎㅎ; 풀이 연속으로 쉰 날의 최소값의 최대값을 구하는 문제다. 연속으로 쉬는날의 최소값을 이분탐색으로 찾아준다. 초기 범위는 Left = 0, Right = N 으로 설정해줬다. DP배열을 선언해서 DP[i] 연속으로 쉬는날의 최소가 mid 일때, i번째 날까지 채울수 있는 할당량의 최대값.. 2022. 3. 30.

이전 1 2 3 다음

티스토리툴바