코린이

이진검색트리 (22강) insert, erase, find, update → O(log N) 내부적으로 원소가 크기 순으로 정렬되어 있음 (★장점) 자가 균형 트리를 사용해야 O(log N)이 보장 됨 (편향된 트리 때문) STL - set, multiset, map set에서는 원소가 정렬되어있기 때문에 unordered_set과 달리 대소비교해서 값 찾는 연산이 O(log N)에 가능 iterator를 활용하여 prev, next, advance, lower_bound, upper_bound, find등의 연산이 O(log N)에 제공 O(log N)이지만 다른 O(log N) 연산에 비해 느린편임. 우선순위 큐 (23강) pop을 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원..

해시 (21강) 해시함수 : 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 충돌문제 발생 (해시에 성능에 큰 영향) 충돌 회피 1 - Chaining 충돌 회피 2 - Open addressing - Linear Probing 충돌 발생 시 오른쪽으로 1칸씩 이동하는 방식 장점 - Cache hit rate가 높다. 단점 - Clustering이 생겨 성능에 영향을 줄 수 있다. - Quadratic probing 충돌 발생 시 오른쪽으로 1,3,5,... 칸씩 이동하는 방식 장점 - Cache hit rate가 나쁘지 않다, Clustering을 어느 정도 회피할 수 있다. 단점 - 해시 값이 같을 경우 여전히 Clustering이 발생한다. - Double Hashing 충돌 발생 시 ..

투 포인터 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개 포인터의 움직임으로 O(N)에 해결하는 알고리즘 i = 0일 때의 정보를 i = 1일 때 활용 (포인터의 이동으로 정보를 관리) 이분탐색으로 투 포인터 문제를 풀 수 있는 경우가 많음 반대로 투 포인터 문제를 이분 탐색으로 풀 수 있는 경우도 많음 이전의 정보를 활용하여 시간복잡도를 확 줄일 수 있음 인덱스 하나차이로 실수하는 경우가 많음.. 주의하기

18강 (수학) 소수 판정법 소수 = 1과 자기 자신으로만 나누어지는 수 = 약수가 2개인 수 = 2부터 n-1까지의 수로 나누어지지 않는 수 O(n) O(sqrt(n))의 방법? → 합성수 n에서 1을 제외한 가장 작은 약수는 sqrt(n) 이하이다. → 따라서 2부터 sqrt(n) 까지만 나눠보면 됨 하지만, sqrt(n)은 오차가 발생할 수 있음 (실수연산이기 때문) → for문이 계속될 조건을 i*i

16강 (DP) 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정의하기 초기값이 어디인지를 잘 생각해서 적용해주어야 함 구현이 짧은 편 D[i][j] (2차원으로 선언 하는 이유? , 지금까지 몇 개의 계단을 밟았는지에 대한 정보가 있어야 하므로) 직접적인 값 or 추상화(D[K][1]) 관점을 달리 하면 또 다른 방식으로 DP식이 도출될 수 있음 2차원 배열을 잘 활용해서 여러 조건을 관리하기 DP에서의 경로추적 → 값 테이블 이외에 경로 복원용 테이블을 하나 만들어서 관리 복원용 테이블의 INDEX를 타고가서 1에 도달할 때 까지 출력 후 종료 17강 (그리디) 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘 이상적인 풀이 흐름 1. 관찰을 통해 ..

정렬I (14강) *max_element(arr, arr+k) → arr[0], arr[1], ..., arr[k-1]에서 최댓값인 원소의 주소를 반환(+참조) 선택정렬, 버블정렬, 삽입정렬 O(N^2) Merge Sort O(NlogN) Stable Sort 우선순위가 같은 원소들끼리는 원래의 순서를 따라가도록 하는 정렬 Quick Sort O(NlogN) - 코딩테스트에서 STL을 못 쓰게 하고 직접 구현해서 정렬을 사용해야 한다면 Quick Sort 구현하지말고 다른 방식으로 퀵소트의 장점은 추가적인 공간이 필요하지 않다는 점, cache hit rate가 높아서 속도가 빠름 → 추가적인 공간을 사용하지 않고(In-Place Sort) pivot을 제자리로 보내는 방법 필요, stable sort가..

JPA(Java Persistent API)란? JPA는 자바 ORM(Object Relational Mapping) 기술에 대한 API 표준 명세를 뜻한다. JPA는 라이브러리가 아닌 ORM을 사용하기 위한 인터페이스의 모음이다. ORM이란? ORM은 말 그대로 객체와 관계형 데이터 베이스를 매핑해 주는 기술이다. 객체는 객체대로, 관계형 데이터 베이스는 관계형 데이터베이스대로 설계하고, ORM 프레임워크가 중간에서 매핑을 해준다. Hibernate란? Hibernate는 JPA를 구현한 구현체이다. 개발된 지 10년이 넘었으며 대중적으로 많이 이용되는 JPA 구현체 중 하나이다. JPA의 핵심들인 EntityManagerFactory, EntityManager, EntityTransaction 등을 ..

JDBC프로그래밍을 좀 더 쉽게 하기 위해 제작된 프레임워크로 XML 설명자나 주석을 사용하여 저장 프로시저 또는 SQL문과 객체를 결합함으로써 객체 관계 매핑에 도움을 준다. Mybatis는 데이터베이스에 액세스하는 작접을 캡슐화하고 JDBC 코드 및 매개 변수의 중복작업을 제거한다. 특징 - 복잡한 쿼리나 다이나믹한 쿼리에 강하지만 반대로 비슷한 쿼리는 남발하게 되는 단점이 있다. - 프로그램 코드와 SQL 쿼리의 분리로 코드의 간결성 및 유지보수성이 향상된다. - resultType, resultClass등 VO를 사용하지 않고 조회결과를 사용자 정의 DTO, MAP등으로 매핑하여 사용할 수 있다. - 빠른 개발이 가능하여 생산성이 향상된다. MyBatis의 DB Access Architecture..