IT LAB

1. Divide and Conquer전체 문제를 하위 문제로 나누고, 하위 문제들을 각각 해결한 후, 각 문제의 해를 결합하여 문제를 해결하는 알고리즘 동작 원리분할: 원래의 문제를 여러 하위 문제로 나누기 (하위 문제는 원래 문제와 비슷함)정복: 각 하위 문제를 해결하기 (재귀적으로 반복)결합: 하위 문제의 해결책들을 결합하여 원래 문제의 해 찾기 장점성능: 병렬 처리 가능 (서로 독립적) 2. Merge Sort주어진 두 리스트를 하나의 정렬된 리스트로 병합하는 알고리즘 입니다.재귀적으로 반복하면서 전체를 정렬하는 방식입니다. 동작 방식분할: 리스트를 반으로 나눕니다.정복: 각 부분 리스트를 정렬합니다.병합: 부분 리스트들을 하나의 정렬된 리스트로 병합합니다. 3. Binary Search정렬된 리..

1. Dijkstra Algorithm시작 정점으로부터 다른 모든 정점까지의 최단 경로를 찾는 알고리즘✅ 음수 가중치가 없는 그래프 (양수 or 0) Greedy가장 짧은 거리를 가진 정점을 하나씩 확정해 나갑니다.✅ 우선순위 큐와 인접 리스트를 사용하여 구현합니다. 2. 동작 원리각 정점마다 출발지로부터의 최단 거리를 저장하며 탐색을 진행합니다. 초기화✅ 출발지 거리 = 0 (자기 자신에서 출발하므로)✅ 모든 교차점의 거리 = INF (현재 해당 교차로로 가는 최단 거리를 모름) 완화현재 정점과 연결된 모든 이웃 정점에 대해 기존 거리보다 더 짧은 경로인지 확인합니다.➡️ 기존 거리보다 더 짧은 경로라면, 그 경로로 거리 값을 갱신합니다 반복우선순위 큐가 비거나, 모든 최단 거리가 확정될 때까지 완화 ..

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(); ..