본문 바로가기

Problem Solving

 (67)
[C++] 백준 1406: 에디터 문제 이해- 한 줄로 된 에디터를 구현하라.- 에디터는 영어 소문자만 기록이 가능하고, 최대 600,000 글자까지 지원한다.- 커서는 문장의 맨 앞, 중간, 맨 뒤까지 어디든 위치가 가능하며, 길이가 L인 문자열에서는 L+1가지의 위치에 있을 수 있다.- 명령어-- L: 커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)-- D: 커서를 오른족으로 한 칸 옮김 ( 커서가 문장의 맨 뒤이면 무시됨)-- B: 커서 왼쪽에 있는 문자를 삭제-- P $: $라는 문자를 커서 왼쪽에 추가- 커서의 처음 위치는 문장의 맨 뒤이다. - 문자열 (길이가 N(1 ~ 100,000, 10^5), 소문자로만 구성됨)- M: 입력할 명령어의 개수 (1~500,000, 10^5)- 명령어들 - 모든 명령어를 수행..
[C++] 백준 13549: 숨바꼭질 3 문제 이해- 수빈이는 동생과 숨바꼭질을 하고 있다.- 수빈이는 현재 점 N에 위치해있고, 동생은 K에 위치해있다.- 수빈이의 위치가 X일 때, 수진이는 1초 후에 X+1 or X-1로 걷거나 0초 후에 2*X 위치로 순간이동 할 수 있다.- 수빈이가 동생을 찾을 수 있는 가장 빠른 시간을 구하여라 - N: 수빈이의 위치 (0 ~ 100,000, 10^5)- K: 동생의 위치 (0 ~ 100,000, 10^5) - 수빈이가 동생의 위치까지 도달하는 가장 빠른 시간을 출력하라. - 시간 제한: 2초- 메모리 제한: 512MB  문제 풀이(BFS)처음에 이 문제에 접근할 때는 우선순위 큐와 BFS를 활용해서 풀어보려 했다.  #include #include #include #include #include us..
[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를 써야함은 문제를 보면 알 수 있다.근처 빵집에서 시작해서 원웅이의 빵집까지 연결해야 하니 말이다.  그런데 파이프의 최대 개수를 어떻게 구할 수 있을까???답은 바로 그리디 알고리즘의 적용이다.  그렇다면 그리디 알고리즘은 어..

티스토리툴바