17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 틀렸습니다, 시간 초과 무식하게 풀 경우 최대 연산 횟수는 1,000,000 + 999,999 + ... + 1 = 500,000,500,000으로 5000억번 가량이 되므로 다른 방법을 찾아야 한다. 요즘 코테 공부하면서 큰돌 선생님 강의를 듣고 있는데 문제를 접근할 때 완전탐색 > DP > 그리디 순서로 생각해보라고 했다. 완전탐색이 안되기 때문에 DP로 문제를 풀어보려고 했다. dp[i]에 i번째 원소의 오큰수를 담는다고 했을..

1️⃣ 그리디 Greedy는 '탐욕스러운, 욕심 많은'이라는 뜻으로 각 단계마다 지역적 최적해가 궁극적으로 전역 최적해가 되는 것이다. (선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달한다) 그리디 알고리즘으로 문제를 풀기 위해서는 아래 두 가지 조건을 충족해야 한다. 최적 부분 구조 - 현재 상태에서의 최적해가 전역적인 최적해로 이어져야 한다. 탐욕적 속성(앞의 선택이 이후의 선택에 영향을 주지 않음)이 증명되어야 한다 귀류, 귀납, 대우증명을 사용할 수 있으며, 귀류법을 보통 자주 사용 귀류법 - 어떤 명제가 참이라고 가정한 후, 모순을 이끌어내 그 가정이 거짓임을 증명하는 방법 코테에서 그리디를 풀기 위해 증명까지 해야 하는가?! 💡 무식하게 풀기 → DP → 그리디 ..

2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 1️⃣ 문제 설명 2️⃣ 예제 설명 예제 1에서 1~5 구간에서는 겹치는 선이 하나로 인식되어 길이가 4인 선분이 되고, 6~7 구간이 길이가 1인 선분이 되어 그은 선의 총 길이는 4+1=5가 된다. 3️⃣ 구현 아이디어 - 틀렸습니다 처음에 문제를 봤을 때 최근에 풀었던 회의실 배정과 비슷해보여 끝나는 지점을 기준으로 정렬하여 문제를 풀어보려고 했다. N의 최댓값이 1,000,000이고 x와 y의 최솟값과 최댓값이 -1,000..

문제 예제 예제 1에서는 첫 번째 보석을 담았을 때가 최대이고, 예제 2에서는 첫 번째 보석을 두 번째 가방에, 세 번째 보석을 첫 번째 가방에 담았을 때가 최대이다. 구현 1 - 시간 초과 💡 보석을 가격이 높은 순으로 정렬, 가방은 무게가 작은 순으로 정렬하고 비싼 보석부터 차례대로 가방에 담는다 우선순위 큐를 사용하면 자동으로 정렬이 되므로 보석 정보를 priority_queue에 담아주었다. 보석을 담을 수 있는 가방을 찾기 위해 반복문을 사용하였는데, 이 때 한 가방에 2개의 보석이 담기지 않도록 visited 배열을 추가로 사용해주었다. #include using namespace std; int n, k; // 보석과 가방의 개수 priority_queue v; // {보석 가격, 무게} v..

최근 DFS나 백트래킹 유형을 풀 때 재귀 함수를 구현하는 것이 어려워서 당분간은 재귀 유형을 풀면서 재귀 연습을 하고자 한다! 이번에 풀 문제는 백준 1780번 종이의 개수라는 문제이다. 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 설명 예제 설명 구현 아이디어 전체 구현 과정 1. 모두 같은 수 A라면 A로만 채워진 종이의 개수를 +1한다 2. -1, 0, 1로 채워진 종이의 개수를 구하기 위해 map을 사용 (ex. 각각 3, 2, 1장일 때 { (-1,3), (0,2), (1,1) ..

1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 설명 뒷면이 위를 향하는 동전 개수를 최소로 해야 하니 T가 최소일 때를 T의 개수를 구해야 한다. 예제 설명 위 그림처럼 2번째 행을 뒤집고 > 3번째 열을 뒤집으면 T가 2개가 되는데 이 때가 T가 최소일 때이므로 2가 출력된다 시간 복잡도 N은 최대 20까지 가능하며, 행이나 열을 뒤집을 수 있기 때문에 모든 경우의 수를 생각했을 때 총 연산 횟수는 2^(20+20) = 2^40번일 것이다. 2^40번이라면 시간 초과가 날 것이다. 하지만, 이 때..