고양이와 별무리 도서관 Post List

누적 합 문제는 구간에 있는 수의 합을 빠르게 계산하기 위한 방법입니다. 11659번: 구간 합 구하기 4 (acmicpc.net) 문제는 1차원 배열에서 특정 구간의 합을 빠르게 계산하기 위한 방법을 묻는 문제입니다. 이는 $O(N)$의 시간 복잡도로 누적 합 배열을 생성하고, 특정 구간의 합을 $O(1)$의 시간 복잡도로 계산할 수 있습니다. ...

포인터(Pointer)란? 포인터(Pointer)란, 메모리의 주소를 저장하는 변수입니다. 즉, 포인터는 초기화되지 않아도 되며 (nullptr 가능), 필요한 주소를 그때그때 저장할 수 있습니다. 또한, 포인터는 산술 연산을 통해 주소 값을 자료형의 크기만큼 더하거나 뺄 수도 있습니다. 특징 포인터는 다른 변수의 주소를 저장할 수 있습...

LCS (Longest Common Subsequence, 최장 공통 부분 수열)은 두 개의 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾는 동적 프로그래밍 알고리즘입니다. 이 알고리즘은 DNA 서열 분석부터 데이터 압축까지 다양한 응용 분야에서 사용할 수 있는 매우 중요한 알고리즘입니다. 하지만, 이 문제를 처음 접하게 되면 풀이 방법을 ...

Dangling pointers는 유효한 객체를 가리키지 않는 포인터를 말합니다. 객체를 가리키고 있던 메모리가 해제된 후에 그 메모리 주소를 계속 참조하는 경우와 같은 경우로, 이 메모리 주소를 역참조하는 경우 정의되지 않은 동작(undefined behavior)이 발생할 수 있습니다. 정의되지 않은 동작(undefined behavior...

포인터(Pointer)란, 메모리의 주소를 저장하는 변수입니다. 이는 프로그래밍에서 중요한 역할을 하는데, 메모리의 특정 위치를 참조하고 그 위치에 저장된 값을 얻는 것을 역참조라고 합니다. 포인터를 사용하게 되면, 데이터를 복사하지 않기 때문에 데이터 구조를 효율적으로 순회하거나, 메모리를 직접 조작할 수 있어 훤씬 빠르고 메모리를 효율적으로 사용...

12865번: 평범한 배낭 문제는 동적 계획법 문제로, 무게가 k인 배낭에 최대한 가치있는 물건을 넣을 수 있는 최적 해를 찾는 문제입니다. 동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다. 우선, 동적 계획법 문제는 최적 부분...

2565번: 전깃줄 문제는 동적 계획법 문제이지만, 문제 풀이를 생각해내기 어려운 문제라고 생각됩니다. 동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다. 우선, 이 문제도 동적 계획법 문제이기 때문에 최적 부분 구조와 중복된 부...

10844번: 쉬운 계단 수 문제는 동적 계획법으로 풀 수 있는 문제입니다. 동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다. 동적 계획법 문제는 최적 부분 구조와 중복된 부분 문제의 두 가지 속성을 가진 문제에 유용합니다. 쉬운...

const는 상수를 선언하는 제한자(qualifier)입니다. 즉, 한 번 초기화된 const 변수의 값은 변경할 수 없습니다. #define으로 상수처럼 사용할 수 있으나, const로 선언하는 경우에는 데이터형을 명시적으로 지정 할 수 있고, 활동 범위 규칙으로 특정 함수나 파일에서만 사용할 수 있도록 제한할 수 있습니다. const int x...

2156번: 포도주 시식 문제는 동적 계획법(Dynamic Programming)으로 풀어내는 문제이지만, 동적 계획법으로 풀어낼 때, 점화식을 생각하는데 어려울 수 있습니다. 규칙은 다음과 같습니다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을...