IT LAB

1. Dynamic Programming큰 문제를 작은 문제로 나누어 풀되, 작은 문제의 결과를 저장해두고 재사용하는 알고리즘나중에 같은 부분 문제를 계산하지 않도록 합니다 조건조건명정의의미/핵심 포인트Overlapping Subproblems전체 문제를 나누면 동일한 서브문제가 반복해서 등장같은 계산을 반복하지 않도록 Memoization하여 재사용Optimal Substructure전체 문제의 최적 해가 부분 문제들의 최적 해로 구성됨부분 문제와 전체 문제 사이에 점화식 존재✅ 작은 문제 해결➡️ 이를 조합해 큰 문제 해결 예시) Overlapping Subproblems더보기피보나치 수열F(5)를 구하려면 F(4), F(3)이 필요F(4)를 구하려면 F(3), F(2)가 필요 예시) Optimal ..

1. Anagram길이가 같고, 같은 문자로 구성된 두 문자열을 가리킴 예시stressed→dessertsElvis→lives Permission to dance → Stories on Pandemic 코드더보기private static int CHARACTER_RANGE= 256;public boolean isAnagramCounting(String string1, String string2) { if (string1.length() != string2.length()) { return false; } int count[] = new int[CHARACTER_RANGE]; for (int i = 0; i  2. Palindrom문자열의 중심으로부터 모든 쌍이 대칭되는 ..

소수란?1과 자기 자신으로만 나누어지는 수 입니다. 판정법for (int i = 2; i 2부터 N-1까지 반복합니다.반복하는 숫자가 N으로 나머지 연산하여 0인지 확인합니다. 에라토스테네스의 체특정 범위 내의 소수판정법입니다.반복하면서 합성수를 소거하는 방식입니다. 더보기boolean[] nums = new boolean[N+1];Arrays.fill(nums, true);for (int i = 2; i answer = new ArrayList();for (int k = 2; k  2부터 N까지 반복합니다.현재 방문한 수의 배수를 소수가 아닌 수로 처리합니다. 골드바흐의 추측2보다 큰 모든 짝수는 2개의 소수 합으로 표현 할 수 있음  출처BaaaaaaaarkingDog - 수학

1. Greedy 란?매 순간 가장 좋은 선택을 하는 알고리즘 입니다.근시안적인 방식으로 최적해를 구합니다. 목적많은 연산이 필요한 Dynamic Programming의 효율적인 대안으로 사용하기 위함입니다.사용조건을 만족하면, Dynamic Programming보다 더 효율적으로 해를 구할 수 있습니다. 동작 방식각 단계에서 최적의 답을 선택하므로써 전체적인 최적해를 구하는 방식으로 동작합니다. 사용 조건탐욕적 선택 속성 (greedy choice property)각 단계에서의 선택이 전체 해결책의 최적성을 보장현재 선택이 문제의 나머지 부분에 독립적 (문제의 남은 부분에 대한 탐욕적 기준 유지) 최적 부분 구조 (optimal substructure)문제의 최적해는 전체 문제의 부분문제의 해로 구성됩..

1. Two Pointer정렬된 선형 자료구조에서 조건을 만족하는 구간/쌍을 찾는 알고리즘 입니다.두 개의 포인터를 동시에 움직여가며 문제를 해결합니다. 동작 원리포인터 설정: 두 개의 포인터 배치 (배열의 시작과 끝)포인터 이동: 범위를 좁히거나 넓히는 방식. (한쪽 또는 양쪽 모두를 이동시킴)조건 만족 검사: 두 포인터의 현재 위치에서 조건을 만족하는지 검사 코드더보기int countPairsEqualToM(int[] a, int M) { Arrays.sort(a); int l = 0, r = a.length - 1, cnt = 0; while (l 장점성능: O(n) (반복을 줄여 시간복잡도를 줄임) 2. 문제Two Sum배열 중 조건을 만족하는 숫자쌍 찾기 문제더보기Two Sum..

1. Binary Search 란?정렬된 자료구조에서 원하는 값을 효율적으로 찾는 알고리즘 입니다.✅ 탐색 구간을 절반씩 줄여가며 목표 값을 찾음✅ 주로 Binary Search Tree에서 사용됩니다. 과정중간 원소 선택범위 지정찾고자 하는 값보다 작다면, 배열의 오른쪽 반을 대상으로 이진 검색찾고자 하는 값보다 크다면, 배열의 왼쪽 반을 대상으로 이진 검색찾을때까지 반복 (재귀적) Lower Bound찾고자 하는 값 이상의 원소들 중, 가장 작은 인덱스 값✅ 내부적으로 루프에서 불변식을 유지하면서 범위를 좁혀감➡️ 항상 반개구간을 유지함 [left, right)➡️ left: 거짓인 마지막 구간을 바로 넘어선 위치➡️ right: 항상 참인 최소 위치✅ 배열이 정렬되어 있으므로 판정 함수는 단조적➡️..

1. Selection Sort 리스트에서 가장 작은 원소를 반복적으로 선택하여, 정렬되지 않은 부분의 맨 앞 원소와 교환하는 방식의 알고리즘 과정주어진 리스트 중, 최소값을 찾음pass: 최소값을 맨 앞에 위치한 값과 교체 ➡️ 첫번째 위치가 정렬됨맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 반복 코드더보기public int[] sort(int[] arr) { for (int i = 0; i arr[j]) minIdx = j; } if (minIdx != i) swap(arr, i, minIdx); } return arr;}Time Complexity : O(n^2) 장점교환 횟수 최소화 (최대 n-1번)in-place (추가 메모리 사용 ❌) 단점성능 ..

난이도 : Level 2 문제링크 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶다. 이를 위해 가장 스코빌 지수가 낮은 두개의 음식을 섞어 새로운 음식을 만든다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다 섞어야 하는 최소 횟수를 리턴하라 해설 1. 최소힙을 사용하여 가장 스코빌 지수가 낮은 음식 두개를 꺼냅니다. PriorityQueue pq = new PriorityQueue(); for (int s : scoville) { pq.add(s); } while (pq.size() > 1 && pq.peek() < K) { int min = pq.poll(); ..

난이도 : Level 2 문제링크 H-Index : 논문 n편 중, h번 이상 인용된 논문이 h편 이상,나머지 논문이 h번 이하 인용시, h의 최댓값 논문의 인용 횟수를 담은 배열이 주어질 때, H-Index를 리턴하라 해설 1. H-Index 의 범위는 1 ~ 전체 논문수 입니다. 2. H가 가장 큰 숫자부터 작은수까지 조건을 만족하는지 확인합니다. public int solution(int[] citations) { int answer = 0, size = citations.length; Arrays.sort(citations); for (int i = 0; i = h) { return h; } } return..

난이도 : Level 3 문제링크 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. I 숫자 : 큐에 주어진 숫자를 삽입합니다. D 1 : 큐에서 최댓값을 삭제합니다. D -1 : 큐에서 최솟값을 삭제합니다. 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 리턴 비어있지 않으면 [최댓값, 최솟값] 리턴 해설 1. 두개의 우선순위 큐 사용하기 - 최대힙, 최소힙 PriorityQueue minPq = new PriorityQueue(); PriorityQueue maxPq = new PriorityQueue(Comparator.reverseOrder()); 최소힙 - 최솟값을 항상 루트로 두는 힙 자료구조 최대힙 - 최댓값을 항상 루트로 두는 힙 자료구조 2. 삽입 for (String ..