DFS 란?깊이우선탐색(DFS;Depth-First Search) 알고리즘은 그래프나 트리구조에서 깊이를 우선으로 탐색하는 알고리즘이다.즉 한 경로를 끝까지 다 탐색한 후에 다음 경로로 넘어가 탐색을 이어간다.주로 스택(Stack)이나 재귀함수를 사용하여 구현하고, 더이상 탐색할 노드가 없으면 이전 분기점으로 돌아간다(=백트래킹).  DFS의 동작 방식0. 탐색이 필요한 노드를 저장할 스택과 방문 처리를 위한 visited 변수가 필요하다.1. 시작노드를 스택에 넣는다2. 스택이 비어있지 않다면 아래 내용을 반복한다.스택 최상단 노드를 현재 노드로 지정한다.현재 노드에 인접한 미방문 노드가 있으면 그 노드를 스택에 넣고 방문처리한다.인접한 미방문 노드가 없으면 스택에서 노드를 꺼낸다.   BFS 구현 ..

BFS 란?너비우선탐색(BFS;Breadth-First Search) 알고리즘은 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다.주로 선입선출 방식은 큐(Queue) 자료구조를 활용하여 구현된다.모든 간선의 비용이 동일한 조건에서 최단거리를 구하는 문제에 효과적이다.  BFS의 동작 방식0. 다음 방문 노드를 저장할 큐와 방문 처리를 위한 visited 변수가 필요하다.1. 시작 노드를 큐에 삽입하고 방문 처리 한다.2. 큐가 비어있지 않다면(= 다음 방문 노드가 남아 있다면) 아래 내용을 반복한다.큐의 첫 번째 노드를 꺼내어 현재 노드로 설정.현재 노드 방문 처리.인접 노드를 확인하고, 인접 노드가 아직 방문 되지 않았다면 큐에 삽입.   BFS 구현 예제[백준/Silver II] 알고리즘..

최장 공통 부분 수열 (LCS; Longest common subsequence problem)부분 수열(subsequence)은 시퀀스의 원소를 순서를 유지한 채 몇 개를 골라낸 것을 말한다.최장 공통 부분 수열은 두 시퀀스(문자열 또는 배열)간 공통된 부분 수열 중 가장 긴 것을 찾아내는 문제이다. 예시) 문자열 `ABCBDAB`와 `BDCABA`의 LCS는 `BCBA`이다. 보통 LCS 문제를 해결하기 위해 주로 동적 계획법(DP;Dynamic Programming)을 사용한다.이 글에서도 DP를 이용한 LCS 알고리즘을 설명하고자 한다.  LCS 길이 구하기동작 원리동적 계획법은 문제를 작은 부분 문제로 나누고 그 해를 이용해서 전체 문제를 해결하는 방식이다.때문에 문제 정의와 점화식, 초기 조건..

벨만-포드 알고리즘이란?벨만-포드 알고리즘(Bellman-Ford Algorithm)은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로/최소 비용를 찾는 알고리즘이다.다익스트라 알고리즘과 차별되는 점은 음수 가중치를 처리할 수 있다는 점과 음수 사이클을 탐지할 수 있다는 점이다.때문에, 음수 가중치가 포함된 그래프에서 유용하게 사용된다. 동작 원리벨만-포드 알고리즘은 크게 세가지의 과정을 거친다.1. 초기화시작 정점에서 다른 모든 정점까지의 거리를 무한대로 설정한다.시작 정점의 거리를 0으로 설정한다. 2. 간선 반복모든 간선에 대해 그 간선을 따라 가는 거리가 기존에 기록된 거리보다 짧으면, 해당 거리를 업데이트 한다.이 과정을 그래프에 있는 `정점의 수 - 1`번 반복한다.왜냐하면, 최단 ..

다익스트라 알고리즘이란?다익스트라 알고리즘(Dijkstra's Algorithm)은 네덜란드의 컴퓨터 과학자 에츠허르 다익스트라(Edsger Dijkstra)가 고안한 알고리즘으로, 그래프에서 한 노드(정점)에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 특히 가중치가 음수가 아닌 경우에 유효하다.동작 원리1. 시작 노드 설정시작 노드를 설정하고, 시작 노드에서 다른 모든 노드로의 거리를 무한대로 설정한다. 시작 노드의 거리는 0으로 설정한다.2. 미방문 노드 집합 설정모든 노드를 미방문 노드 집합에 넣는다.3. 최단 거리 노드 선택처음에는 시작노드가 선택되고, 이후에는 미방문 노드 중에서 현재 가장 짧은 거리를 가진 노드를 선택한다.4. 거리..

저장 프로시저란?저장 프로시저는 데이터베이스에서 반복적으로 수행되는 작업을 하나의 단위로 모아 저장해 놓은 일련의 SQL문들이다.특정 작업을 수행할 때마다 동일한 SQL문을 다시 작성할 필요 없이, 미리 정의된 절차를 호출함으로써 실행할 수 있다. SELECT, INSERT, UPDATE, DELETE 등의 DQL, DML을 포함할 수 있다.IF문, DECLARE, SET 등의 프로그래밍 문법을 사용할 수 있어 복잡한 로직 구현이 가능하다.CALL, EXEC 명령어를 통해 함수처럼 호출하여 실행할 수 있다.   저장 프로시저의 장단점장점 성능 향상저장 프로시저는 컴파일되고 캐싱되기 때문에 동일한 작업을 반복적으로 수행할 때 성능이 향상다.보안 강화데이터베이스 접근을 저장 프로시저를 통해 제어하면, 프로..

인덱스(Index)란?데이터베이스에서 검색 성능을 향상시키기 위해 사용되는 데이터 구조인덱스는 책의 색인처럼, 테이블의 데이터를 효율적으로 검색할 수 있도록 돕는 데이터 구조이다. 인덱스가 설정된 열을 기준으로 데이터를 빠르게 찾아갈 수 있어, 전체 테이블을 순차적으로 검색하지 않아도 된다.예를 들어, 'Name'이 'HOLLY'인 데이터를 조회할 때, 'Name' 컬럼에 인덱스가 설정되어 있다면 전체 데이터를 비교할 필요 없이 빠르게 검색할 수 있습니다.  인덱스 장단점인덱스 장점빠른 데이터 검색데이터를 빠르게 검색할 수 있어 조회 성능 향상.데이터 정렬인덱스가 적용된 열에 대해 정렬된 데이터를 효율적으로 접근할 수 있음.고유성 보장Primary Index, Unique Index 등의 사용을 통해 고..

Redis란?Redis는 고성능의 온프 소스 인메모리 데이터 구조 저장소이다.NoSQL의 한 종류로, 주로 키-값(key-value) 저장소로 사용되며 다양한 데이터 구조를 지원한다.빠른 일기 및 쓰기 속도를 제공하여 캐싱, 세션 관리, 실시간 분석, 메시지 큐와 같은 다양한 용도로 활용된다.   Redis 특징인메모리 저장소모든 데이터를 메모리에 저장하여 매우 빠른 읽기 및 쓰기 성능을 제공.고성능이 요구되는 애플리케이션에 적합한 특징.풍부한 데이터 구조키-값 저장소뿐만 아니라 문자열, 해시, 리스트, 셋, 비트맴, 하이퍼로그로그, 스트림 등의 다양한 데이터 구조를 지원.지속성(영속성)데이터는 메모리에 저장되지만, *RDB(Redis Database) 스냅샷과 *AOF(Append Only File) ..

이상현상(Anomaly)란?이상현상은 데이터베이스 조작 시 발생할 수 있는 비정상적인 동작이나 데이터 무결성 문제를 의미한다.주로 비정규화된 데이터베이스에서 발생하며, 데이터 중복과 관련된 문제를 초래할 수 있다.이상현상은 크게 삽입 이상, 삭제 이상, 갱신 이상 세가지로 나눌 수 있다.   삽입 이상(Insertion Anomaly)새로운 데이터를 삽입할 때 불필요한 데이터도 함께 삽입해야하는 문제를 말한다.이는 데이터베이스 설계가 잘못되어 필수적이지 않은 데이터 없이 원하는 데이터를 삽입할 수 없는 경우 발생한다. 예시)아래의 테이블은 고객과 그들이 주문한 상품 정보를 하나의 테이블에 저장하는 경우이다.| CustomerID | CustomerName | OrderID | ProductName ||-..