똑똑한망치의 성장일기

깊이 우선 탐색 (DFS)은 그래프 완전 탐색 기법 중 하나이다.깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 기능특징시간 복잡도(노드 수: V, 엣지 수: E)그래프 완전 탐색재귀 함수로 구현스택 자료구조 이용O(V+E) 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로(stack overflow)에 유의해야 한다.깊이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등이 있다. 깊이 우선 탐색 DFS의 핵심 이론DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는..

JPA, Spring Data JPA 둘의 차이점이 무엇일까?  JPA는 자바 애플리케이션에서 객체 관계 매핑(ORM)을 위해 기술 표준으로 채택된 인터페이스이다.JPA는 Java Persistence API의 약자로, 자바 애플리케이션에서 관계형 데이터베이스를 사용하는 방식을 정의한 인터페이스와 어노테이션의 표준 집합을 정의한다.즉, 자바 ORM(Object Relational Mapping) 기술에 대한 API 표준 명세를 의미한다. JPA는 특정 기능을 하는 라이브러리가 아니다. 자바 애플리케이션에서 관계형 데이터베이스를 어떻게 사용해야 하는지를 정의하는 한 방법일 뿐이고 단순한 명세이기에 구현은 없고, 다양한 ORM 프레임워크(예: Hibernate, EclipseLink, OpenJPA 등) 에..

모듈 간의 통신에서는 되도록 비동기 통신(async)을 사용하는 것을 권장하며, 동기 통신(sync)의 횟수를 최대한 줄이는 것이 바람직하다. 서비스 간 통신이 불가능한 상황이 바로 장애로 이어지지 않게, 당장 메시지를 처리하지 못하더라도 보낸 메시지를 어딘가에 쌓아 둔 뒤 나중에 처리할 수 있는 채널을 만들어 주는 것. 이것이 메시지 브로커의 핵심 역할이라고 할 수 있다. 메시지 브로커는 크게 메시징 큐와 이벤트 스트림이라는 두 가지 형태로 나눌 수 있다. 메시징 큐 (메시지 큐) 생산자(producer) : 주로 데이터를 생성하는 쪽소비자(consumer) : 데이터를 수신하는 쪽이벤트 스트림발행자 (publisher) : 데이터를 생성하는 쪽구독자 (subscriber) : 데이터를 조회하는 쪽메시..

세션이란?세션이란 서비스를 사용하는 클라이언트의 상태 정보를 의미한다. 애플리케이션은 현재 서비스에 로그인돼 있는 클라이언트가 누구인지, 그 클라이언트가 어떤 활동을 하고 있는지 저장하고 있으며, 유저가 서비스를 떠나면 세션 스토어에서 유저의 정보를 삭제한다. 많은 서비스에서 레디스를 세션 스토어로 사용하고 있다. 유저가 로그인해 있는 동안 세션의 데이터를 끊임없이 읽고 쓰게 되므로 빠른 응답 속도는 필수적이다. 또한 레디스는 키-값 형식으로 사용이 간단하며 string, set, hash 등의 자료 구조를 제공하기 때문에 사용자 데이터를 저장하기에 용이하다. 세션 스토어가 필요한 이유  위의 그림과 같이 서비스 초창기, 혹은 프로토타입용 서비스에서는 → 굳이 세션 스토어가 필요 ❌각 웹 서버에 세션 스..

레디스와 캐시캐시란?캐시란 데이터의 원본보다 더 빠르고 효율적으로 액세스할 수 있는 임시 데이터 저장소를 의미한다.  위 그림과 같이 사용자가 동일한 정보를 반복적으로 액세스할 때 원본이 아니라 캐시에서 데이터를 가지고 옴으로써 리소스를 줄일 수 있다. 원본 데이터 저장소 데이터를 가지고 오는 시간을 단축시키기 때문에 애플리케이션의 응답 속도를 줄일 수 있다. 캐시로서의 레디스레디스는 단순하게 키-값 형태로 저장하므로, 데이터를 저장하고 반환하는 것이 굉장히 간단하며, 자체적으로 다양한 자료 구조를 제공하기 때문에 애플리케이션에서 사용하던 list, hash 등의 자료 구조를 변환하는 과정 없이 레디스에 저장할 수 있다. 또한 레디스는 모든 데이터를 메모리에 저장하는 인메모리 데이터 저장소이기 때문에 데..

Redis란?Remote dictionary server의 약자인 레디스(Redis)는 고성능 키-값 유형의 인메모리(in-memory) NoSQL 데이터베이스로, 오픈 소스 기반의 데이터 저장소다.  특징실시간 응답 (빠른 성능) 대부분의 데이터베이스는 온디스크(disk-based) 형태다. 온디스크 형태의 데이터베이스에서 데이터는 영구적으로 디스크에 저장된다. 자주 사용되는 데이터는 캐싱돼 메모레이 올라와 있는 경우도 있지만, 그렇지 않은 데이터를 찾고자 할 때에는 직접 디스크에 가서 데이터를 검색하는 과정을 거쳐야 한다. 이때 디스크에 저장된 데이터는 바로 찾을 수 없으며, 디스크의 데이터를 페이지 단위로 메모리에 올린 뒤 메모리에서 데이터를 찾고, 없는 경우 다시 다른 페이지를 디스크에서 가져와 ..

정렬 알고리즘 정의버블 (Bubble) 정렬- 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 선택 (selection) 정렬- 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식 삽입 (insertion) 정렬- 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식 퀵 (quick) 정렬- pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식 병합 (merge) 정렬- 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식 기수 (radix) 정렬- 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

투포인터 (Two Pointers)리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘정렬되어있는 두 리스트의 합집합에도 사용됨. 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 한다. 예제 문제 - 특정한 합을 가지는 부분 연속 수열 찾기투포인터 알고리즘의 대표적인 문제이다. 어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제이다. 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.현재 부분 합이 M과 같다면 카운트 한다.현재 부분합이 M보다 작다면 end를 1 증가시킨다.현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.모든 경우를 확인할 때까지 2~4번 과정을 반복한다. 위..

✏️ TDD란Test Driven Development의 약자로 '테스트 주도 개발' 이라고 한다.반복 테스트를 이용한 소프트웨어 방법론으로, 작은 단위의 데스트 케이스를 작성하고 이를 통과하는 코드를 추가하는 단계를 반복하여 구현한다. 짧은 개발 주기의 반복에 의존하는 개발 프로세스이며, 애자일 방법론 중 하나인 eXtream Programming(XP)의 'Test-First' 개념에 기반을 단순한 설계를 중요시한다. 🕹️ TDD 개발 주기 Red 단계에서 실패하는 테스트 코드를 먼저 작성한다.Green 단계에서는 테스트 코드를 성공시키기 위한 실제 코드를 작성한다.Blue 단계에서는 중복 코드 제거, 일반화 등의 리팩토링을 수행한다. 중요한 것은 실패하는 테스트 코드를 작성할 때까지 실제 코드를 ..

🟥 2차원 구간 합 배열 D[X][Y] 정의D[X][Y] = 원본 배열의 (0,0) 부터 (X, Y)까지의 사각형 영역 안에 있는 수의 합 ⚛️ D[X][Y]의 값을 채우는 구간 합 공식D[ i ][ j ] = D[ i ][ j - 1 ] + D[ i - 1][ j ] - D[ i - 1 ][ j - 1] + A[ i ][ j ] ❗질의 X1, Y1, X2, Y2에 대한 답을 합으로 구하는 방법D[X2][Y2] - D[X1-1][Y2] - D[X2][Y1-1] + D[X1 - 1][Y1 - 1] 관련 문제https://www.acmicpc.net/problem/11660