땡글이LAB

처음 문제를 접했을 때는 DP라는 생각이 들지 않고, 그냥 단순한 구현문제인 줄 알고 구현했더니 시간초과가 나왔다. 내가 짠 코드의 시간복잡도는 O(N * M) 이었다. (아래의 코드는 시간초과된 틀린 코드이다.) #include using namespace std; typedef long long ll; int N, M; int board[2005]; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for (int i = 1; i > board[i]; } cin >> M; int S, E; while (M--) { cin >> S >> E; if (S == E) { cout > E; cout

이 2295번 문제에 가장 간단하게 접근하는 방법은 arr[i] + arr[j] + arr[k] = arr[m] 방식으로 시간복잡도가 O(N^4)인 방법이 있을테고, arr[m]을 찾는 방식을 이분탐색으로 바꿔주면, O(N^3 * logN) 이 될 것이다. 이 문제가 정답율이 낮은 이유도 이렇게 다들 생각을 많이 하고 제출했더니 메모리 초과가 나거나 시간초과가 난 것 같다. O(N^3 * logN) 코드는 다음과 같다. 이렇게 풀면 틀립니다 #include using namespace std; typedef long long ll; int N; int arr[1005]; vector three; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> ..

매개 변수 탐색 문제(Parametric Search)는 그냥 이분 탐색 문제와는 접근방법이 조금 다르다. 기본적인 이분탐색 문제의 경우에는 배열 요소들을 정렬해준 뒤, 위치를 찾아내기만 하면 된다. 하지만 2805번 문제와 같이 매개 변수 탐색 문제 같은 경우에는 조건을 만족하는 최소/최댓값을 구하는 문제, 즉 최적화 문제를 결정 문제로 변환해 이분탐색으로 문제를 해결해야 한다. 이걸 모르면 이분 탐색을 사용해서 풀라고해도 모를 수 있다. 나 또한 그랬다... :) 그럼 2805번 문제를 살펴보자. 문제에선 상근이가 M 미터 이상의 나무를 가져가야 하는데, M미터 이상의 나무를 가져가면서 절단기 높이의 최대 길이를 구해야한다. 이제 매개 변수 탐색 문제라고 했으니, '절단기 높이'와 '상근이가 취할 수..

[Spring Bean] Spring IoC Contatiner 에 의해 관리되는 객체를 Bean 이라고 한다. 일반적으로 Java에서 new 연산자를 통해 객체를 얻어낸 것은 Spring Bean이 당연히 아니다. Bean을 우리가 사용하기 위해 가져오려면 ApplicationContext 의 getBean() 메서드를 통해 가져온다. 그럼 어떻게 등록해야 하는 걸까?? [Spring Bean 수동 등록] 어플리케이션의 설정 정보를 담당하고 각 클래스 별 중추 역할을 해줌으로써 SOLID 원칙을 위반하지 않게 해주는 설정 클래스 AppConfig.class 가 있다고 가정해보자. 해당 AppConfig.class 에 @Configuration 어노테이션을 붙여주고, AppConfig 클래스 안에서 @B..

# Iterator(반복자) 컨테이너에 저장되어있는 원소들을 공통적인 방법으로 하나씩 접근 가능하다. 모든 컨테이너들이 다 같은 방법으로 반복자 사용 가능. 각 타입에 ::iterator 또는 ::const_iterator 를 뒤에 붙여주면 사용이 가능하다. vector 컨테이너의 반복자 vector::iterator it; vector 컨테이너의 const한 반복자 vector::const_iterator it; 포인터와 비슷하게 사용된다. 간접 참조 가능 it = v.begin() + 2 에서 *it 간접 참조를 하면 세 번째 원소 값이 리턴된다. iterator와 const_iterator의 차이 const_iterator는 반복자가 가리키는 원소의 값을 변경하지 못한다. 반복자 값이 변경되지 못하..

C++에서 문자열을 자르는 데에는 여러 방법이 있는데 istringstream을 사용한 방법과 find + substr을 사용한 방법을 알아보겠다. #1. istringstream 사용 - 헤더 파일 #include #include #include #include using namespace std; int main() { string str = "c++ java python JS"; istringstream iss(str); string tmp; while (getline(iss, tmp, ' ')) { cout

처음에 조합 리스트를 어떻게 구해야할지 몰라서 굉장히 막막했었는데, C++에서 제공하는 next_permutation 함수를 이용하면 순열 및 조합을 구할 수 있다는 걸 알고 내가 한 번 짜봤다. 이 문제에서의 핵심은 문자열로부터 조합을 구할 수 있느냐 없느냐의 차이인 것 같다. 조합만 구할 줄 안다면, 그 이후의 문제는 너무 쉽다. 이것 저것 찾아보니 조합을 구하는 방법 두 가지를 알게 됐다. 첫 번째 방법은 위에서 말한 대로 next_permutation 함수를 이용해서 구하는 것이고, 두 번째는 DFS(또는 재귀)로 구하는 방법이다. #1 next_permutation() 활용 풀이 우선 내가 푼 코드는 next_permutation 함수를 사용해서 푼 방식이니 내 코드부터 설명을 해보겠다. #in..

세그먼트 트리(Segment Tree)는 제목에 적힌 것처럼 이진 트리에서 응용된 트리이다. 세그먼트 트리는 여러 개의 데이터가 순서를 가지고 존재할 때, 특정 범위의 합을 구할 때 사용된다. 물론 데이터의 변경이 없다면 특정 범위의 합을 구하는 문제에서 동적 프로그래밍(DP)를 사용해도 괜찮다. 만약 주어진 데이터의 숫자가 지속적으로 변경되고 여러 번 특정 구간에 대해 합을 구해야 한다면 동적 프로그래밍(DP)의 사용이 적절할까?? 아니다. 데이터가 여러 번 바뀌고 구간 합을 여러 번 구해야 하는 상황이라면 동적 프로그래밍(DP)는 데이터가 바뀔 때마다 O(N) 시간복잡도를 가질 것이고, 데이터가 변경되는 횟수가 M이라면 총 O(NM)의 시간복잡도를 가진다. 그렇다면 세그먼트 트리의 경우는 어떨까? 세..