계란 블로그

1. 집합 (Set) - 선형 데이터 구조 + 탐색 알고리즘 - list와 다르게 set은 중복을 허락하지 않는다. - set은 순서를 보장하지 않는다. - 합집합: setA.addAll(setB) - B의 원소를 모두 A에 추가한다. - 차집합: setA.removeAll(setB) - A에서 B의 원소 모두 제거 - 교집합: setA.retainAll(setB) Ex) Set 연습 import java.util.LinkedHashSet; import java.util.Objects; import java.util.Set; class MyData{ int v; public MyData(int v) { this.v = v; } public String toString() { return "" + v; }..

1. Map - Map은 array와 list의 장점만 모아놓았다. Def) hashing - key를 범위(배열 크기)에 맞게 적절이 겹치지 않는 index로 변경한다. Ex) import java.util.Hashtable; public interface MapP { public static void main(String[] args) { Hashtable map = new Hashtable(); map.put("A", 1); map.put("B", 2); map.replace("A", 11); System.out.println(map.remove("B", 3)); // map에 B,2가 있으면 삭제된다. System.out.println(map); System.out.println(map.get("..

1. Array - 여러개의 데이터를 한 번에 다룰 수 있다. - Object는 아니지만 Reference Value로 취급된다. - 메모리상에 연달아 공간을 확보한다. - 미리 공간을 확보해 놓고 써야한다. - 단점 - 한 번 만들어진 공간은 크기가 고정된다. - 단점 - 첫 번째 위치만 알면 index로 상대적 위치를 빠르게 찾을 수 있다. -> array의 단점을 보완하기 위해 list가 등장 - System.out.println(Arrays.toString(배열명))을 이용해야 배열의 내용 출력 가능 2. List - 데이터를 추가: link를 늘린다. - LinkedList: 데이터를 서로 Link로 연결한다. - 데이터 삭제: link를 없앤다. - 양쪽으로 연결: double linked l..

1. primitive (기본형) - 자바는 기본형마다 래퍼 클래스 제공 - 자바에서는 string을 immutable 데이터로 취급 - call by value: value값이 그대로 전달된다. - call by reference 2. 시간 복잡도 (O(n)) Def) 시간 복잡도: 입력되는 데이터의 증가에 따른 성능의 변화를 예측 -> 작업량(시간 복잡도): 얼마나 적은 연산으로 결과를 만들어 내는가 Note) 메모리 사용량(공간 복잡도): 얼마나 적은 메모리를 사용하여 결과를 만드는가 ->Big O 표기법: O(n) -> O(1): 연산의 양이 변하지 않고 그대로 일 때 -> O(n): n에 비례하여 처리횟수가 증가하는 경우 -> O(n^2): -> O(log n): 입력 데이터가 n개 일 때, 처..

Def) 서브 쿼리: SQL문 (주로 SELECT문) 안에 포함되는 SELECT문 - 질의문 / 갱신문 위치에 사용가능하다. 1. 주의 사항 1) 컬럼참조 시 주의 사항: 메인쿼리에서 볼 때, 서브쿼리는 블랙 박스 - inline view(FROM절 서브쿼리)의 경우, 메인쿼리는 inline view의 컬럼을 자유롭게 참조한다. 2) ORDER BY절 사용 제한 - WHERE절 서브쿼리에서는 ORDER BY절을 사용하지 못한다. - inline view의 경우, 사용 가능. - WHERE절 서브쿼리 1) 단일값 서브쿼리 (scalar sunquery) 2) 다중값 서브쿼리 (column subquery): ANY | SOME | ALL 3) 다중행 서브쿼리 (table subquery): 여러 개의 투플..

1. 동적 계획법(Dynamic Programming, DP) - 특별한 속성을 가진 복잡한 문제를 푸는 방법 - 단순한 하위 문제를 나눠서 푼다. Ex) 배낭 문제 - 물품 하나가 추가될 때마다 경우의 수가 2배씩 늘어난다. - 시간복잡도: O(2^n) 2. 메모이제이션(memoization) - 계산 결과를 캐시에 저장해둔 뒤, 나중에 재사용하는 기법 -> 처음 계산할 때, 그 결과를 캐시에 저장한다. - 메모이제이션에 "배열"이 가장 적합하다. -> 배열은 매개변수에 대해 값을 저장할 수 있다. Ex) 메모이제이션을 사용한 피보나치 함수 public static int fibonacciRecursive(int number, int [] cache) { if(number 동적 계획에서 메모이제이션이 ..

2022-03-19 프로그래머스 4주차 강의 1. 3주차 세션 리뷰 1.0. 지난 과제 리뷰 - DB에서 가장 중요한 개념 "JOIN"을 활용하는 문제로 구성됐다. - JOIN을 완벽히 이해해야 서브쿼리 알 수 있다. - 99%의 조인은 PK, FK 사이에서 이뤄진다. - 프로그래밍에서 for반복문이 중첩되서 돌아가는 것과 같다. - where절 조인은 검색 조건과 조인 조건이 섞여 있어서 가능하다면 FROM절 조인을 쓰는 게 좋다. - 과제할 때 WHERE절에 조인 조건을 깜빡해서 오답이 있었다. - LEFT JOIN에 WHERE 절을 적용하면 조인의 의미가 사라진다. -> customers LEFT JOIN payments ... 하면 결제액 없는 고객도 출력 - OUTER JOIN에 WHERE절을 ..

Ex) 첫째줄에 N이 입력된다. (1N개가 입력된다. 출처: https://codeup.kr/problem.php?id=3102 package D220316; import java.util.Scanner; interface IStackble100{ boolean empty(); void push(int nData); int peek(); void pop(); void print(); } public class STL implements IStackble100{ private int[] mnArray; private int mnCapacity; private int mnTop; public STL (int nCapacity) { mnArray = new int[nCapacity]; mnCapacity = ..

1. 깊이 우선 탐색 (DFS, Depth-First Search) - 한 우물부터 깊이 판다. - 스택 이용 Ex) //깊이 우선 탐색 코드 public static void SearchDepthFirst(Node node) { Stack stack = new Stack(); stack.push(node); while(!stack.empty()) {// 스택이 비는 순간 끝 Node next = stack.pop(); System.out.println(next.data);// 방문해서 출력 for(Node child : next.children ) { stack.push(child); } } } 2. 너비 우선 탐색 (BFS, Breadth-First Search) - 여러 우물을 동시에 같은 깊이로 ..

1. 트리 - 널리 이용되는 자료구조 중 하나 - 나무의 "계층적" 구조를 표현한다. Def) 노트(node): 실제로 저장하는 데이터 Def) 루트(root): 최상위에 위치한 데이터 Def) 리프(leaf): 마지막에 위치한 데이터들 - 부모와 자식 관계(부모는 언제나 하나, 자식은 없거나 여러개 가능) - 높이: 어떤 노드->리프 경로의 최대 길이 -> 부모 기준으로 아래 3개 있으면 높이가 3 - 깊이: 어떤 노드->루트 경로의 길이 -> 자식기준으로 위에 3개 있으면 깊이가 3 - 하위 트리(subtree): 어떤 노드 아래의 모든 것을 포함하는 트리 2. 트리의 용도 - 계층적 데이터를 표현 - 검색트리를 통해 검색 알고리즘 구현 가능 Ex) 트리의 저장법 public class Node{ p..