IT LAB

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. Linked List각 요소들을 연쇄적으로 연결한 선형 자료구조✅ 각 요소마다 이전/다음 노드의 포인터를 보유함✅ Head 포인터: 맨 처음 요소를 가리키는 포인터 (링크드리스트 마다 가지고 있음) Node각 요소를 표현하는 자료구조✅ 구성: 값, next 포인터 (다음 노드를 가리키는 포인터) 장점구분설명장점동적 할당크기가 동적으로 할당됨유연한 메모리 사용 가능메모리 비연속적메모리 연속적이지 않고 흩어져 저장됨✅ 다른 요소에 독립적으로 존재함✅ 각 노드는 next 포인터를 가짐요소 추가/삭제 시 전체 재배치 불필요효율적 연산배열처럼 연속된 메모리를 고려하지 않아도 됨삽입/삭제 등의 연산이 효율적임 단점구분설명단점추가 메모리 비용각 노드가 데이터를 저장할 뿐만 아니라 next 포인터도 가져야 함배열..

1. Array 같은 타입의 요소들을 보관하는 자료구조 입니다.요소들의 중복을 허용합니다. 연속적 (선형적)요소들은 메모리 연속적인 공간에 저장됩니다. (물리적) 인덱스 기반각 요소들은 특정 인덱스에 대응되어 구성되어 있습니다.Random Access 가능합니다. 배열 주소첫번째 요소의 메모리 주소 입니다. 요소 주소기본 주소로부터 현재 요소의 인덱스와 데이터 타입 크기를 곱하여 알 수 있습니다. 정적 할당크기가 생성되는 시기에 정해집니다. 요소 갯수가 배열 크기보다 커질 경우 리사이즈 연산 발생2배 큰 새로운 배열을 생성 + 새 배열에 요소들을 이주 중간 요소의 추가 연산삽입: 삽입할 곳의 공간을 만들기 위해 뒤 요소들을 뒤로 한 칸씩 이동 (right shift)삭제: 삭제한 공간을 메우기 위해 뒤 ..

Docker는 애플리케이션을 개발, 배포 및 실행하기 위한 오픈 플랫폼입니다. 애플리케이션을 인프라에서 분리하여 빠르게 소프트웨어를 제공할 수 있습니다. 코드를 작성하고 프로덕션에서 실행하는 사이의 지연 시간을 크게 줄일 수 있습니다. 1. The Docker platform Docker는 컨테이너라는 약간 격리된 환경에서 애플리케이션을 패키지화하고 실행할 수 있게 합니다. 컨테이너는 경량화되어 있으며, 애플리케이션을 실행하는 데 필요한 모든 것을 포함하므로 호스트에 의존할 필요가 없습니다. 2. What can I use Docker for? Fast, consistent delivery of your applications 개발자가 로컬 컨테이너를 사용하여 표준화된 환경에서 작업할 수 있게 해줍니다...

1. Overview GitHub Actions는 CI/CD 플랫폼입니다. 빌드 - 테스트 - 배포 를 자동화할 수 있습니다. Repository의 다양한 이벤트가 발생할 때 Workflow를 실행합니다. 데이터 센터나 클라우드 인프라를 사용하기 위한 Virtual Machine을 호스팅해줍니다. 2. The Components of GitHub Actions Workflow는 저장소에서 발생하는 이벤트에 따라 트리거 될 수 있습니다. Workflow에는 하나 이상의 Job이 포함되면 각 Job은 다양한 Step을 포함합니다. 작업은 가상 머신 러너나 컨테이너 내에서 실행됩니다. Action은 Workflow를 단순화하기 위한 재사용 가능한 확장 기능입니다. 3. Create an example work..

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 (추가 메모리 사용 ❌) 단점성능 ..

1. Heap 이란?최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조 입니다.완전 이진트리 기반 입니다.우선순위 큐 구현에 사용됩니다. 완전 이진트리마지막 레벨을 제외한 모든 노드가 채워져 있는 이진트리 자료구조 입니다.마지막 레벨은 왼쪽부터 채워져 있어야 합니다. 인덱스모든 노드를 배열로 표현할 수 있습니다.노드 간 관계를 배열 인덱스를 통해 접근할 수 있습니다.왼쪽 자식 노드 indexindex*2 + 1오른쪽 자식 노드 index index*2 + 2부모 노드 index(index-1) / 2 2. 종류최대 힙부모 노드가 자식 노드보다 크거나 같은 값을 가집니다. 최소 힙부모 노드가 자식 노드보다 작거나 같은 값을 가집니다. 3. 연산Heapify전체 배열을 힙 구조로 만드는 연산입니다.리..

1. Trie 란?문자열 탐색에 최적화된 트리 자료구조 입니다.1959년 Edward Frendkin에 의해 처음 소개되었습니다. 2. 기능사전 검색완전한 단어나 문구를 입력하여 해당 단어를 찾아냅니다. 접두사 검색뿌리부터 시작해서 각각의 가지가 알파벳 문자를 표현합니다.표시된 노드까지 문자열을 이루고 있음을 마크해둡니다. (각 단어가 끝나는 지점에 표시)자동완성 기능을 구현할 수 있습니다. 3. 구현더보기public class MyTrie { class Node { Map children; boolean endOfWord; Node() { this.children = new HashMap(); this...