📌 키워드 Dynamic Programming 📌 문제 요약Middler : 리그 오브 레전설 (BOJ,S2) : https://www.acmicpc.net/problem/17271dp는 아직 감이 없는 것 같다. 이게 완탐, dfs ,, 짱구 굴리다가 아무리 생각해도 시간 내에 안될 것 같아 힌트를 보니 dp.. ㅎㅎ 그래도 이번 풀이를 통해서 dp에 익숙해지고 있는 것 같다. N초 동안 게임이 이루어진다. 1초 동안 A의 스킬을 시전할 수 있고, M초 동안 B의 스킬을 시전할 수 있다. N초의 시간 동안, 스킬이 멈추어서는 안된다. 연달아 사용해야 한다는 뜻. 📌 문제 풀이dp[i] 정의 : i 초 동안 시전 가능한 스킬의 조합. i i >= m 일때 : dp[i] = dp[i-1] ..

📌 키워드 문자열 스플릿 📌 문제 및 요약 Middler : jaden case 문자열 만들기 📌 Middler : JadenCase 문자열 만들기 문제에서 중요 키워드를 놓치고 split() 함수를 제대로 이해하지 못한 이슈로 조금 헤맸던 문제다. 단어의 첫글자가 대문자로 시작하도록 문자열을 만드는 간단한 문제였는데 "공백이 연속으로 나올 있을 수 있다." 는 문장을 못봤다. 간단 한 문제라서 정리하지 않고 바로 코딩으로 도입했는데 중요 요소를 놓쳤다. 쉬워보여도 입력, 로직, 출력을 제대로 정리하고 들어가야겠구나를 다시한번 느꼈다. "공백 문자가 연속으로 나올 수 있습니다." => "공백 문자가 문자열의 앞 뒤로 나올 수 있습니다. 공백의 갯수를 유지해주세요" 처음에는 String.spl..

📌 키워드 이분 탐색 📌 문제 분석 시간복잡도 생각 안하면 어떻게 풀 수있을까? 최대 길이 만큼 Max(L) 반복을 하며, 주어진 과자(N)개에 대해 각 길이로 나누었을때 조카의 수만큼 동일한 길이로 줄 수 있는지 확인한다. 이 경우, 최악의 경우 Max(L) * N 으로 1초 이내에 풀이 할 수 없다. 그렇다면 탐색의 횟수를 줄여야 하는데, 어떻게 줄일 수 있을까? 나의 경우에는 이분 탐색 방법을 썼다. Max(L) 만큼 탐색하는 것이 아니라 탐색의 범위를 반씩 줄여나가면서 log(Max(L)) = 9 (사실은 밑이 2라서 조금 더 크긴 하다.) 의 시간으로 줄인다. 개인적이로 이분탐색은 정말 획기적인 알고리즘중 하나라고 생각한다. 따라서 예상되는 최종 시간 복잡도는 O(Nlog(Ma..

오늘의 키워드 그래프 이론 그래프 탐색 깊이 우선 탐색 너비 우선 탐색 문제 파악 지난번 4일차에 풀었던 배경화면 정리하기 문제와 거의 유사한 문제이다. 하나의 노드를 탐색할때, 지난 문제에서는 대각선을 제외한 위치를 인접 노드라고 인식했다면, 이번에는 하나의 격자를 둘러썬 모든 격자를 인접 노드로 보면 된다.  문제 해결 방법 입력으로 w(너비), h(높이)와 땅/바다 정보가 주어진다.이중 for문으로 전체 지도를 순회하며, 땅(1)을 발견하면 dfs() 함수를 호출해 인접한 모든 땅을 탐색하고, 방문 처리를 해준다.하나의 DFS 탐색이 끝났다는 것은 하나의 섬을 다 방문한 것이므로 cnt++로 섬의 개수를 증가시킨다.방향 벡터를 8방향(상, 하, 좌, 우, 대각선 포함)으로 설정하여, 대각선으로 연결..

📌 오늘의 키워드 누적 합투 포인터슬라이딩 윈도우 📌 문제 파악   방법 1.  O(N**2)일단 그냥 시간 복잡도 고려하지 않고 생각나는건 2중 포문입니다. 근데 K가 N에 가까워 지는 순간 시간 복잡도는 최악의 경우 O(NK) -> O(N**2)이 된다. 그러면 당연히~ 1초 넘는다.  방법 2.  O(N)그러면 어떻게 풀 수 있을까 내가 생각한 방식은 슬라이딩 윈도우다. 인덱스 0번 지점부터 k-1번까지 미리 누적합을 구해둔 후, 윈도우를 한칸씩 밀어나가는거다. 그러면 탐색 과정에서 바로 직전의 인덱스를 제외하고, i + k 번째 값을 추가하면 된다. 그러면 2중 포문이 아니라 단일 포문으로 가능해지는 것이다.   📌 코드 import java.io.BufferedReader;import ja..

📌  키워드 완전 탐색 시뮬레이션최대 최소📌  문제 탐색 문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/161990입력n X m 의 크기를 갖는 격자판에 #, . 으로 각각 파일, 빈 격자판이 String 1차원 배열로 입력된다.  출력 드래그의 시작점과 끝점을 담은 정수 배열 로직시작점 찾기 : 파일이 위치한 최소의 x축, y축의 교차점 (min_y_index, min_x_index)끝점 찾기 : 파일이 위치한 최소의 x축, y축의 교차점 (max_y_index+1, max_x_index+1)2중 포문을 돌면서 min_y, min_x, max_y, max_x 갱신코드import java.util.*; class Solution { ..