뺙이 개발자

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 풀이방법1) recursive함수의 인자로 r,c를 넘겨 검사한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; impor..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net '좌표압축'이라는 것을 해줘야하는 문제이다. 좌표압축은 이분탐색을 이용한 STL함수인 lower_bound를 이용하게 된다. 알고리즘의 아이디어는 위와 같다. 일단 배열을 입력받아 정렬을 해준다. 그리고 중복 원소를 제거해준다. 이 후, lower_bound를 이용하여 현재 값을 넣어도 정렬이 유지되는 곳 중에서 가장 왼쪽 위치를 찾는다. 이 위치..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net dp문제이므로 테이블 설정을 잘 해주어야 한다. d[a][b]=k : a부터 b 팰린드롬이라면 k=1, 아니라면 k=0 우선, a부터 a는 항상 팰린드롬이다. 추가로 길이가 1 차이나는 a와 a-1는 서로 값이 같다면 팰린드롬이 된다. 그리고 길이가 2 차이부터 n-1 까지 나는 숫자가 팰린드롬인지 검사해주면 된다. 시작점이 s 이고 끝점이 e라면 두 숫자가 같으면서, 시작점과 끝점을 제외한 가운데 숫자가 팰린드롬이면 s부터 e는 팰린..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp문제이므로 테이블 설정을 잘해줘야 한다. d[a][b]=k : (a,b)까지 만들 수 있는 가장 큰 정사각형의 한 변의 길이는 k이다. 그러기 위해선 지금 좌표를 기준으로 위쪽, 왼쪽, 대각선왼쪽을 볼 필요가 있다. (a,b)를 기준으로 위의 세 군데 중에서 1이 아닌 0을 갖게 되면 지금 나의 좌표에서 만들 수 있는 정사각형의 크기가 다시 1로 초기화된다. 그러니깐 현재 좌표를 기준으로 위,왼,대각선왼쪽에 영향을 받게 되는 것이다. 그래서 나머지 두 좌표가 아무..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net dp문제이다. dp문제이므로 테이블 설정을 잘 해줘야 한다. d[a] = b : a원을 만들 수 있는 방법의 수가 b개 라고 정의해주었다. 먼저, 3원을 만들어야하고 우리에겐 1,2,3원이 있다고 가정해보자. 여기서 포인트는 "가장 마지막에 해당 동전을 사용하여 금액을 완성시키는 과정" 이다. 1) 1원을 가장 마지막에 사용하여 금액을 완성시키기 위해서는 1원을 채우는 경우, 2원..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 1 = 1*1 2 = 1*1 + 1*1 3 = 1*1 + 1*1 + 1*1 4 = 2*2 5 = 2*2 + 1*1 6 = 2*2 + 1*1 + 1*1 7 = 2*2 + 1*1 + 1*1 + 1*1 8 = 2*2 + 2*2 9 = 3*3 이렇게 나타낼 수 있다. 그래서 d[1] = 1 d[2] = d[2-1]+1 = 2 d[3] = d[3-1]+1 = 3 d[..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 아주 유명한 dp문제이다. 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중에서 가장 긴 것을 찾아야한다. 부분 수열이 되어야하므로 공통되는 부분이 연속할 필요는 없다. 가능한 수열을 전부 각각 만들어 비교하게 되면 시간복잡도가 O(2^n*2^m) 으로 너무 느려서 dp를 이용해야한다. dp를 사용하게 되면 문자열의 길이가 n,m 일 때, 시간..

https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net dp문제이다. dp문제이므로 테이블 설정을 잘 해주어야 하고, 현재 무슨 값을 저장할 필요가 있는지 생각해야한다. 먼저, 몇 초가 지나갔는지를 저장해줘야 하고 현재까지 몇 번의 움직임이 있었는지를 저장해줘야한다. 그래서 d[a][b]=k : a초일 때, b번 움직인 경우 얻을 수 있는 자두의 최대개수는 k개 라고 설정해주었다. b번 움직였다는 사실을 통해 현재 몇번 나무에 위치해 있는지 알 수 있다. 1번..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp문제이다. dp문제는 테이블을 정의하는 것이 너무나 중요하다. 이번 문제도 테이블만 잘 정의하면 어렵지 않게 문제를 풀어나갈 수 있는데, 중요한 건 테이블을 정의하는 게 쉽지 않다는 것이다. 우선, 계단 수를 생각해보자. 길이가 1인 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9 이렇게 총 9개가 있다. 그리고 길이가 2인 계단수는 1로 부터 10,12 / 2->21,23 / 3->32,34 / ... / 8->87,89 / 9->98 가 있다. 현재 1~8까지는 각각 2개의 계단수를 생성하였고,..

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 퇴사2 문제는 퇴사1 문제와 N의 범위만 다르다. N (1 ≤ N ≤ 1,500,000) 이 범위가 매우 크기 때문에 완전탐색으로 풀 수 있었던 퇴사1과 달리 퇴사2는 무조건 dp로 풀어줘야 통과할 수 있다. 상담일 수는 t배열에 저장해주었고, 상담액은 p배열에 저장해주었다. 추가로 1-indexed로 풀어주었다. 처음엔 for문을 앞에서부터 돌리려고 하였는데, 그 ..