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

문제 링크 풀이 - 앞서 풀었던 치즈(2638)에서 조건에 맞게 수정하여 풀었으나 마지막 98%에서 '실패했습니다' 확인 https://dev-ljw1126.tistory.com/243 [BOJ 2638] 치즈 (Java, BFS) 문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있 dev-ljw1126.tistory.com - 마찬가지로 공기(0)인 부분에 대해 탐색을 진행하는데, 공기와 접촉한 치즈의 경우 임의 값(2)로 갱신 후 치즈 개수를 카운팅 수행 - while 반복문 시작 하기전 녹아 없어질..

문제 링크 https://www.acmicpc.net/problem/3190 3190번: 뱀'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임www.acmicpc.net풀이- 주어진 조건에 맞게 BFS, 시뮬레이터 구현 하는 문제- Queue를 활용하여 뱀의 위치 정보를 관리하고, 맵 데이터를 갱신 시켜 줌 게임 조건게임은 N * N 보드 위에서 진행되고, 게임이 시작할 때 뱀은 맨위 맨 좌측에 위치하고 뱀의 길이는 1이다.뱀은 맨 처음 오른쪽으로 향한다.뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.- 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨..

문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 - 격자형 그래프 탐색 문제 - BFS 풀이 - N이 최대 50이므로 O(N^2)으로 풀이 가능 예제 입력 4 3 5 10 10 15 20 20 30 25 40 22 10 예제 출력 4 2 1회차 int[][] WORLD 10 15 20 20 30 25 40 22 10 int[][] GROUP_INFO 0 0 0 0 0 0 1 0 2 1회차 인구 이동 결과 20 20..

문제 링크 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 풀이 - 첫 줄 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100) 주어짐 - 치즈 (1), 없는 부분 (0)으로 표시 - 치즈가 모두 녹아 없어지는데 필요한 시간을 출력 - 상,하,좌,우 격자형 그래프 문제 - 시간복잡도 O(N^2) 절차* - 가장 가리(1,1) 위치 부터 시작하여 공기(0)에 대해 BFS 탐색 수행하면 치즈를 만나면 +1 해..