2023/11/08 6

[기초 알고리즘] String

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문자열의 중심으로부터 모든 쌍이 대칭되는 ..

Algorithm 2023.11.08

[기초 알고리즘] 수학: 소수

소수란?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 - 수학

Algorithm 2023.11.08

[고급 알고리즘] Greedy

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

Algorithm 2023.11.08

[알고리즘] Range: Two Pointer

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..

Algorithm 2023.11.08

[기초 자료구조] Linked List

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

Data Structure 2023.11.08

[기초 자료구조] Array

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

Data Structure 2023.11.08