DEVLOG DEVLOG

이진 탐색이란? 이진 탐색은 정렬된 리스트에서 검색 범위를 절반씩 줄여 나가며 검색 데이터를 탐색하는 알고리즘입니다. 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만 검색이 반복될 때마다 검색 범위가 절반으로 줄기 때문에 속도가 빠르다는 장점이 있습니다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾는 방식으로 동작합니다. 배열의 중간 데이터를 비교 중간 데이터와 검색 데이터를 비교 중간 데이터가 검색 데이터와 같다면 종료 중간 데이터보다 검색 데이터가 크다면 중간 데이터 기준 배열의 오른쪽 구간을 대상으로 탐색 중간 데이터보다 검색 데이터가 작다면 중간 데이터 기준 배열의 왼쪽 구간을 대상으로 탐색 데이터를 찾을 때까지 2번 작업을 반복 예제 key = 23 ..

힙이란? 데이터에서 최대값과 최솟값을 빠르게 찾기 위해 완전 이진 트리로 구현된 자료구조입니다. 부모 노드가 가진 값이 자식 노드의 값보다 작은 힙을 Min Heap, 부모 노드가 가진 값이 자식 노드보다 큰 힙을 Max Heap 이라고 합니다. 이때 부모노드의 값은 자식 노드보다 무조건 작거나 커야합니다. 위 이미지는 Max Heap의 예시입니다. 루트 노드의 값이 가장 크고 리프 노드를 제외한 자식 노드들 또한 본인의 자식 노드 보다 큰 값을 가지고 있습니다. 이러한 특성을 활용하여 가장 크거나 가장 작은 값을 찾아내기에 적합한 자료구조라고 볼 수 있습니다. 힙의 동작 방식 데이터 삽입 힙은 완전 이진 트리이기 때문에 최하단 노드부터 데이터가 채워집니다. 추가된 노드와 부모 노드의 값을 비교 후 자식..

누적합 알고리즘은 배열의 각 원소에 대한 누적된 합을 구하는 알고리즘입니다. 누적합 알고리즘을 사용하면 배열의 부분합을 낮은 시간복잡도로 효율적으로 구할 수 있고 구간 합을 여러번 계산할 때 주로 사용됩니다. 1차원 누적합 arr = [a1, a2, a3, a4] 을 누적합 배열로 계산하게 되면 다음과 같이 계산됩니다. accumulated_sum = [a1, a1 + a2, a1 + a2 + a3, a1 + a2 + a3 + a4] 특정 배열 구간(i, j)의 합은 accumulated_sum[j] - accumulated_sum[i - 1]로 표현할 수 있습니다. public int[] accumulate(int[] arr) { int n = arr.length; int[] accumulatedSum..

리스트란? 리스트는 데이터를 나란히 저장하고 중복된 데이터의 저장을 허용하는 자료구조입니다. 순서의 개념이 없는 집합과는 달리 순서, 위치를 갖고 있습니다. 스택, 큐 또한 리스트를 활용하여 구현된 자료구조입니다. 리스트의 구현 방법으로는 배열을 사용하는 순차 리스트, 메모리의 동적 할당을 기반으로하는 연결 리스트가 있습니다. 순차 리스트 순차 리스트는 배열을 기반으로 리스트를 구현한 방법입니다. 장점 데이터의 참조가 쉽다(인덱스 값으로 한번에 참조 가능) 단점 연속된 메모리 주소를 할당해야 하기 때문에 배열의 길이가 초기에 결정되어야함 삭제의 과정에서 데이터의 이동이 빈번하게 발생 시간 복잡도 데이터 탐색 인덱스를 활용하여 임의 접근이 가능하기 때문에 탐색 과정에 시간 복잡도는 O(1)입니다. 데이터 ..

문제 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요. 3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고..

컴파일 과정 1. 개발자가 자바 소스코드(.java)를 작성 2. 자바 컴파일러가 자바 소스파일을 컴파일하여 자바 바이트 코드(.class)로 변환, 자바 바이트 코드는 컴퓨터는 읽지 못하고 JVM에서 읽을 수 있습니다. 3. 컴파일된 자바 바이트 코드를 JVM의 클래스 로더에게 전달하고 클래스 로더는 동적 로딩을 통해 필요한 클래스들을 로딩 및 링크하여 런타임 데이터 영역(JVM 메모리)에 올립니다. 4. 실행 엔진은 JVM 메모리에 올라온 바이트 코드들을 명령어 단위로 하나씩 가져와 실행합니다. 클래스 로더 클래스 로더가 클래스들을 로딩 및 링크하는 과정은 다음과 같습니다. 로드: 클래스 파일을 가져와 JVM 메모리에 로드 검증: 자바 언어 명세, JVM 명세에 명시한대로 구성되어 있는지 검사 링킹:..

DB의 데이터의 볼륨이 커지면 DB의 읽기, 쓰기 성능이 저하될 수 있는데 이러한 문제점을 분산 처리 기법으로 방지할 수 있습니다. 샤딩은 분산 처리 기법 중의 하나로 테이블의 row들을 여러 대의 DB 서버들에 물리적으로 나누어 분산 저장하는 기법입니다. 샤딩은 수평 파티셔닝과 유사하지만 파티셔닝은 동일한 서버에 저장하지만 샤딩은 데이터를 물리적으로 서로 다른 서버에 분산하여 저장한다는 차이점이 있습니다. 장점 여러 서버에 분산되어 저장이 되어 쿼리 스캔 범위가 줄어 처리 속도가 향상됩니다. 서버의 replica를 진행하여 이중화 구성이 용이합니다. 단점 어플리케이션(코드)의 복잡도가 증가합니다. 핫스팟이라고 불리는 데이터가 특정 샤드에 몰리는 케이스의 경우 샤딩이 무의미해집니다. 샤딩 방식 모듈러 샤..

트랜잭션 격리 수준 이란 동시에 여러 트랜잭션이 수행될 때 특정 트랜잭션이 다른 트랜잭션에서 변경하는 데이터를 조회 가능 여부를 결정하는 것입니다. 종류는 총 4가지로 Read uncommitted, Read committed, Repeatable read, Serializable이 있습니다. Read uncommitted 한 트랜잭션에서 변경된 데이터를 Commit, Rollback 여부와 관계 없이 다른 트랜잭션에서 조회할 수 있는 Dirty read가 발생하고 데이터의 정합성과 일관성이 깨지게됩니다. Read committed 실제 테이블의 데이터를 조회하는 것이 아닌 Undo 영역에 백업된 데이터를 조회합니다. 그로인해 Read uncommitted에서 발생하던 Commit되지 않은 트랜잭션에서 ..