Algorithm

BOJ 15686 치킨 배달

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 아이디어 1. map을 돌면서 집과 치킨집의 좌표를 저장 2. 저장해둔 리스트에서 치킨 집을 M개 선택 - 중복없이 순서 상관 없이 뽑는 조합문제 2. 각 경우마다 치킨 거리를 구해 최솟값 갱신 처음에 map을 보자마자 고정관념으로 map 전체를 돌면서 완전탐색을 해야할 거라고 생각했는데 그렇게 하면 너무 복잡해진다. 어짜피 거리를 구하는 문제이기 때문에 거리 구하는 공..

BOJ 2470 - 두 용액 (투 포인터)

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net - 서로 다른 두 용액을 더해서 합이 최대한 0에 가깝게 만드는 문제 - 산성 용액 (1 ~ 10억) - 알칼리성 용액 (-10억 ~ -1) 아이디어 기존의 이분탐색 풀이법을 생각해보면 먼저 용액들을 정렬을 해준 후 이분탐색을 통해 답을 구했었다. 새로운 관점으로 투 포인터를 활용해서 풀이를 해보자 포인터 L과 R을 사용한다. L은 제일 작은 원소(최소)를 가리키..

BOJ 2230 - 수 고르기

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net N개의 정수로 이루어진 수열 A (1 ≤ N ≤ 10만) 수열 A의 각 원소는 (0 ≤ |A[i]| ≤ 10억) 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우 (0 ≤ M ≤ 20억) 아이디어 배열 A에서 두 수를 골라서 차이가 M 이상인 경우를 찾기 위해 먼저 모든 경우의 수를 생각해 봤다. 배열 A를 오름차순 정렬 후 이중 for문으로..

BOJ 15565 - 귀여운 라이언

https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 인형 총 N개 (라이언 인형 K개 어피치 인형 N-K개 ) (1 ≤ K ≤ N ≤100만) 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기 아이디어 연속 부분 수열에 관한 문제이므로 투 포인터 알고리즘으로 먼저 접근해보았다. L과 R 포인터를 설정한 후 R 포인터를 라이언 인형이 K개가 되도록 옮겨준 후 답을 갱신한다. 그 후 L 포인터를 다음 라이언 인형까지 옮겨준 후..

[Algorithm] Two Pointers

투 포인터 알고리즘 화살표 두 개에 의미를 부여해서 탐색 범위를 압축하는 방법 1차원 배열 위에 2개의 포인터를 만드는 경우 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동 2개의 포인터가 양 끝에서 서로를 향해 이동 관찰을 통해서 문제에 등장하는 변수 2개의 값을 투 포인터로 표현하는 경우 투 포인터 팁 키워드 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로" 라는 말이 있으면 한번쯤 투포인터 알고리즘을 생각해볼 필요가 있다. 곱의 최소 - A x B를 최소로 하려면 A가 커지면 B가 작아져야 한다. 이 경우가 위에서 언급한 관찰을 통해서 문제에 등장하는 변수 2개의 값을 투 포인터로 설정하는 경우이다. BOJ 1806 - 부분합 https://www.acmicpc.net..

BOJ 20444 - 색종이와 가위

https://www.acmicpc.net/problem/20444 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 색종이를 자를 때에는 한 변에 평행하도록 n번의 가위질을 했을 때 k개의 색종이 조각을 만들 수 있을까? n번의 가위질 (1 ≤ n ≤ 2^31-1) k개의 색종이 조각 (1 ≤ k ≤ 2^63-1) : long형 변수 아이디어 0.1초라는 적은 시간에 넓은 탐색 범위 안에서 최적의 조건을 찾아야 하므로 이분탐색으로 먼저 접근해보았다. n번의 가위질을 했을 때 k개의 색종이 조각을 만들 수 있는 지 판단해야 한다. 하나씩 해보니 아래와 같은 규칙을 발견했다. 가위질 수 = (가로로 자르는 횟..

BOJ 3079 - 입국심사

문제 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 상근이와 친구들 M명 (1 ≤ M ≤ 10억) 입국심사대 N개 (1 ≤ N ≤ 10만) k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk (1 ≤ Tk ≤ 10억) 모든 사람이 심사를 받는데 걸리는 시간이 최소가 되도록 아이디어 ' 최소 '라는 키워드가 나와서 이분탐색으로 먼저 접근해보았다. 원래 문제 N개의 심사대에 M명의 사람이 심사받을 때 모든 사람..

BOJ 6236 - 용돈 관리

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net N일 동안 사용 (1 ≤ N ≤ 100,000) 통장에서 M번만 출금 (1 ≤ M ≤ N) i번째 날에 이용할 금액 (1 ≤ 금액 ≤ 10000) 현우가 통장에서 인출할 최소 금액 K 값은? 아이디어 ' 최소 ' 키워드가 나왔으므로 이분 탐색으로 먼저 접근해보았다. 원래 문제 N일동안 통장에서 M번만 출금할 때 한번에 인출할 최소 금액 K 값은? 최소 금액 K를 매개 변수로 설정하고 문제를 뒤집어서 Y..

BOJ 2343 - 기타 레슨

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 블루레이 N개의 강의 (녹화 순서 준수) (1 ≤ N ≤ 100,000) 블루레이 M개 (모두 같은 크기) (1 ≤ M ≤ N) 기타 강의 길이 리스트 - 분 단위로(자연수)

BOJ 2110 - 공유기 설치

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 수직선 위 N개의 집 (2 ≤ N ≤ 200,000) 각 집의 좌표 xi (0 ≤ xi ≤ 10억) 공유기 C개 (2 ≤ C ≤ N) 아이디어 집이 5개이고 공유기가 3개인 경우 C개의 공유기를 몇몇 집에 설치할 것인데 가장 인접한 공유기 사이의 거리를 최대가 되도록 설치할 것이다. ' 최대 ' 라는 키워드가 나왔으므로 이분탐색을 먼저 생각..