문제 링크 https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

문제 링크 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제 풀이 - 시간복잡도의 경우 상향식 O(N), 하향식 O(2^N) 소요됨 - 하향식의 경우 메모리제이션 기법 사용하여 풀이 - 상향식으로 풀 때 초기항부터 누적하는 형태로 풀이할 경우 최대치가 int를 초과하는 것으로 생각됨 (최대치 따로 구해보기) *하향식 풀이의 경우 아래 기술 블로그 통해 형식 이해함 https://steady-coding...

문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 풀이 - 입력의 경우 int 배열로 100개까지 받으므로 400byte - 연산에 필요한 DP의 경우 행20 * 100 * 8byte = 16KB 정도 메모리 잡음 - 최대치의 경우 출력에 2^63 -1 명시되어 있기 때문에 long으로 처리 시간 복잡도 상향식 (Bottom-Up) 하향식(Top-Down, 재귀 함수) O(N * 20) O(2^n) = O(2^100) - ..

문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 - 시간복잡도 : O(N) - 점화식 DP[N] = DP[N - 2] + DP[N - 1] 형태로 최대 N이 90까지 가능하다 - 피보나치의 경우 46번째만 넘어가도 29억이 넘기 때문에 long (8byte, 64bit)으로 문제 풀이 해야 함 풀이 순서 가짜 문제 정의 - 가짜 문제로 정답을 구할 수 있는가? - 초기항 - 점화식 - 풀이 & 테스트 0 1 2 ..

Jenkins 설치 (By Docker) - 처음 lts와 2.176.2 설치했었는데, 버전 문제인지 플러그인 설치 실패 계속 되었음 - docker hub에서 2.413-jdk11버전으로 받으니 플러그인 정상 설치 확인 # docker image 검색 $ docker search jenkins # image 다운로드 $ docker pull jenkins/jenkins:2.413-jdk11 # image 확인 $ docker images # 설치 $ docker run --name jenkins -d -p 8080:8080 -p 50000:50000 -v /home/jenkins:/var/jenkins_home -u root jenkins/jenkins:2.413-jdk11 # container 터미널..

문제 링크 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 풀이 - 시간 복잡도 O(N) - 메모리 제한 4MB 직접 문제를 풀었을 때 최대 값을 구하는 것은 Bottom-Up방식으로 설명에 따라 그대로 하였기에 구할 수 있었다. 그러나 최소 값의 경우 구할 수 없었고, 기술 블로그를 찾아 본 결과 '메모리 제한', '슬라이딩 윈도우 기법'와 같은 파악하지 못 한 부분에 대해서도 확인할 수 있었다. (최소값의 경우 반대로 선택 가능 범위 내에 최소 값을..

문제 링크 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제의 경우 직접 풀이하지 못하고, 기술 블로그를 참고하여 풀 수 있도록 하였습니다. 2차원 배열 DP로 풀이시 문제가 되었던게 '0 ~ 9의 숫자를 사용한 여부는 어떻게 알 수 있을까' 였습니다. 3차원으로 변경하여 0 ~ 9 까지 체크했는지 반복문으로 사용해서 할 경우 그거대로 더 복잡해 질거 같은 생각이 들었습니다. 기술 블로그를 찾아본 결과 해당 문제는 '비트 마스킹' 기법을 사용하여 문제 풀이 가능한 것을 알게 되었고 2~3일간 이해가 되지 않아 시간을 보냈고, 지금은 이해한 내용을 ..

문제 링크 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제 풀이 - 시간복잡도 O(N) - 최대치의 경우 9907에 대한 나머지를 구하라 하므로 Integer로 예상 가능 (문제 설명에 나머지 처리 없는 경우 최대치 잘 파악) 2 * 1 일때 0 의 경우 아무것도 없는 경우 1의 경우 왼쪽에 사자가 있는 경우 🦁 2의 경우 오른쪽에 사자가 있는 경우 🦁 2 * 2의 경우 1) 앞에 블록에 빈 우리 더할 경우 : 3가지 🦁 🦁 2) 왼쪽에 사자🦁가 있는 우리를 추가하는 경우 : 2 가지 빈 우리 아래에 추가하거나 🦁 오른쪽에 사자가 있는 우리 밑에 추가 할 수 있다 🦁 🦁 ..

문제 링크 https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1 0) { T -= 1; N = Integer.parseInt(br.readLine()); sb.append(sumValue(N)).append("\n"); } } static long sumValue(int n) { long result = 0L; for(long v : DP[N]) { result += v; } return result; } static void preProcess() { DP = new long[65][10]; for(int i = 0; i

문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 풀이 - 시간 복잡도 O(N), 최대치 Integer 범위 내 - 스티커 하나를 뜯을 경우 상하좌우로 찢어져서 사용할 수 없게 됨 - 2 x N열 스티커, 2차원 배열 형태의 DP 문제 초기화 1 DP[0][i] 50 DP[1][i] 30 0번행의 2열 스티커를 뽑을 경우 아래 선택가능한 영역에서 최대치를 뽑아 더해주면 됨 0 1 2 O 스티커 선택 O O 1번행의 2열..

문제 링크 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이 - 시간복잡도 O(N) - DP 상향식 문제 *절차 (1) 가짜 문제 정의 진짜 문제 = 주어진 N에 대해 N을 1,2,3의 합으로 표현하는 경우의 수 가짜 문제 = DP[i] 를 1,2,3으로 표현하는 경우의 수 (2) 가짜 문제를 풀면 진짜 문제를 풀 수 있는가 ? YES (3) 초기항 정의 0 1 2 3 0 1 2 ( 1 + 1, 2) 4 - 0에 3을 더할 경우 - 1에 2를 더할 경우 - 2에 1을 더할 경우 (4) 점화식 세우기 DP[i] = DP[i - 1] +..

문제 링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 - 시간 제한 0.5초 이므로 완전 탐색으로 풀 경우 시간 초과 발생 - 첫번째 집의 RGB 값으로 초기값을 설정하고, 동적 프로그래밍으로 풀이한다 - 최종적으로 DP[N][1 ~ 3] 값 중 최소값 출력 - 시간복잡도 : O(N) 점화식 DP[i][j] = Math.min(DP[i - 1][x], DP[i - 1][y]) + RGB[i][j] (이때 i..

- 슬램덩크 성지 순례 위해 가마코마에 (가마쿠라코 마에) 역을 방문하실 분에게 몇가지 정보 공유- 해당 게시글은 신주쿠역을 기준으로 작성- 에노덴은 10분 단위로 열차 운행(1) 날씨 어플, 웹 사이트 통해 일기 예보 확인 (2) 하루 날 잡고 방문할 경우 교통비 절약 위해 "에노덴 PASS" 구매 (3) 🇨🇳중국 명절/연휴 확인 '이것이 현실이다!' 1. 일기 예보 확인날씨 어플이나 아래 두 웹사이트 통해 확인 후 방문하도록 하였다 https://www.accuweather.com/ko/jp/tokyo/226396/june-weather/226396 도쿄, 도쿄, 일본 월별 날씨 | AccuWeatherGet the monthly weather forecast for 도쿄, 도쿄, 일본, incl..

문제 링크 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N^2) - "병사 배치하기" 문제에서 역추적을 추가한 문제 - Stack의 성질(LIFO)을 활용하게 되면 pop하는 것만으로도 오름차순 정렬 결과를 구할 수 있다 https://dev-ljw1126.tistory.com/271 [BOJ 18353] 병사 배치하기 (Ja..

문제 링크 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 - DP, LIS (Longest Incresing Subsequence, 최장 증가 부분 수열) - 시간 복잡도 O(N^2) - 단순히 LIS 최대 길이를 구한 후 N과 차이를 구하면 되는 문제라서 DP 배열을 순차적으로 갱신 해준다 (1) 입력된 배열을 reverse함 (2) DP 배열을 1로 초기화함 (숫자 자신을 가르킴) (3) 순차 조회하면서 앞에 숫자 중..

문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N * 10) = O(N) - MOD를 나누지 않으면 터지는 이유 확인 필요 DP[i][j] = i 는 자리수 이고, j는 j로 끝나는 수를 뜻함 i\j 0 1 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9 2 10 21 12, 32 23, 43 34, 54 45, 65 56, 76 67, 87 78, 98 89 제출 코드 1) Bottom-Up 방식 import java.util.*; import java.io.*; public class Ma..

문제 링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 - 상향식(Bottom-up)으로 DP 풀이 - 시간복잡도 O(N) *DP 배열 결과 idx 0 1 2 3 4 5 6 7 8 9 10 DP 0 0 1 1 2 3 2 3 3 2 3 제출 코드 import java.util.*; import java.io.*; public class Main { static int N; static int[] DP; static void input() throws Exception { BufferedReader br = new BufferedReader(new..

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net문제 풀이 - 시간복잡도 O(N)- 초기항 구하고, N번째 포도주에 대해 아래 3가지 경우를 비교하여 최대 값 구함  이때 3번 연달아 포도주를 마실 수 없다는 규칙에 따라 DP 테이블을 갱신한다 i번째 포도주를 마시지 않는 경우① DP[i - 1]할당 i번째 포도주를 마시는 경우② i - 1 번째 포도주 먹고 마시는 경우 최대치 (DATA[i - 1] + DP[i - 3])③ i - 2 번째..