https://www.acmicpc.net/problem/1253 간단하게 생각하면 모든 수를 하나씩 더해봐서 할 수 있는 간단한 문제이다. 다만, N의 최대값은 2,000인데 시간복잡도에 따라 N^2 or N^3 등등 커질수록 많은 시간이 걸릴 것이다. 그렇게 되면 시간초과에 걸리게 된다. 즉, 이 문제를 풀기 위해서는 그 이하의 시간복잡도를 가지는 알고리즘을 사용하여 문제를 풀어야 한다. 두 개의 합으로 나타낼 수 있는 수를 찾는 문제이므로, 투 포인터 알고리즘을 사용한다. 시작 인덱스 0과, 끝 인덱스 N - 1에서 차례차례 더해서 확인해가며 값을 찾으면 시간복잡도 O(N)으로 값을 찾을 수 있다. 그 작업을 수행하기 위해서는 정렬을 먼저 수행하여 두 수를 더해 그 값을 비교하여 합이 작으면 시작 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 (DP)와 브루트포스 알고리즘을 활용한 문제이다. 주어진 기간 안에 최대한의 이득을 확인하는 문제이기 때문에 점화식으로 계산하여, DP리스트에 그 날에 할 수 있는 최댓값을 넣어주면서 진행하면 된다. N날이 되었을 때 DP[N]에 있는 값이 그 기간 안에 할 수 있는 최대의 가치를 가진 일이 될 것이다. #include using namespace std; int N; int list[15][2]; int dp[15]; int main() { ios::sync_with_stdio(0); cin.tie(0); cou..

https://www.acmicpc.net/problem/11047 그리디 알고리즘을 사용한 실버4 문제이다. 동전의 가치를 오름차순으로 입력한 뒤, 가장 최소한의 동전을 사용하여 K의 합을 만들면 문제이다. 처음에 어떻게 해야할지 막막할 수 있지만, 생각해보면 간단한 문제이다. K값보다 작거나 같은 가치의 동전을 먼저 사용하고, 나머지는 먼저 사용한 동전보다 낮은 가치의 동전을 사용해서 다시 메꿔주는 작업을 반복하면 된다. #include int main() { int N, K; int array[10]; int answer = 0; std::cin >> N >> K; for (int i = 0; i > array[i]; } for (int i = N - 1; i..

참조자란? 기존에 있던 C언어에서는 다른 변수를 가르키고 싶을 때 포인터를 사용했었다. C++에서도 사용할 수 있지만, 다른 방식도 존재하는데 이 방식이 바로 참조자(Reference) 이다. 참조자는 접근하려는 변수에 다른 이름을 말한다. #include int main() { int A = 10; int& Another_A = A; Another_A = 20; // A = 20, Another_A = 20. return 0; } Another_A를 변경하니 A의 값도 변경하는 것을 확인할 수 있다. 포인터와 참조자의 차이점 그렇다면 포인터와 참조자의 차이는 무엇일까? 1. 참조자는 처음 정의할 때 누구를 가리키는지 명시해야 한다. 포인터는 처음 정의할 때 누구를 가르키는지 명시하지 않아도 된다. 하지..

선형 자료구조에는 앞서 정리했던 배열, 연결 리스트, 스택 그리고 큐가 있다. 이번에는 큐(Queue)에 대해 정리해보자. 큐 큐는 스택과 비슷하지만 조금은 다르다. 스택은 위에서부터 수직으로 쌓는 느낌이였다면, 큐는 수평으로 넣는 느낌이다. 즉, LILO(Last in Last out), FIFO(First in First out)의 순서를 따라간다. 특징 데이터를 받는 순서대로 정렬해서 저장한다. 가장 앞부분을 Front / Head, 뒷부분을 Rear / Tail라고 한다. 한쪽 끝에서는 삽입, 다른 한쪽에서는 삭제만 수행한다. 시간복잡도 접근(Access) : 들어간 순서에 따라서 접근할 수 있기 때문에 O(n)의 시간 복잡도를 가진다. 삽입(insert) 및 삭제(delete) : 앞쪽에 삽입하..

자료구조의 스택에 대해 알아보자. 스택 스택은 쌓아놓은 더미를 뜻한다. 쌓여져 있는 데이터를 한 쪽에서만 넣고 뺄 수 있는 선형 구조로 되어 있다. LIFO(Last in First out), FILO(First in Last out)의 순서를 따라간다. 특징 데이터를 받는 순서대로 정렬해서 저장한다. LIFO는 맨 위, 즉 마지막으로 삽입된 데이터를 먼저 사용한다. FIFO는 맨 아래, 즉 먼저 삽입된 순서대로 데이터를 사용한다. 시간복잡도 접근(Access) : 쌓여져있는 순서대로 접근할 수 있기 때문에 O(n)의 시간 복잡도를 가진다. 삽입(insert) 및 삭제(delete) : 가장 위에 삽입하거나 삭제할 수 밖에 없기 때문에 O(1)의 시간 복잡도가 발생한다. 검색(search) : 접근과 마..