본문 바로가기

분류 전체보기99

유니온 파인드(Union find) 알고리즘 개념 유니온 파인드란 합집합 찾기라는 의미로, 상호 배타적 집합(Disjoint set)이라고도 한다. 여러 노드가 존재할 때, 두 개의 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 해당 알고리즘은 find와 union 연산으로 이루어지며, find는 a가 어떤 집합에 포함되어 있는지 부모를 찾는 연산이고, union은 a와 b가 포함되어 있는 집합을 합치는 연산이다. 설명 노드 번호 1 2 3 4 5 부모 노드 1 2 3 4 5 만약 위와 같이 독립된 노드들이 있을 때 각 노드의 부모는 자기 자신이다. 노드 번호 1 2 3 4 5 부모 노드 1 1 3 4 5 이때 1과 2번 노드를 합친다(union)고 생각해보자. 부모를 합칠 때는 일반적으로 더 작은 노드를 기준으로 합치기 때문에 2의 .. 2021. 10. 10.
코딩테스트 SQL 문법 정리 SELECT 모든 레코드 조회하기 - 오름차순 select * from 테이블명 order by 정렬기준컬럼 asc; - 내림차순 select * from 테이블명 order by 정렬기준컬럼 desc; 조건없는 특정 컬럼 조회하기 select 컬럼명 from 테이블명; 조건있는 특정 컬럼 조회하기 - 값이 일치하는 행 가져오기 select 컬럼명 from 테이블명 where 컬럼명 = "값"; - 값이 일치하지 않는 행 가져오기 select 컬럼명 from 테이블명 where 컬럼명 != "값"; 여러 기준으로 정렬하기 select * from 테이블명 order by 컬럼명1 asc, 컬럼명2 desc; 상위 N개 조회하기 select * from 테이블명 order by 컬럼명 limit N; MA.. 2021. 10. 9.
프로토타입 빈(Prototype Bean) 개요 스프링의 빈은 기본적으로 싱글톤으로 만들어진다. 하나의 빈 오브젝트에 동시에 여러 스레드가 접근하기 때문에 상태 값을 인스턴스 변수에 저장해두지 않고, 의존관계에 있는 빈에 대한 레퍼런스나 읽기전용 값만 저장해둔다. 그렇다면 빈을 싱글톤이 아닌 방법으로 만들 때는 어떻게 해야 할까? 싱글톤이 아닌 빈은 프로토타입 빈과 스코프 빈으로 나눌 수 있다.(싱글톤, 프로토타입도 스코프의 한 종류이다) 스코프(Scope) 존재할 수 있는 범위를 가리키고 빈 스코프는 빈 오브젝트가 만들어져서 존재할 수 있는 범위다. 싱글톤 스코프는 단일 컨테이너 구조에서 컨테이너가 존재한느 범위와 싱글톤이 존재하는 범위가 일치하기 때문에 컨테이너 스코프라고도 부른다. 프로토타입 스코프 싱글톤 스코프는 컨텍스트당 하나의 오브젝트.. 2021. 10. 9.
투포인터(Two Pointers) 알고리즘 개념 투포인터 알고리즘은 리스트에서 순차적으로 접근해야 할 때 두 개의 위치(인덱스)를 기록하면서 처리하는 알고리즘이다. 정렬되어 있는 두 리스트의 합집합에도 사용된다. 두 개의 인덱스 중 하나는 탐색을 할 때마다 반드시 1 증가한다. 어느 인덱스라도 리스트의 크기에 도달해야 하므로 투포인터 알고리즘의 시간복잡도는 O(N)이 된다. 설명 개요 1. 부분합이 찾는 값이거나 오른쪽 인덱스가 (리스트의 크기 - 1)이라면 왼쪽 인덱스를 1 증가시킨다. 2. 부분합이 찾는 값이 아니라면 오른쪽 인덱스를 1 증가시킨다. 3. 위 과정을 왼쪽 인덱스가 (리스트의 크기 - 1)이 될 때까지 반복한다. 구현 구간이 연속적일 때 0 1 2 3 4 5 1 4 2 2 1 2 어떤 숫자들의 리스트가 위와 같이 주어질 때, 해.. 2021. 10. 8.

티스토리툴바