본문 바로가기

알고리즘 별 문제 정리

 (33)
[C++] 백준 1018: 체스판 다시 칠하기 문제 이해- M * N 크기의 보드가 주어진다.- 보드는 검은색 또는 흰색으로 칠해져있다.- 이 보드로 체스판을 만들 예정인데 8 * 8 크기이고, 검은색과 흰색이 번갈아 칠해져야 한다.- 체스판은 그러므로 맨 왼쪽 위칸이 흰색인 경우와 검은색인 경우 두 가지만 존재한다.- 8 * 8 크기로 자른 뒤, 다시 칠해야 하는 정사각형의 최소 개수를 구하라. - N, M; 보드의 크기 (8 ~ 50)- B: Black- W: White - 8*8로 자른 뒤 다시 칠해야하는 정사각형 개수의 최솟값 - 시간 제한: 2초- 메모리 제한: 128MB  문제 풀이브루트포스 혹은 분할정복을 써야한다고 생각했는데보드의 크기가 작아 브루트포스로도 충분히 풀 수 있다고 생각했다.  처음에는 8*8로 자른 뒤, 처음 시작이 W인..
[C++] 백준 1269: 대칭 차집합 문제 이해- 자연수를 원소로 갖는 공집합이 아닌 집합 A와 B가 있다.- 대칭 차집합: (A - B) U (B - A) - 시간 제한: 2초- 메모리 제한: 256MB - 집합 A와 B의 원소의 개수 (1 ~ 200,000, 10^5)- 집합 A와 B의 원소의 값들 (1 ~ 100,000,000, 10^8) - 두 집합의 대칭 차집합의 개수를 출력하라.  문제 풀이A * B의 시간 복잡도는 O(N^2)이 되어 시간초과이다.그러므로 당연히 완전 탐색은 아니었고, 처음에 시도한 방법은 이분 탐색이었다. A와 B의 원소의 개수의 합을 미리 초기화해둔 뒤 A의 원소만 배열에 넣어두고,B의 원소를 입력받을 때 존재할경우 합에서 -2씩 해준뒤 그 값을 출력해줬다. 이 방법으로도 AC를 받기는 했지만, 문제 알고리즘..
[C++] 백준 1920: 수 찾기 문제 이해- N개의 정수 A[1] ... A[N]이 주어질 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하라. - N: 주어지는 정수의 개수 (1 ~ 100,000, 10^5)- A[1] ... A[N] (-2^31 ~ 2^31)- M: 주어지는 X의 개수 (1 ~ 100,000, 10^5)- X: 찾아야하는 정수 (-2^31 ~ 2^31) - 시간제한: 1초- 메모리제한: 128MB - M개의 줄에 출력하고, 존재할경우 1, 존재하지 않을경우 0을 출력하시오.  문제 풀이먼저 가장 쉬운 완전 탐색을 생각했을때N이 10^5, M이 10^5이므로 N * M은 10^10이 되어 가볍게 시간초과가 된다.  그러므로 더 시간 복잡도가 작은 방법을 선택해야 하는데 바로 이분탐색이다.이분 탐색은 ..
[C++] 백준 2212: 센서 문제 이해- 도로에 센서와 그것을 관리할 집중국을 설치할 예정이다.- 센서는 적어도 하나의 집중국과 통신이 가능해야 한다.- 각 집중국은 수신 가능 영역을 조절할 수 있다. - N: 센서의 개수 (1 ~ 10,000, 10^4)- K: 집중국의 개수(1 ~ 1,000, 10^3) - 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 구하여라.  문제 풀이문제에서 원하는 것은N개의 센서가 있을 때, 이들을 K개의 영역(집중국의 영역)으로 나누는 것이다.그럼 수신 가능 영역의 길이의 합이 최소가 되도록 K개의 영역으로 어떻게 나눌까?  센서들을 K개의 영역으로 나누면 K-1개의 영역 사이의 구간이 생긴다.센서들끼리의 거리를 먼저 구한 뒤, 거리가 먼 k-1개의 구간을 영역 사이의 구간으로 하면 되..
[C++] 백준 1781: 컵라면 문제 이해- 각 문제는 데드라인과 보상이 별개로 존재한다.- 데드라인은 N 이하의 자연수이다.- 각 문제에 대한 보상과 총 보상은 2^31보다 작은 자연수이다. - 시간 제한: 2초- 메모리 제한: 256MB - N: 숙제의 개수 (1 ~ 200,000, 10^5)- (데드라인, 풀면 받는 컵라면 수) - 동호가 받을 수 있는 최대 컵라면 수를 구하라.  문제 풀이처음에 접근한 방식은 하루에 풀 수 있는 문제는 1개이므로 데드라인과 보상을 pair형으로 묶은 뒤,첫 번째 인자를 데드라인으로 올림차순으로 정렬같다면 두 번째 인자인 보상을 내림차순으로 정렬하여 진행하였다.정렬을 통해 그리디가 구현되었다고 생각하고슬라이딩 윈도우로 하루마다 선택해주는 방식으로 진행했는데,41 502 303 603 70위와 같은..
[C++] 백준 3109: 빵집 문제 이해- 첫째 열: 근처 빵집의 가스관- 마지막 열: 원웅이의 빵집- 파이프는 그러므로 첫째 열에서 시작하여 마지막 열에서 끝나야 함- 파이프의 방향은 우측 위, 우측, 우측 아래만 가능- 각 칸을 지나는 파이프는 1개만 존재할 수 있다. - 시간 제한: 1초- 메모리 제한: 256MB - R: 행의 개수 (1 ~ 10,000, 10^4)- C: 열의 개수 (5 ~ 500, 10^2) - 원웅이가 설치할 수 있는 가스관과 빵집을 연결하는 파이프라인의 최대 개수 문제 풀이DFS를 써야함은 문제를 보면 알 수 있다.근처 빵집에서 시작해서 원웅이의 빵집까지 연결해야 하니 말이다.  그런데 파이프의 최대 개수를 어떻게 구할 수 있을까???답은 바로 그리디 알고리즘의 적용이다.  그렇다면 그리디 알고리즘은 어..
[C++] 백준 17420: 깊콘이 넘쳐흘러 문제 이해- 기프티콘이 N개 있으며 사용 가능 기한이 존재한다.- 기한은 연장이 가능한데 한 번 연장하면 30일이 늘어난다.- 기한 연장은 최소한으로 하려 한다.- 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용 가능하다.- 기한이 같은 게 여러 개면 아무거나 사용할 수 있다.- 하루에 여러 개를 사용하거나 연장하는 것 모두 가능하다. - 시간 제한: 1초- 메모리 제한: 512MB - N: 기프티콘의 수 (1 ~ 100,000, 10^5)- Ai: 기프티콘의 남은 기한(1 ~ 1,000,000,000, 10^9)- Bi: i번째 기프티콘의 경우 Bi일 뒤에 사용할 계획이다.(1 ~ 1,000,000,000, 10^9) - 기한 연장을 해야 하는 최소 횟수를 출력하라.※ 32비트 정수를 넘을 수 있다..
[C++] 백준 2637: 장난감 조립 문제 이해- 완제품: 기본 부품 + 중간 부품 - 시간 제한: 1초- 메모리 제한: 128MB - N: 완제품의 번호 (3 ~ 100, 10^2)- M: 관계의 개수 (3 ~ 100, 10^2)- 관계(완제품, 중간 부품 or 기본 부품, 필요한 개수) - 하나의 완제품을 만들기 위하여 필요한 기본 부품의 종류별 개수  문제 풀이기본 부품과 중간 부품을 조합하여 완제품을 만든다는 점에서 선행 관계가 있다고 볼 수 있다.즉 위상 정렬을 사용하여 푸는 문제이다.  개수를 구해야 하므로 DP를 사용해야 할 거 같은데 시간을 구하는 여러 문제들과 달리 개수를 구하는 문제였다. 문제의 입력이 주어지는 것에서 힌트를 얻을 수 있는데,완제품에서 시작하여 위상정렬을 시작하면 문제를 쉽게 풀 수 있다.   1. dp[n..

티스토리툴바