서로소 집합(Disjoint Set)서로소 집합(Disjoint Set)이란?서로 공통된 원소를 갖고 있지 않은 두 개 이상의 집합즉, 교집합이 없는 집합들을 관리하는 자료구조이다. 서로소 집합 자료구조는 서로 다른 원소들이 같은 집합에 속해있는지를 판단하기 위해 사용하는 자료구조이다.서로소 집합엔 MakeSet, Find, Union 세 가지 연산이 있다.MakeSet새로운 집합(parent 배열)을 생성하는 연산 처음 집합을 생성할 때 각 노드는 부모 노드가 없기 때문에 자기 자신을 가르키는 parent 배열을 생성한다.int n = 10; // 노드의 개수int[] parent = new int[n];// 처음 parent 배열을 초기화 할 때는 각 노드가 자기 자신을 가르키도록 설정한다.for (..

Github 레포지토리에 정리되어 있습니다.👨‍💻 개발자 면접을 위한 CS 스터디 : 탄젠트📅 일정 : 2024/09/23 (월) ~📄 목표취업을 위한 면접 CS 스터디를 목표를 한다.Network, OS, Database, Java, Design Pattern을 공부한다.SQLD 자격증 취득을 위해 병행 공부한다.🤔 방법주어진 범위 각자 공부한 내용 깃허브에 .md 파일로 업로드매주 월요일 14:30에 대면으로 만나서, 한 주동안 각자 공부한 내용 공유면접 대비하여 면접 예상 질문과 모범 답안 준비하여 상대방에게 질문매주 스터디가 끝나면 돌아가면서 교내 씨부엉 스터디에 활동일지 업로드또한 Github Issue에 면접 예상 질문 정리해두어, 추후 돌려볼 수 있도록 함큰돌의 CS 지식의 정석 강..

이진 탐색이란?'정렬된 배열(리스트)'에서 탐색 범위를 절반으로 줄여가며 특정 값을 찾는 알고리즘탐색할 때마다 탐색 범위가 절반으로 줄어들기 때문에 '탐색해야 할 데이터의 양이 많을수록 유리'동작 방식동작 방식정렬된 배열의 중간 값을 찾아서 목표 값과 비교한다.목표 값보다 작다면 왼쪽 절반을 탐색하고 크다면 오른쪽 절반을 탐색한다.목표 값과 중간 값이 같을 때까지 위 과정을 반복한다.구현 방법반복문 이용한 방법정렬된 배열의 첫 번째 인덱스를 low로 선언하고 마지막 인덱스를 high로 선언한다.while문을 이용하여 high가 low보다 크거나 같을 때까지 아래 탐색을 실행한다.중간 인덱스(mid)와 중간 값(midValue)를 구한다.중간 값 > 목표 값이라면 왼쪽 배열을 탐색한다.중간 값 이라면 오른..

다이나믹 프로그래밍이란하나의 큰 문제를 여러 개의 작은 문제로 나누어 풀면서 그 결과를 저장해 나가며 큰 문제를 해결할 때 재활용하는 것을 의미한다.DP 사용하는 이유일반적인 재귀 함수의 불필요한 중복 연산을 줄이기 위해 동적 계획법을 사용한다.일반적인 재귀를 사용하면 동일한 작은 문제를 여러 번 반복 하여 계산하기 때문에 비효율적이다.DP는 동일한 작은 문제를 저장(Memoization)해두고 나중에 같은 문제가 나오면 재활용하여 중복 연산을 피할 수 있기 때문에 일반적인 재귀 함수에 비해 효율적으로 계산할 수 있다.피보나치 수열 예시D[12]가 세 번이나 반복해서 계산되었다. 이때 DP를 사용하면 D[12]를 한 번만 계산하고 저장한 후 나중에 재활용하여 사용하기 때문에 훨씬 효율적으로 계산할 수 있..

DFS(Depth First Search)란?한 경로를 끝까지 탐색한 후, 이전 경로로 돌아가서 다른 경로를 탐색하는 방법이다.DFS에서 사용하는 알고리즘은 백트래킹(backtracking) 알고리즘이다. 백트래킹이란 해를 찾아가는 도중 지금 가는 경로가 해가 아니라면 왔던 경로로 되돌아가는 것을 의미한다. 즉, 트리의 마지막 노드에 도달했을 경우 이전 노드로 되돌아가서 새로운 경로를 찾는 것을 의미한다.재귀 함수와 스택을 이용하여 구현한다. 재귀를 이용할 경우 종료 조건을 명시해서 무한 반복에 빠지지 않게 해야 한다.딱 두 가지만 생각하면 된다.DFS 탐색 과정한 경로를 끝까지 탐색한다.마지막 노드에 도달했다면 이전 노드로 돌아가서(backtracking) 탐색하지 않은 노드가 있는지 확인한다.탐색하지..

BFSBFS(Breadth First Search)는 루트 노드에서 시작해서 인접 노드를 먼저 탐색하는 방법이다. 즉, 시작 정점으로부터의 거리가 가까운 정점들부터 차례로 방문해 나가는 방법이다.BFS 특징큐(Queue) 자료구조를 사용하여 구현한다.각 노드들을 방문하면서 방문한 노드와 연결된 노드를 큐에 추가하고 빼면서 한 번씩 탐색한다.회색 노드(큐에 추가), 검정 노드(큐에서 삭제)노드 방문 여부를 체크하지 않으면 무한 반복에 빠질 위험이 있기 때문에 반드시 체크해야 한다.BFS 문제 유형최단 경로 탐색미로 찾기2차원 배열로 주어진 미로에서 시작점에서 출발해 출구까지의 최단 경로 찾기특정 거리 내 노드 탐색소셜 네트워크 탐색특정 거리 내에 있는 친구 찾기전염 확산 모델링전염병이 특정 거리 내에 얼마..