꾸준하게 거북이처럼

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 입력 개수 단위가 크다 => 완탐은 아니고, 이분탐색도 조건 찾을 때 시간초과 발생 가능,, 어떤 방법을 선택해야할까? 주어진 데이터를 순서대로 누적해서 계산하는 중에 조건에 부합하지 않은 상황이 발생시, 누적 데이터 중 가장 큰 값 또는 작은 값 제거가 필요한 경우, 힙 자료구조 (logN) 를 사용할 수 있다. 이 문제에서 현재까지 데이터 중에서 k개의 무적권은 가장 큰 수에 사용, 작은 수의 적군 일때는 병사를 소모하는 방법으로 최대 라운드 수를 구할 수 있다고 볼 수 있다. from heapq i..

2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 공유기 사이의 최대 거리를 찾는 문제로, 입력이 20만인 것을 보면 시간 복잡도는 nlogn이하로 만들어야한다. 이진 탐색으로 문제를 해결을 해보자. 최소 거리를 s, 최대 거리를 e라고 했을 때 중간값을 탐색하면서 조건(공유기를 해당 값 거리 만큼씩 설치할 수 있는가)에 맞는지 체크하면 문제를 해결할 수 있다. 코드 n, c = map(int,input().split()) h = [] for _ in rang..

13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 관련된 문제로 연속합 문제가 있는데, 이번에는 연속합2 이다. dp는 역시, 이전의 값을 참조해서 답을 찾아나가는 과정! 경우의 수를 잘 나누는 것이 진짜 중요하다. => 점화식 빠르게 찾는 지름길* 10만이 입력이라서, 2차원 배열은 포기해야겠네 생각했었다. 하지만 그렇다고 해서 2차원 배열을 바로 포기해서는 안된다. 내가 어떻게 써먹는지에 따라 시간적 효율성은 달라지기 때문. 풀이 이 문제는 두 가지의 경우의 수로 나눌 수 있다. 이 힌트만으로도 문제 풀이가 금방..

11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 가장 긴 부분 수열 문제를 풀어봤다면, 이 두 가지 힌트로 문제풀이를 쉽게 떠올릴 수 있을 것이다. 1. 주어진 수열 arr[i] 까지의 가장 긴 증가 수열의 길이를 담은 increase[i] 사용 2. i 부터 n까지 가장 긴 감소 수열의 길이를 담은 decrease[i] 사용 => **reverse를 이용한다. 주어진 수열: 1, 5, 2, 1, 4, 3, 4, 5, 2, 1 increase[i] - 증가하는 수열 길이: 1, 2, 2, 1, 3, 3, 4, 5, 2, 1 dec..

11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수 www.acmicpc.net 풀이 현재의 값보다 작은 수들 중 가장 dp 값이 큰 것을 더하여 dp값을 업데이트 하고 max(dp)를 구한다. 코드 n = int(input()) arr = list(map(int, input().split())) dp = [0] * n dp[0] = arr[0] for i in range(1, n): big = 0 for j in range(i): if arr[j] < arr[i] and big < ..

1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net n = 1 : 3가지 n = 2 : 7가지 n = 3: 17가지 .,, 어떤 규칙이 있을까 아무리 생각해도 떠오르지 않았다. 기준을 무엇으로 두어야할까? 가 문제였다. dp는 전의 결과를 참고하는 과정에서 차곡차곡 답이 쌓인다. 이걸 꼭 명심하자. 2x1 타일을 새로 추가할 때 그 때 2x1 타일을 기준으로 총 3가지의 경우로 분류할 수 있다. 1. 아무것도 선택 안할 때 2. 왼쪽 타일 선택 3. 오른쪽 타일 선택 - 아무것도 선택 안하는 경우 (dp[i][0]이라 하자) dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] - 왼쪽 타일을 선택하는 경우 (dp..

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이번달까지는 dp만 풀 것 같다. 오늘은 가야할 곳이 있어서 바쁜 나머지,, 잠도 요즘 덜자고? 맘도 급했고 문제가 잘 풀리지 않았다.ㅠ dp인것은 대충 감이 오지만, dp는 지금까지 백준에서는 1 또는 2차원 배열을 이용해서 차곡차곡 이전의 요구사항에 맞게 정답을 만들어 나갔다. 예를들어 최솟값을 찾는 거라면, n이 될 때까지, 점화식을 이용해서 1 ~ n 까지 차례대로 차곡차곡 이전의 값을 이용해서 n일때의 최솟값을 만들어 나가는 느낌이..

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 풀었긴했지만 시간적 효율이 안좋아서 다시 한번 생각해 보았다. 처음에 이 문제에서 점화식을 dp[n][k] = dp[n - 1][i]( i = 1 ~ k까지) 라고 두었다. 그렇게 되면 => 3중 중첩문 + 여러번 같은 수를 반복해서 더하게됨. dp[2][1] 이나 dp[2][5] 를 더할 때도 반복해서 dp[1][1 ~ k] 까지 똑같이 같은 반복으로 더해야한다. 이는 불필요하다. 아래는 위의 점화식으로 코드를 짠것이다. dp = [[0] * 201 for _ in range(201)] n, k = map(int,input().split()) for i in range(1, 20..

1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 최소 제곱수의 합을 쭉 나열해 보면, 0 - 0개 1 - 1^2 (1개) 2 - 1^2 + 1^2 (2개) 3 - 1^2 + 1^2 + 1^2 (3개) 4 - 2^2 (1개) 5 - 2^2 + 1^2 (2개) 6 - 2^2 + 1^2 + 1^2 (3개) 7 - 2^2 + 1^2 + 1^2 + 1^2 (4개) 8 - 2^2 + 2^2 (2개) 9 - 3^2 (1개) 10 - 3^2 + 1^2 (2개) 11 - 3^2 + 1^..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 가장 긴 증가 부분 수열을 찾는 것으로, 각 수열 요소보다 작은 요소들의 수열 길이 중 가장 큰 것 +1 을 하는 방식으로 문제를 풀 수 있다. arr 10 20 10 30 20 50 dp 1 2 1 3 2 4 주어진 수열에서 증가수열 & 수열의 길이가 최대가 되어야한다. 그렇다면 dp를 이용해서 현재까지 가장 수열의 길이가 큰 것을 차근차근 구하고, 이를 배열에 저장한다. 현재 요소보..