서론SPA의 정의 및 기본 개념SPA(Single Page Application)는 단일 HTML 페이지로 구성된 웹 애플리케이션을 의미합니다. 사용자가 웹 페이지를 탐색할 때, 전체 페이지를 다시 로드하지 않고 현재 페이지 내에서 필요한 콘텐츠만 동적으로 로드하여 빠르고 원활한 사용자 경험을 제공합니다. 이는 주로 JavaScript 프레임워크와 라이브러리를 활용하여 구현됩니다. SPA의 동작 원리기존의 다중 페이지 애플리케이션(MPA)에서는 사용자가 다른 페이지로 이동할 때마다 서버로부터 새로운 HTML 페이지를 받아오고 전체 페이지를 새로 고칩니다. 반면에 SPA에서는 처음에 한 번만 전체 페이지를 로드하고, 이후의 페이지 전환은 서버와 비동기적 통신(AJAX)을 통해 필요한 데이터만 받아와 화면을..

https://www.acmicpc.net/problem/10986누적합(prefix sum)먼저 누적합이란 나열된 수의 누적된 합을 말한다. 만약 [1, 2, 3, 4, 5] 라는 배열이 있고, 이 배열을 누적합으로 나타낸다면 [1, 3, 6, 10, 15] 가 된다. 보통 반복문을 통해 `0번 index부터 4번 index까지의 누적합`을 구한다면 5번의 수행동작이 필요하다. 즉 O(N)의 시간 복잡도를 갖는 것이다. 하지만 누적합을 사용하여 `0번 index부터 4번 index까지의 누적합`을 구한다면 누적합 배열의 4번 index 값을 꺼내오기만 하면 되기 때문에 O(1)의 시간 복잡도를 갖는다. 그렇다면 `2번 index부터 4번 index까지의 누적합`을 구하기 위해서는 어떻게 해야할까? (1..

https://www.acmicpc.net/problem/11444인사이트이번 문제는 우리들이 사랑하는 피보나치 수열이다. 피보나치 수열이 골드2까지 난이도가 책정된 이유에는 입력값의 크기 제한에 있다. 일반적으로 1초에 대략 1억번 정도의 연산이 처리된다는 것을 감안하면, 입력값의 최대값이 1000억이기 때문에 dp를 사용해서 O(N)의 시간 복잡도로 처리해도 시간 초과가 날 것임을 예상할 수 있다. 그렇기 때문에 피보나치 수열의 일반항으로는 어떤 짓을 해도 시간초과를 해결할 수 없을 것이다. 해서, 이 피보나치 수열의 일반항에서 시간 처리를 극적으로 줄일 점화식을 고안해내야 한다. 여기서 한가지 더 생각해보면 1000억이란 숫자를 1억 내로 안정적으로 줄이려면 제곱근으로 접근하는 것 외에는 거의 방법..

https://www.acmicpc.net/problem/17114문제 해설이번 하이퍼 토마토 문제는 지난 토마토 문제에서 배열의 깊이가 2차원에서 11차원으로 변형된 심화 문제입니다.  [백준 / BOJ] 7576번 토마토 ( Node js / Javascript )https://www.acmicpc.net/problem/7576  문제 풀이토마토는 BFS의 대표 문제들 중 하나입니다. 만약 BFS 혹은 그래프 탐색 자체에 대한 지식이 부족하다면 아래 링크를 참고하시길 바랍니다. 너비 우선 탐dnd0707.tistory.com 언뜻 보기에는 11차원이라는 말도 안되는 조건 때문에 괴랄해 보이겠지만 사실은 보이는 것 만큼의 난이도를 가진 문제는 아닙니다. 만약 만약 x축이 이동할 때 동시에 y축도 이동이..

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]가  주어졌을 때, 가..