📌 키워드 이분 탐색 📌 문제 분석 시간복잡도 생각 안하면 어떻게 풀 수있을까? 최대 길이 만큼 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 { ..

✔️  오늘의 키워드 dp 메모이제이션dfs ✔️  문제  및  풀이  피보나치 수열 문제와 거의 동일하고 n   나는 일단 두가지 방식으로 풀어보았다.  1. dfs() with memoization입력 : 자연수 n (1~116)로직 : dfs를 사용하여 재귀적으로 탐색, 중복 계산 방지를 위해 배열에 결과 저장 , f(n) = f(n-1) + f(n-3)연산 수행  메모이 제이션을 활용하지 않고 재귀로만 구현했다면 O(2^n)이었겠지만 메모이제이션을 활용하여 중복된 연산을 수행하지 않음. 즉, Cache 값이 없는 경우에만 연산을 수행한다는 것이다. => O(n) 출력 : 피보나치 비스무리한 수열 f(n) = f(n-1) + f(n-3)의 결과 2. dp입력 : 자연수 n (1~116)로직 :  4..

오늘의 학습 키워드 - Priority Queue - Sort() 문제 Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Example 1:Input: nums = [1,1,1,2,2,3], k = 2Output: [1,2]Example 2:Input: nums = [1], k = 1Output: [1] Constraints: 1 -104 k is in the range [1, the number of unique elements in the array].It is guaranteed that the answer is unique.Fol..