1. 동적 계획법이란?동적 계획법이란 해결하고자 하는 문제를 작은 문제로 나누어 해결하고, 작은 문제들의 해들로부터 큰 문제의 답을 구하는 방식입니다. 여기서 중요한 점은 "분할과 정복"과 달리 DP는 분할된 작은 문제들이 상호 독립적이지 않고, 일정 부분을 공유한다는 점입니다. 본인은 편의점 알바를 하고있습니다. 그리고 저는 항상 출근하면 가장 먼저 담배 재고를 조사합니다. 담배를 꺼내 세다보면 맨 오른쪽처럼 10개가 넘어가는 재고들이 종종 있는데, 이런 경우에는 한눈에 몇개인지 들어오지도 않고 이런 것들을 하나하나 다 세다보면 재고 조사에 쓰는 시간이 꽤 길어집니다. 그렇다고 대충 눈대중으로 세고 넘어가기에는 여간 찝찝한게 아니죠.사진 속 모든 담배의 개수를 세야한다고 가정해볼까요?  세줄로 나누어 ..

이번 포스팅에서는 LCS 알고리즘에 대해 아래의 백준 문제를 예제로 소개해보겠습니다.https://www.acmicpc.net/problem/9251 Longest Common Subsequence / Longest Common Substring LCS란 최장 공통 부분 수열(Longest Common Subsequence) 혹은 최장 공통 부분 문자열(Longest Common Substring)을 뜻합니다. LCS를 구하는 알고리즘은 다이나믹 프로그래밍(DP) 알고리즘의 대표적인 유형으로, 어째서 DP인지는 글의 마지막 부분에서 설명하겠습니다.   먼저 최장 공통 부분 수열( Longest Common Subsequence ) 란 두 개 이상의 시퀸스[ACAYKP, CAPCAK]가  주어졌을 때, 가..

BFS(Breadth-First Search)와 DFS(Depth-First Search)는 그래프 탐색 알고리즘의 두 가지 주요 유형으로, 그래프의 데이터를 탐색하는 데 사용됩니다. 이 두 알고리즘을 이해하기 위해서는 그래프가 무엇인지에 대한 개념이 선행되어야 합니다. 그래프에 대한 개념이 부족하신 분들은 아래 포스팅을 참고해주시면 감사하겠습니다.  그래프 ( Graph ) 탐색 이론1. 그래프의 구성요소 그래프의 기본 구성 요소는 정점(Vertex, 혹은 노드(Node))과 간선(Edge)입니다. 정점은 그래프의 기본 단위로, 위치나 상태 등을 나타낼 수 있고, 간선은 두 정점을 연결하는 선dnd0707.tistory.com 너비 우선 탐색 (BFS)너비 우선 탐색 (BFS) 는 그래프의 시작 정점에..

1. 재귀 함수란? 코드 내에서 본인을 호출하는 함수를 재귀함수라고 한다. 하지만 단순히 아래와 같이 자기 자신을 호출만 한다면 함수는 위 송강호씨처럼 영원히 자기 자신을 호출하기를 반복하게 될 것이다. function recursive() { recursive(); } recursive(); 이를 방지하기 위해서 재귀함수는 코드 내에 탈출 조건을 포함하고 있어야 하고, 본인을 호출할 때마다 입력 파라미터가 탈출 조건에 수렴하는 양상으로 변화해야 한다. function recursive(n) { if(n < 0){ //탈출 조건 return; } recursive(n - 1); //변화하는 파라미터, 0으로 수렴 } recursive(5); 2. 반복문 vs 재귀 함수 대부분의 재귀 함수 동작은 변수값을..

1. 그래프의 구성요소 그래프의 기본 구성 요소는 정점(Vertex, 혹은 노드(Node))과 간선(Edge)입니다. 정점은 그래프의 기본 단위로, 위치나 상태 등을 나타낼 수 있고, 간선은 두 정점을 연결하는 선으로, 두 정점 사이의 관계를 표현합니다. 이러한 구성 요소들을 바탕으로, 그래프는 복잡한 네트워크 관계를 모델링하는 데 사용됩니다. 2. 그래프의 형태 그래프는 크게 방향성의 유무와 가중치의 유무에 따라 분류할 수 있습니다. 2-1. 무방향 그래프, 방향 그래프 무방향 그래프(Undirected Graph): 간선에 방향성이 없는 그래프로, 간선이 (A, B)라면 A와 B는 서로 연결되어 있음을 나타냅니다. 방향 그래프(Directed Graph): 간선에 방향성이 있는 그래프로, 간선이 (A..