문제 링크 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 번째..

초기 개발 환경에서 h2 inmemory 데이터 베이스를 활용하여 테이블 생성 및 샘플 데이터 입력할 수 있도록 설정 수행 1. 의존성 추가 (build.gradle) dependencies { // spring boot implementation 'org.springframework.boot:spring-boot-starter-web' implementation 'org.springframework.boot:spring-boot-starter-data-jpa' // test testImplementation 'org.springframework.boot:spring-boot-starter-test' // lombok compileOnly 'org.projectlombok:lombok' annotatio..

문제 링크 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 문제 풀이 - DP, 피보나치(fibonacci) 응용하여 풀면되는 문제였음 - 시간 복잡도 O(N * M) 절차 (1) DP 배열에 좌석 개수별 경우의 수를 미리 구함 (2) 앉을 수 있는 좌석 범위를 각각 구한 후 곱셈 연산으로 결과값 구함 (이때 모든 좌석이 VIP인 경우 앉을 수 있는 경우의 수는 1) *DP 초기항 구할 경우 자리가 1개 일 때 1가지 경우의 수 자리가 2개 일 때 2가지의..

문제 링크 https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 문제 풀이 - 시간복잡도 O(N) - DP 배열의 경우 이전 값과 곱한 경우와 자기 자신과 비교했을 때 더 큰 값을 갱신 1 2 3 4 5 1.1 0.7 1.3 0.9 1.4 1.1 0.77 1.3 1.117 1.638 *참고. 자바 소수점 처리 https://bullie.tistory.com/7 [Java] 자바 소수점 원하는 자리수 만큼 출력 자바로 문제를 풀다보면 소수..

문제 링크 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 문제 풀이 - 00, 1 이 주어지고, N 자리 수 만큼의 2진 수열 개수를 구하는 문제 - N = 1,000,000 인 경우 int[] DP = new int[N + 1] 했을 때 배열 자리수 하나당 4byte 차지하므로 4MB 용량 차지 (제한 256MB) - 상향식 방식으로 풀이하여 O(N) 시간복잡도 소요됨 초기화 DP 0 1 2 ... 0 1 2 ... N = 1 의 경우 1 N =..

문제 링크 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 - 매 테스트 케이스마다 피보나치 함수로 구할 경우 '시간 초과' 에러 발생 - fibo(N) = fibo(N - 1) + fibo(N - 2) 형태로 구해지는 피보나치 수열은 재귀 방식으로 구할 때 O(2^n) 시간복잡도 가짐 (N이 최대 40일 때 2^40은 대략 10^12) 그래서 - 상향식으로 40번째 배열 까지 DP 배열에 값을 구한 후 호출하게 되면 O(N) 시간복잡도로 구해짐 이때 0, 1 초기항 처리 후 호출 0 1 2 3 4 5 0 1 1 2 3 4 특이한..

도쿄 여행 3일차 그 날은 마침 일기 예보에 오후부터 비가 예상되어 신주쿠 교엔에 방문하기 좋은 흐린 날씨☁️였다위치- 도쿄 신주쿠역에서 걸어서 5 ~ 10분 정도 소요  위치/좌표 공유 (구글 나만의 지도) 신주쿠 교엔 외에 너의 이름은, 날씨의 아이, 초속 5cm, 스즈메의 문단속의 배경지 좌표도 포함" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스성지 순례 마침 신주쿠 교엔 바로 옆에 스팟 한 군데가 있어서 아침 일찍 다녀왔다 1. 라보헴 (Cafe La boheme)  - '너의 이름은'에서 오노데라상과 타키가 아르바이트 하던 이탈리아 식당좌표 35.6876, 139.71281 TIP. 여기서 신주쿠 교엔으로 이동할 경우 건너편 산책로 통해서 걸어가시면 편합니다.아니면 ..

문제 링크 https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제 풀이 - 첫째 줄 회사 직원 수 n, 최초의 칭찬 횟수 m (2 ≤ n, m ≤ 100,000) - 둘째 줄 직원 n명의 직속 상사(=부모 노드)가 주어짐, 최종적으로 1번이 사장(=Root)이다. - 다음 m줄에는 직속 상사로부터 칭찬을 받은 직원 번호 i, 칭찬의 수치 w가 주어진다. (2 ≤ i ≤ n, 1 ≤ w ≤ 1,000) 최대치 계산할 경우 - 직원 수(n) 1명에..

문제 링크 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 풀이 - 인접 리스트로 트리 정의 - 제거할 노드(REMOVE_NODE)를 인접 리스트 순회하면서 제거 - LEAF 노드 배열 값을 갱신하며 DFS 탐색 - 최종적으로 ROOT 노드의 있는 값을 출력하면 됨 - 시간 복잡도 : O(N) , (N

문제 링크 https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 문제 풀이 - (중요) 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라 함 - 입력 초기화할 때 이전 노드와 현 노드 차이가 1이 아닌 경우 부모 노드 인덱스(parentIdx)를 변경하여 PARENT 배열 정의 - PARENT 배열을 구한 후 선형 탐색 하여 O(N) 시간복잡도 가짐 TARGET 노드가 있을 때 TARGET ..

문제 링크 https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 풀이 - 두 노드 간의 가장 가까운 공통 조상(Lowest Common Ancestor)을 찾음 - 각 노드의 부모 노드(PARENT)와 깊이(DEPTH) 를 구하고, 깊이의 차가 있을 경우 동일하게 맞춘 후 공통 조상 노드를 찾아 감 - 선형 탐색으로 풀이 하여 O(T * N) 시간복잡도 ( 2 ≤ N ≤ 10,000 ) LCA..

문제 링크 https://www.acmicpc.net/problem/20364 20364번: 부동산 다툼 첫 번째 줄에 땅 개수 N과 꽉꽉나라에 사는 오리 수 Q가 공백으로 구분되어 주어진다. (2 ≤ N

문제 링크https://www.acmicpc.net/problem/15900 15900번: 나무 탈출평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게www.acmicpc.net문제 풀이- 노드 N (1 ~ 500,000) 이때 1번 노드가 정점 노드로 주어짐- 간선의 수 N - 1 - LEAF 노드의 DEPTH를 구하고 그 합이 홀수인 경우 Yes, 짝수인 경우 No로 답을 구하면 됨- 시간복잡도 : O(V + E) = O(500,000 + 499,999)  DEPTH 배열을 따로 구할 필요 없이 전역 변수에 LEAF 노드의..

문제 링크 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 풀이 - 정적 클래스를 정의하여 주어진 입력값을 이진 검색 트리(전위 순회) 방식으로 정의 - 이전에 풀었던 트리 순회와 동일하게 재귀 함수 사용하여 후위 순회 구할 수 있도록 함 - 노드의 최대 개수는 10^4 이고, 각 노드 별로 최대 2번 재귀를 호출할 때 O(2 * 10^4) 시간 복잡도 소요 참고 https://dev-ljw1126.tistory.com/248..

문제 링크 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 풀이 전위 순회(preodrer) : 부모 > 왼쪽 > 오른쪽 중위 순회(inorder) : 왼쪽 > 부모 > 오른쪽 후위 순회(postorder) : 왼쪽 > 오른쪽 > 부모 - 알파벳 26개 그리고 알파벳 노드별 자식 2개(왼쪽, 오른쪽) - 전위/중위/후위 순회로 인해 총 3번 로직 수행 - 한 노드당 최대 2번 재귀 호출을 수행하므로 O(26 * 2 * 3) 시간..

1. 날씨 확인 (필수*)- 비 내리거나 뿌연 안개가 낀 날에 전망대를 방문하고 싶은 사람은 아무도 없을 것이다.- 방문 하루 전날 날씨를 확인하고, 예약 방문하시는 것을 추천드립니다  개인적으로 아이폰 날씨 어플을 도쿄로 바꿔서 확인하거나, 웹에서 아래 두 사이트 통해 날씨 체크 하였습니다 https://www.accuweather.com/ko/jp/tokyo/226396/june-weather/226396 도쿄, 도쿄, 일본 월별 날씨 | AccuWeatherGet the monthly weather forecast for 도쿄, 도쿄, 일본, including daily high/low, historical averages, to help you plan ahead.www.accuweather.co..