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개가 넘어가는 재고들이 종종 있는데, 이런 경우에는 한눈에 몇개인지 들어오지도 않고 이런 것들을 하나하나 다 세다보면 재고 조사에 쓰는 시간이 꽤 길어집니다. 그렇다고 대충 눈대중으로 세고 넘어가기에는 여간 찝찝한게 아니죠.사진 속 모든 담배의 개수를 세야한다고 가정해볼까요?  세줄로 나누어 ..

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..