어흥

문제 링크: www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 1. 주의할 점 - 모두 비교할 경우, 최악의 경우 O(N*M)으로 TLE가 발생한다 - 둘중 하나는 lgN이나 lgM으로 바꿔야 TLE가 발생하지 않는다 - 사대의 X값이 정렬되어 있지 않다. 왜? 2. 구현 - 입력 받은 사대 Arr[]를 오름차순으로 정렬한다 - 동물들의 위치를 X[], Y[]에 할당 받는다 - 각 동물을 기점으로 사대까지의 거리가 Len보다 작거나 같다면, Result++하고..

문제 링크: www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 1. 주의할 점 - LIS 알고리즘에 대해 알고 있어야 한다 - 이분탐색을 통한 LIS를 수행한다 2. 구현 - 모든 수를 Arr[] 배열에 담는다 - DP[idx] 배열에 가장 긴 증가하는 부분수열 중에서 idx번째에 위치한 수를 저장한다 - DP[0] = Arr[0]을 담은 후, 1번째 index부터 탐색을 시작한다 - 만약 DP[Idx]보다 Arr[i]가 크다면, 가장 긴 ..

문제 링크: www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 1. 주의할 점 - 4개의 수를 어떤 방식으로 뽑을 것인지 잘 생각한다 - 정렬 이후, 인접합 4개를 조작하여 답을 구할 경우, 반례가 존재한다. 반례) 6 1 2 1000 2000 10001 10002 답: 0 2. 구현 - 조합을 통해 2개 공의 합이 나타낼 수 있는 높이를 벡터에 저장한다. 이때, 벡터는 사용한 번호 2개, 2개의 합 총 변수가 3개인 구조체 형태..

문제 링크: www.acmicpc.net/problem/9879 9879번: Cross Country Skiing The cross-country skiing course at the winter Moolympics is described by an M x N grid of elevations (1 = 0 && nx row >> col; int l = 0, r = 0, mid, result; for (int i = 0; i > arr[i][j]; r = max(r, arr[i][j]); } for (int i = 0; i ..

문제 링크: www.acmicpc.net/problem/1800 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 1. 주의할 점 - 이분탐색 + 다익스트라를 이용하여 문제를 해결한다 2. 구현 - 2가지의 방법으로 풀었으며, 다익스트라는 우선순위큐를 활용하여 푸는 방법이 훨씬 빠르다 - Result의 값은 -1로 초기화한다(N번 컴퓨터까지 도달하지 못할 경우를 대비) - Dijkstra() 함수만 바뀐다 - 메인 함수에서 케이블선에 대한 정보를 받을 때, 케이블선의 최..

문제 링크: www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 1. 주의할 점 - 메모리 제한이 작다. 메모리를 최대한 적게 쓰도록 한다 - Map을 1개 사용하고, 이분탐색을 통해 답을 유추한다 2. 구현 - A배열과 B배열을 입력받은 후, A배열에서 만들 수 있는 부분 배열을 Ma Map에 저장한다(숫자, 해당 숫자를 만들 수 있는 개수) - B배열의 부분 배열을 구할 때마다 Ma..

문제 링크: https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당� www.acmicpc.net 1. 주의할 점 - 용액을 합성할 때 항상 사용될 용액 A를 미리 지정해 놓는다 - 이분탐색을 사용한다 2. 구현 - 용액 Num개를 입력 받는다 - For문을 통해 용액 A를 Arr[0]~Arr[Num-1]사이에 모든 용액을 사용한다(사실 Num-2까지만 해도 된다) - 용액 A를 Arr[i]로 골랐다면, Low = i+1, High = num-1을 가리..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 1. 주의할 점 - 이분탐색으로 해결한다 - Right 포인터의 값이 Int값을 벗어날 수 있다 (Long Long으로 형변환 필요) -> 8번 TC 2. 구현 - Tip) Mid의 값을 구할 때 Left+(Right-Left)/2로 한다. Right+Left/2로 할 경우, Int 혹은 Long Long의 범위를 벗어나면 음수값이 저장되므로 사전에 예방한다. ..