IT LAB

1. Dynamic Programming복잡한 문제를 작은 문제로 나누어 푸는 알고리즘 입니다.작은 문제의 해를 저장해 나중에 같은 부분 문제를 계산하지 않도록 합니다. 조건중복 부분 문제 구조 (Overlapping Subproblems)전체 문제를 작은 부분 문제들로 나누었을 때, 같은 부분 문제들이 반복됨 Memoization: 작은 문제들의 해를 저장 및 재사용함으로써 중복계산을 방지할 수 있습니다. 최적 부분 구조 (Optimal Substructure)전체 문제의 해가 부분 문제의 해를 이용해 구해질 수 있는 성질부분 문제와 전체 문제간에 의존성이 존재합니다.이러한 의존성을 점화식으로 도출하여 전체 해를 작은 문제의 해의 조합으로 표현할 수 있습니다.작은 문제부터 해결해 나가면서, 점진적으로 ..

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조건을 충족하는 구간 혹은 쌍을 찾는 알고리즘 입니다.두 개의 포인터를 동시에 움직여가며 문제를 해결합니다.정렬된 선형 자료구조에서 사용됩니다.답에 가깝게 접근하기 위한 올바른 포인터 이동을 하기 위해서 동작 원리포인터 설정두 개의 포인터 배치 (배열의 시작과 끝 or 인접한 위치) 포인터 이동범위를 좁히거나 넓히는 방식으로 답을 찾아갑니다. 한쪽 또는 양쪽 모두를 이동시킵니다. 조건 만족 검사두 포인터의 현재 위치에서 조건을 만족하는지 검사합니다. 장점반복을 줄여 시간복잡도를 줄이는 목적을 가지는 알고리즘 입니다.O(n)으로 최적화 가능 2. 문제Two Sum배열 중 조건을 만족하는 숫자쌍 찾기 문제Two Sum 2 - Input Array is sorted (문제) (해설) ..

1. Binary Search 란?정렬된 배열에서 찾고자 하는 요소를 빨리 찾는 알고리즘 입니다.주로 Binary Search Tree에서 사용됩니다. 과정중간 원소 선택범위 지정찾고자 하는 값보다 작다면, 배열의 오른쪽 반을 대상으로 이진 검색찾고자 하는 값보다 크다면, 배열의 왼쪽 반을 대상으로 이진 검색 찾을때까지 반복 (재귀적) Lower Bound값이 해인 인덱스 중, 가장 작은 인덱스 값더보기while (left  Upper Bound해를 초과하는 값 중, 가장 작은 값의 가장 작은 인덱스 값더보기while (left  2. 구현Array더보기public int search(int[] arr, int data) { int l = 0, r = arr.length-1; while (l ..

1. Selection Sortin-place 과정주어진 리스트 중, 최소값을 찾음최소값을 맨 앞에 위치한 값과 교체 (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^2의 시간 복잡도를 가짐안정성 없음 (같은 값이면 순서가 계속 바뀜) 2. Bubble Sort인접한 두 원소를 비교하여, 순서가 잘못되어 있으면 교환하는 방식의 알고리즘i..

난이도 : 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 ..