회고장

👣 개요 코딩 테스트에 자주 나오는 보일러플레이트 기록. [특정 행렬 회전시키기] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 👣 코드 기본 아이디어 자리를 한 칸씩 옮기기 위해 swap처럼 임시 공간[tmp]을 하나 마련하고 1회전 하면서 tmp과 table[x][y]을 swap한다. 그리고 최종 마지막으로 최초 시작점과 tmp을 맞바꾸며 종료. int rotate(T[][] table, int x1, int x2, int y1, int y2) { T swap=0; // 순수 swap을 위한 공간 T tmp=0; // 회전을 위한 임시 공간 int x..

B-tree 역시 'AVL 트리'와 '레드 블랙 트리'와 같이 Balanced Tree이다. 다만 균형 이진 탐색 트리는 아니다. B-tree는 앞서 살펴봤던 트리들과는 달리 Node당 1 개 이상의 데이터가 포함된다. Node 안은 여러 개의 Key로 이뤄져 있다. 그리고 B-tree는 차수라는 속성을 가지고 있다. 이는 한 Node의 최대 자식 Node 갯수를 의미한다. B-tree는 높이를 최소화하기 위해 노드의 분할과 병합을 수행한다. 주로 DB의 인덱스를 구현하기 위해 사용되는 자료 구조다. 👣 B-tree 조건 1. node의 key의 수가 k개라면, 자식 node의 수는 k+1개이다. ["Key 갯수" + 1 = "자식 Node 수"] 2. node의 key는 오름차순으로 정렬된 상태여야 한..

(Key, Value) 로 데이터를 저장하는 자료 구조. 해시 함수에 Key 값을 입력하면 Value를 저장할 메모리의 Index가 결과값으로 도출된다. 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다. 랜덤 탐색, 삽입, 삭제 모두 O(1)라는 성능을 보여준다는 장점이 있지만, 순차 탐색이 불가능하고 해시 함수에 따라 성능이 좌지우지 된다. 최악의 경우 연결 리스트와 다를 바가 없어진다. Random Read Sequential Read Insert Delete 시간 복잡도 O(1) X O(1) O(1) 해시 충돌 제아무리 해시 함수를 잘 구축해도 해시 함수 결과값이 중복될 수 있다. 이 경우, 2 가지 방법으로 해결 가능하다. 1. 분리 연결법(Separate Chaining) 단순하게 연결 리..

완전 이진 트리의 자료 구조. 이진 탐색 트리는 아니다. 최소힙과 최대힙으로 나뉠 수 있다. 해당 트리는 최소값, 최대값을 찾기에 특화되어 있는 자료 구조다. 최소값과 최대값은 각각 최소힙과 최대힙의 루트 노드다. 최대힙의 법칙 힙의 모든 부모 노드는 자식 노드보다 크다. 최대힙의 삽입 1. 새로운 노드를 마지막에 삽입. 2. 새로운 노드를 부모 노드와 비교하며 최대힙의 법칙을 위반하면 Swap 한다. 3. 위 과정이 안정화가 될 때까지 재귀적으로 반복한다. 최대힙의 삭제 1. 루트 노드를 삭제. 2. 마지막 노드를 루트 노드에 위치시킴. 3. 루트 노드를 자식 노드와 비교하며 최대힙의 법칙을 위반하면 Swap 한다. 단, Swap 대상은 자식 노드 중 가장 큰 노드이다. 4. 위 과정이 안정화가 될 때..

균형 이진 탐색 트리를 위해 고안된 자료 구조. 각 노드는 빨간색, 검은색 색상을 나타내는 추가 비트를 저장하며, 삽입, 삭제 중에 균형을 유지하기 위해 사용된다. 레드 블랙 트리 규칙 1. 모든 리프 노드와 루트 노드는 블랙이다. 2. 모든 레드 노드의 자식 노드는 블랙이다. 3. 모든 리프 노드의 Black Dept는 같은 값이다. 레드 블랙 트리 삽입 1. 항상 모든 새로운 삽입은 레드 노드로 삽입한다. 2. 조부모 노드를 G, 부모 노드를 P, 삼촌 노드(조부모 노드 중 부모 노드가 아닌 것)은 U, 새로 삽입된 노드를 N이라고 칭한다. 이 때, U가 블랙이면 Restructuring을 수행, U가 레드라면 Recoloring을 수행. 3 - 1. Restructuring은 다음과 과정과 같다. ..

이진 탐색 트리의 최악의 경우를 피하기 위해 스스로 균형있는 트리로 변형되는 이진 탐색 트리. AVL 트리는 모든 노드의 Balence Factor가 [-1, 0, 1]이어야 한다. Balance Factor 왼쪽 자식 노드가 루트 노드인 서브 쿼리의 최대 높이와 오른쪽 자식 노드가 루트 노드인 서브 쿼리의 최대 높이의 차이를 뜻하는 지표. BF = {왼쪽 자식 노드 최대 높이} - {오른쪽 자식 노드 최대 높이} Rotation 균형을 맞추기 위해 서브 쿼리의 부모 노드를 자식 노드로 수준을 낮추는 행위. 회전 방법은 다음과 같다. 1. Z의 부모 노드를 Y로 재설정. 2. 1번 과정에서의 떨어져 나간 서브 트리(T2)를 Z의 자식 노드로 재설정. Random Read Sequential Read In..

👣 개요 자료 구조가 일렬로 나열된 형태의 구조가 아닌 Tree나 Graph와 같은 형태로 존재하는 것을 일컫음. 👣 그래프 정점과 간선으로 이뤄진 자료 구조. 👣 그래프 표현 방법 - 인접 행렬 i번째 노드와 j번째 노드가 연결되면 해당 간선의 가중치를 (i, j) 셀에 기입. 👣 그래프 표현 방법 - 인접 리스트 각 노드가 연결된 노드를 리스트로 표현 👣 트리 그래프의 일종으로 부모, 자식 계층의 구조를 가지고 있다. 그리고 간선 사이의 가중치가 없다. 오로지 연결 여부만 나타낼 뿐이다. 👣 이진 트리 트리의 일종으로 자식 노드 수가 2개 이하인 트리. Full 자식노드가 0 또는 2개인 이진 트리. 쉽게 말해서 1개 짜리 자식노드가 없다는 것. Complete 왼쪽부터 차곡차곡 채워진 트리. Deg..

👣 개요 말 그대로 자료 구조가 일렬로 나열되어 있는 자료 구조를 일컫느다. 👣 배열 물리적으로 메모리에 나열되어 있는 데이터 집합. 요소들의 크기가 정해져 있고 같은 변수 타입으로 이뤄져 있다. 중복을 허용하고 순서가 존재. Random Read Sequential Read Insert Delete 시간 복잡도 O(1) O(n) O(n) O(n) 👣 연결 리스트 논리적으로 나열되어 있는 데이터 집합. 각 요소를 포함한 노드 앞단에 포인터가 존재해 다음 포인터를 표시할 수 있다. 싱글 연결 리스트 Next 포인터만 포함. 이중 연결 리스트 Next 포인터와 Prev 포인터를 포함. 원형 이중 연결 리스트 이중 연결 리스트와 같지만 마지막 노드와 첫 노드가 포인터로 연결된 형태. Random Read Se..

👣 시간 복잡도 👣 Big - O 표기법 Big-O 표기법은 알고리즘의 시간 복잡도를 표현하는 방법 중 하나로, 알고리즘이 얼마나 빨리 실행되는지를 나타내는 지표. 다른 평가지표에 비해 Big-O 표기법은 매우 비관적으로 시간 복잡도를 평가한다. 때문에 최악의 경우의 알고리즘의 성능을 표기. 알고리즘의 시간 복잡도는 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타내며, 이를 통해 알고리즘의 효율성을 평가할 수 있음. 👣 복잡도가 최고 차항의 단항식에만 집중하는 이유 - 개인적인 의견 1. Big-O 표기법이라는 것 자체가 최악의 시나리오에서의 알고리즘 성능을 측정하는 것. 최악의 상황은 입력 데이터 갯수가 커질 때 발생하기 마련이다. 2. 사실 입력 데이터의 갯수(n)가 적다면 알고리즘 사이의 차..

👣 개요 기존의 복잡한 문제를 간단한 작은 문제로 나눠 점차 해결해나가는 문제 풀이법. 점화식을 세우고 초기값을 이용해 원하는 목표를 달성한다. 👣 적용 사례 1 - 프로그래머스 '도둑질' 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 점화식을 다음과 같이 설정했다. F(n) = max( F(n-1) , F(n-2) + money[n] ) F(n) : n 번째까지의 갈취한 돈의 최대값. (n 까지 턴 돈) = (n-1 까지 턴 돈)과 (n-2까지 털고 n을 턴 돈) 중 더 많은 돈. 그리고 초기값은 2가지 상황을 상정해 설정했다. 시나리오 1)..