어흥

문제 링크: https://www.acmicpc.net/problem/9007 9007번: 카누 선수 이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그 www.acmicpc.net 1. 주의할 점 - 시간복잡도를 줄이려고 노력한다 - TestCase를 시작하기 전, 연산에 사용되는 모든 벡터 및 값을 초기화한다 2. 구현 - 4개의 집합(V[])을 2개씩 묶어서 각 집합의 모든 원소의 합을 twoSum[]에 저장한다 - 두 집합의 합을 구할때: O(N^2) - twoSum을 통해 Weight과 비교할 때(twoSum[0]의 길이를 A(=N^..

문제 링크: https://www.acmicpc.net/problem/22116 22116번: 창영이와 퇴근 A1,1에서 AN,N까지, 경로상의 최대 경사의 최솟값을 출력한다. www.acmicpc.net 1. 주의할 점 - 여러가지 푸는 방식이 존재하지만, 1씩 증가시키면서 10억까지 테스트 → TLE 발생 2. 구현 - BFS+이분탐색을 통해 차이가 Mid이하라면 전진이 가능하다고 판단 - L=0, R=10억, Result = R-L로 초기화 하고 이분탐색을 시작한다 - Mid = L+(R-L)/2를 통해 Mid값을 갱신하고, BFS()가 가능하면 Result의 값도 갱신한다 import java.util.*; import java.lang.*; import java.io.*; class Main {..

문제 링크: www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 1. 주의할 점 - 세그먼트 트리에 대해 알고 있어야 한다 - 우선순위가 높은 사탕을 뽑을 방법은? 2. 구현 - Tree[]를 이용하여 세그먼트 트리를 구성한다. 이때, Tree의 크기는 사탕의 우선순위가 1~1000000이므로 N=1000000일때 완전이진트리의 높이를 구하고, 비트연산으로 배열의 메모리를 동적으로 할당한다 - Update() 함수를 통해 idx가 포함된 ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 1. 주의할 점 - 브루트포스로 접근하지 않는다 - 구하려는 수의 범위가 크다 + O(N^2)의 경우로는 TLE가 발생할 것 같다 → 최소 O(NlgN)의 방법으로 접근한다 2. 구현 - 구하려는 답의 크기가 1~10억 사이의 수 → 이분탐색으로 접근 - 파라미터로 전달받은 Rocks의 수가 정렬되어 있지 않다 -> 이분탐색을 위해 정렬 - V 벡터에..

문제 링크: programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 1. 주의할 점 - 숫자가 크다 → 단순한 풀이로 접근하려고 하면 TLE가 발생한다 - 벡터/배열의 index 범위를 벗어나는지 확인한다 2. 구현 - 이분탐색을 통해 접근한다. 중간값만큼의 사람들이 넘어갈 수 있는가? - 돌의 가장 큰 크기가 200,000,000이므로 이보다 1 더 크게 R을 설정한다. L은 0으로 설정한다 - 0번째 돌까지 뛰는것도 1만큼 뛴것이기 때문에 idx를 -1로 설정하고 점프 크기(J)를 1~K까지로 설정한다 - 현재 위치에서 뛰어서 징검다리의 반..

문제 링크: www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 1. 주의할 점 - 이분탐색을 사용하는 LIS 알고리즘에 대해 알고 있어야 한다 - DP[] 배열을 TC마다 초기화한다 2. 구현 - 입력 받는 수들을 Arr[] 배열에 저장하면서 DP[] 배열을 전부 0으로 초기화한다 - DP[0] = Arr[0]과 idx=0을 초기화한다 - i: 1~Num-1까지 Arr[]에 있는 모든 수들에 대해 Arr[i]의 값이 DP[idx]보다 크다면 DP[++idx]..

문제 링크: www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 1. 주의할 점 - 일반적으로 알고 있는 LIS의 공식은 길이를 구하는 것으로, 실제 LIS를 구하는 것은 추가 작업이 필요하다 2. 구현 - 모든 수를 Info 구조체 형태의 Vector로 입력 받고, 첫 번째 인자를 기준으로 오름차순 정렬한다 - DP[] 배열을 통해 LIS의 간략한 형태를 구하고, Pos[] 배열을 통해 추가 또는 수정된 원소가 몇 번째 DP 원소와 바뀌었는지 저장한다 - ..

문제 링크: www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 1. 주의할 점 - LIS(가장 증가하는 부분수열)에 대해 알고 있어야 한다 2. 구현 - 모든 수에 대한 입력을 Arr[] 배열에 받는다 - DP[idx] 배열 통해 가장 긴 증가하는 부분 수열을 나타낼 때, idx번째로 작은 수를 DP[idx]에 저장한다 - 만약 새로 비교하는 값(Arr[i])가 DP[] 배열의 가장 마지막 원소(DP[idx])보다 크면, DP배열에 새로 추가한다..