개발 무지렁이

프로그램의 효율성을 따질 때, 시간복잡도와 공간복잡도를 따진다. 시간복잡도 시간복잡도는 간단히 말해서 연산양이다 (연산이 많을 수록 오래걸린다) 빅오 O(N) 최악일때 연산횟수 입력개수(N)에 따른 연산양을 함수로 나타낸 것을 '시간복잡도 함수'라고 한다. 시간복잡도 함수에서 영향이 미미한 정보를 제거, '최악의 경우'의 '증가 추세'만을 나타낸 표기법을 '빅오표기법'이라고 한다 📌 보통 연산양이 1억번(100_000_000)이면 1초가 걸린다

더 맵게 🪅 매번 배열의 원소를 제거하고 넣고, 정렬해야하는 조건에서 우선순위 큐를 생각해 낼 수 있느냐 🪅 같은 동작을 반복해서 해야할 때 이를 메서드로써 만들 수 있느냐 🪅 항상 처음과 끝은 예외상황이 발생할 수 있는 것을 확인했느냐 💡 문제 접근 과정 음식 개수에 따라 scoville 최초 배열의 길이가 달라지고 한 번 스코빌 지수를 섞을 때마다, 배열의 길이가 1씩 줄어든다. 이 조건을 봤을 때 가변길이 배열(ArrayList)을 써야겠다는 생각이 들었다. 이 자료구조를 썼더니 매번 정렬해줘야돼서인지(?) 효율성테스트를 통과하지 못했다. (중간에 모든!! 음식의 스코빌 지수가 K이상이어야하는 조건을 놓쳐서 많이 헤맸다) 즉, 자료구조에 원소를 넣을 때마다 정렬을 해주는 자료구조가 무엇인지 생각해봤..

시간복잡도 알고리즘 수행시간 분석 수행시간은 연산수행횟수에 비례 즉, 문제를 해결하기 위한 연산횟수를 의미한다. (1억번의 연산은 1초의 시간이 걸린다) 시간복잡도 함수 입력개수(N)에 따른 연산수행횟수 빅오 표기법 시간복잡도함수에서 영향이 미미한 정보를 제거하여, 증가추세만을 표기하는 표기법 (최악일 때)

슬라이딩 윈도우(Sliding Window) N개의 원소를 갖는 배열과 w 너비의 창문 창문을 한칸씩 오른쪽으로 이동할 때, (매순간 창문 안에서의 정보 노출 필요) Window를 한칸 옮기면 w-1칸은 겹친다 이전의 결과를 써먹는 방향으로 접근하자 🕑 시간복잡도: O(N) [ 맨 처음 Window에 대해서만 O(w) ] 슬라이딩 윈도우(Sliding Window) 코드 구현 import java.util.*; import java.io.*; class Main { static int[] checkArr; static int[] myArr; static int checkSecret; public static void main(String[] args) throws IOException { Buffered..

동적계획법(Dynamic Programming)의 전제와 정의 ⚠️ 큰문제를 동일한 형태의 작은문제로 나눌 수 있어야 한다. ⚠️ 작은문제에서 구한 값이 그것을 포함하는 큰문제에서도 동일하다. . 하나의 문제는 단 한번만 풀도록 하는 알고리즘을 말한다. 그러기 위해서 이미 구한 답을 잠시 기록해두는 과정을 '메모이제이션'이라고 한다. 🕑 시간복잡도: O(N) 동적계획법(Dynamic Programming)과 피보나치 수열 ❓ 피보나치 수열이란 : 모든 항이 바로 앞 두 항의 합인 수열을 말한다. (단, 첫번째항과 두번째항은 1 이다) import java.util.*; class Main { static int[] A = new int[100]; public static void main(String[]..

계수(Counting) 정렬 위치를 바꿀 필요도 없이, 세기만 하면 된다. 해당 인덱스의 Counting만큼을 출력한다. (⭐. 데이터의 크기가 한정되어 있을 때, 사용) 🕑 시간복잡도: O(N) [ 모든 데이터를 한번씩만 접근하면 된다. ] 계수(Counting) 정렬 코드 구현 import java.util.*; import java.io.*; class Main { static int[] A = new int[] {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1}; static int[] count = new int[6]; public static void main(String[] args..