그리디 문제이다. 조를 나누는 문제이므로 K-1의 칸막이를 설치한다고 생각할 수 있다. 직관: 한 조의 차이가 가장 작아야 하므로 일단 가장 차이가 큰 곳에 칸막이를 우선적으로 설치하면 차이가 최대가 될 것 같다. 반례: 가정 결론 도출 코드 #include #include #define F first #define S second using namespace std; int N, K, h[300000], sum; pair dif[300000]; bool devide[300000]; int main(void){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); cin >> N >> K; for(int i=0; i> h[i]; for(int i=0; i

stack의 이용한 괄호쌍의 유효성 검사 문제이다. 하지만 이 문제는 값이 존재하여 연산이 추가되었다. 먼저, 괄호가 닫힐 때마다 곱해진 값을 더해주고 갱신하면서 계산하려고 했으나 앞의 값들이 다 날아가는 문제가 생겼다. 다른 방법을 다른 블로그들을 참고하다 괄호가 열릴 때 미리 계산해야 한다는 사실을 깨달았고 이 과정에서 분배법칙을 이용하였다. #include #include #include using namespace std; string str; int temp, ans; stack bracket; char pre; int main(void){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); temp = 1; cin >> str; for(auto e..

1. 문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 2. 풀이 아이디어 알고리즘 코드 #include #include #include #define F first #define S second #define IN(Y, X) Y >= 0 && Y = 0 && X < N using namespace std; queue q; int dy[4] = {0, 1, 0, -1}; int dx[4] = {1, 0, -1, 0}..

#include #include #include #include #define F first #define S second #define IN(Y, X) Y >=0 && Y =0 && X < M using namespace std; int N, M, cheese, board[100][100]; bool visit[100][100]; queue q; vector melt; int dy[4] = { 0, 1, 0, -1 }; int dx[4] = { 1, 0, -1, 0 }; void BFS(int y, int x) { visit[y][x] = true; q.push({ y, x }); while (!q.empty()) { pair front = { q.front().F, q.front()..

1. 문제 https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 2. 풀이 아이디어 제한 시간이 2초인 만큼 모든 수를 선형탐색해도 시간이 넉넉하다. 따라서 1부터 N까지 반복문을 다음 수를 만들면 된다. 분해합이 N이 되는 순간 반복문을 멈추고 바로 답을 출력하면 통과 시간을 최대한 빠르게 할 수 있다. 분해합을 구하는 과정은 [자릿수 분해] 알고리즘을 사용한다. 알고리즘 순서 1 ~ N까지 반복문을 돌며 현재의 숫자의..

1. 문제 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2. 풀이 아이디어 완전 탐색으로 로프의 모든 조합을 비교하면 부분집합의 개수를 구하는 문제와 같아진다. 이런 경우 2ⁿ의 가지수가 생긴다. 최대 N이 10⁵이므로 완전 탐색을 이용할 경우 무조건 시간 초과가 발생한다. DP를 사용하여 memoization한다고 해도 O(N²)의 시간 복잡도를 가지므로 제한 시간내에 통과할 수 없다. 따라서 더 빠른 풀이를 생각해야 한다. 그러..

https://velog.io/@pppp0722/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EB%AC%B8%EC%A0%9C-%EC%9C%A0%ED%98%95-%EC%A0%95%EB%A6%AC 코딩테스트 문제 유형 정리 코딩테스트에서 가장 중요한 것은 꾸준함이 아닐까...? 🔥 코딩테스트의 중요성 신입 개발자 채용의 경우 지원 후 코딩테스트로 일정이 시작되는 경우가 대부분이다. 물론 코딩테스트를 보지 velog.io https://devjeong.com/algorithm/algorithm-1/#%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0 [Algorithm] 백준 문제 추천 devjeong.com

1. 문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 중복을 허락하여 해당 동전을 만들 수 있는 경우이므로 자연수 분할, 즉 중복 조합문제이다. 2. 풀이 아이디어(시행착오) 동전 n개로 k원을 만들 수 있는경우의 수를 구하는 문제이다. 언뜻 보기엔 일반적인 DFS로 재귀를 이용한 top - down방식으로 풀 생각이 들 수 있다. 예들 들어 1, 2원짜리 동전을 가지고 4원을 만드는 경우 3원(4 - 1원)에 1원을 더한 것과 2원(4 -..