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. 소수소수란?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 2부터 N까지 반복합니다.현재 방문한 수의 배수를 소수가 아닌 수로 처리합니다. 골드바흐의 추측2보다 큰 모든 짝수는 2개의 소수 합으로 표현 할 수 있음 2. 최대공약수약수어떤 수를 나누어 떨어지게 하는 수 입니다.약수끼리 곱이 N이 되게끔 짝을 지을 수 있습니다. 최대공약수두 자연수의 공통된 약수 중에서..

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

1. Two Pointer 란? 두 개의 포인터를 동시에 움직여가며 문제를 해결하는 알고리즘 입니다. 조건을 충족하는 한 쌍의 값을 찾는데 사용합니다. 정렬된 선형 데이터에서 사용됩니다. 특징 반복을 줄여 시간복잡도를 줄이는 목적을 가지는 알고리즘 입니다. 2. 사용 사례 Two Sum 배열 중 조건을 만족하는 숫자쌍 찾기 문제 Two Sum 2 - Input Array is sorted (문제) (해설) Sliding Window 조건에 만족하는 subarray 찾기 일정한 크기의 구간을 움직여 문제를 해결합니다. 문제 Minimum Size Subarray Sum (문제) (해설) Longest Substring Without Repeating Characters (문제) (해설) Fast / Slo..

1. Binary Search 란? 정렬된 배열에서 찾고자 하는 요소를 빨리 찾는 알고리즘 입니다. Binary Search Tree에서 자주 사용됩니다. 동작원리 배열의 중간 원소를 선택합니다. 이 원소가 찾고자 하는 값과 같다면 검색은 종료됩니다. 만약 중간 원소가 찾고자 하는 값보다 작다면, 배열의 오른쪽 반을 대상으로 이진 검색을 계속 진행합니다. 만약 중간 원소가 찾고자 하는 값보다 크다면, 배열의 왼쪽 반을 대상으로 이진 검색을 계속 진행합니다. 배열의 크기가 0이 될 때까지 원하는 값을 찾지 못하면, 해당 원소는 배열 내에 없는 것으로 판단합니다. 2. 구현 Array public class BinarySearch { public int search(int[] arr, int data) { ..

1. 정렬이란? 주어진 데이터를 기준에 따라 순서대로 배열하는 알고리즘 입니다. 알고리즘과 자료구조의 기초입니다. 자료구조를 최적화할 수 있습니다. 데이터를 보다 빠르게 찾을 수 있습니다. 코드를 간결하게 만들어줍니다. 2. 선택 정렬 배열에서 가장 작은 값을 선택하여 맨 앞자리 원소와 자리를 교환합니다. 맨 앞자리로 옮겨진 원소는 정렬이 끝날때까지 그 자리를 지킵니다. 첫번째 원소를 제외한 나머지 원소들을 대상으로 교환을 반복합니다. public int[] sort(int[] arr) { for (int i = 0; i arr[j])..

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