Jin's Dev Story

💡 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될 때까지 작동하는 방법 → 최대공약수 최대 공약수 두 수의 공통된 “약수 중에서 가장 큰 수” 재귀 방식 // 재귀 방식 public static int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } 반복문 방식 // 반복문 방식 public static int gcd(int a, int b) { while (b != 0) { int temp = b; b = a % b; a = temp; } return a; } 최소 공배수 두 수의 공통된 “배수 중에서 가장 작은 수” public static i..

💡 모든 경우의 수를 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 모든 영역을 전체 탐색하는 방법 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)가 기본적인 도구이다. ⇒ Ex) 4자리의 암호를 하나씩 대입하여 푸는 것

깊이우선탐색 - DFS 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 → 정점의 자식들을 먼저 탐색하는 방식 스택 자기 자신을 호출하는 순환 알고리즘의 형태를 지님 인접리스트로 표현된 그래프 : O(N+E) 인접 행렬로 표현된 그래프 : O(N^2) public class DFS { public static void main(String[] args) { HashMap graph = new HashMap(); graph.put("A", new ArrayList(Arrays.asList("B", "C"))); graph.put("B", new ArrayList(Arrays.asList("A", "D"))); graph.put("C", new ArrayList(Arrays.asList("A", "G",..

와일드카드 ?의 의미는 알 수 없는 타입이고 모든 타입이 될 수 있음 제네릭 타입을 사용하고 싶지만, 들어오는 실제 타입 매개변수가 무엇인지 신경쓰고 싶지 않다면 와일드카드()를 사용함 제네릭 타입와 와일드 카드의 차이 제네릭 : 타입을 모르지만, 타입이 정해지면 그 타입의 특성에 맞게 사용함 와일드 카드 : 무슨 타입인지 모르고, 무슨 타입인지 신경쓰지 않음. 타입을 확정하지 않고 가능성을 열어둠 interface Drink{ } class Coffee implements Drink{ } class Milk implements Drink{ } public class GenericTest { private void test1(final List

제네릭(generic) 데이터의 타입을 일반화한다는 것을 의미 클래스나 메소드에서 사용할 내부 데이터 타입을 컴파일 시에 미리 지정하는 방법 제네릭 장점 클래스나 메소드 내부에서 사용되는 객체의 타입 안정성을 높일 수 있음 반환값에 대한 타입 변환 및 타입 검사에 들어가는 노력을 줄일 수 있음 제네릭의 선언 및 생성 class MyArray { T element; void setElement(T element) { this.element = element; } T getElement() { return element; } } public void test(){ List example = new ArrayList(); method1(example); // 제네릭 타입이 일치하지 않기 때문에 컴파일 에러 발..

알고리즘의 복잡도를 판단하는 척도는 시간 복잡도와 공간 복잡도가 있음 그 중 시간 복잡도는 알고리즘 내 연산의 횟수와 밀접한 관계가 있음 시간 복잡도 표기법 Big-O(빅 오) 표기법 알고리즘 최악의 실행 시간을 표기함 가장 많이 사용하는 표기법 최소한 보장되는 성능을 표기 Big-Ω(빅 오메가) 표기법 알고리즘 최상의 실행 시간을 표기 Big-θ(빅 세타) 표기법 알고리즘 평균 실행 시간을 표기 x축 → 자료 입력 개수, y축 → 시간 실행 속도 O(1) → O(log N) → O(N) → O(N log N) → O(N^2) → O(2^N) 빅오 표기법의 특징 상수항(영향력 없는 항) 무시 : O(N + 1) → O(N)으로 표기 계수 무시 : O(2N) → O(N)으로 표기 최고차항만 표기 : O(3..