n . n

https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 다이나믹 프로그래밍. 현재 위치를 [row][col]이라고 할 때, 현재 위치에서 가질 수 있는 합은 (왼쪽 상단에서 온 값 or 오른쪽 상단에서 온 값) + 현재 위치의 숫자 이므로 두 값을 비교하여 더 큰 값을 dp[row][col] 위치에 저장하는 식으로 탐색하면 리프 위치에서의 최댓값을 구할 수 있음 public class Solution { public static int solution(int[][] triangle) { in..

https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 시간도 넉넉하고.. 걍 정신똑바로차리고풀면되는문제!!!! 더 깔끔하고멋들어지게 풀고 싶었는데 걍 이게 최선인듯 하다.. ? 자리가 모두 차있을 때 1. 나중에 또다시 사용되지 않는 플러그를 뽑음 2. 제일 나중에 사용되는 플러그를 뽑음 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader..

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 시작시간 순으로 정렬 후 겹치는 부분이 있는지 판단하고 있을 때에는 겹치는 부분으로 left, right 범위를 조정 없을 때에는 새로운 카메라 범위 값으로 left, right 범위를 조정함 import java.util.Arrays; import java.util.Comparator; public class Solution { public static int solution(int[][] routes) { int answer = 0; //시작시간 순 ASC Ar..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 입력받은 수들의 중간값을 출력해야 함. 일반적으로 정렬 후 중간위치의 인덱스를 탐색하면 정렬이 nlogn의 시간복잡도를 가지므로 시간초과가 남 -> 두 개의 priority queue를 이용하여 중간 값 반환 숫자들을 반반씩 저장, 하나의 queue는 최대값을(maxheap), 다른 하나의 queue(minheap)는 최소값을 뽑아내어 비교 후 중간값을 구함. + 어지간한 문제에서..

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 효율성 테스트의 시간초과 때문에 쌩고생 했음.. 1) int 배열을 Integer ArrayList 배열로 변환 -> Collections.sort 정렬 -> new ArrayDeque(list) 로 덱 생성 효율성테스트 시간초과 5 ... ArrayList list=(ArrayList) Arrays.stream(people).boxe..

Arrays.sort()의 경우 primitive type Arrays를 정렬할 경우 Dual-pivot quicksort가 수행되며 이는 최악의 경우 O(n^2)이다. Collections.sort()의 경우 Arrays.sort() 함수를 호출하고는 있지만 위와 같이 MergeSort, TimSort(mergeSort + insertSort) 를 사용하고 있음을 보여주며, 이는 최악의 경우에도 O(nlogn)의 시간복잡도를 갖는다 한다. (참조 지역성의 원리를 이용하여 최적화한...) + 참조 지역성의 원리에 의하여 Array 는 값들의 주소가 연속적인 값을 가지기 때문에 C(참조 지역성이 정렬에 영향을 주는 정도)의 값이 작으며, 따라서 퀵 정렬로도 충분한 성능을 제공할 수 있다고 함. 하지만 Co..

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 문자열의 최대 길이가 7이므로, 7개의 문자로 만들 수 있는 최대 문자열의 수 7! ≒ 5000 문자의 개수가 N일 때 만들 수 있는 문자열의 길이는 1,2,3,,,N 이므로만들 수 있는 문자열의 최대 개수는 약 10000 라고 할 수 있음(어림잡음..) 더하여 모든 문자열에 대해 소수임을 판별해야 하는데 이는 소인수분해 방식을 통해 √N 번의 연..

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net ArrayList 삭제의 시간복잡도는 O(n) 인데.. 이걸 헷갈려서 삽질함 1) 처음 시도 ArrayList에서 보석을 가격 DESC, 무게 ASC 순으로 정렬 후 보석을 하나씩 뽑아 c++ 에서 사용하던 lowerbound라는 함수를 만들어 적절한 가방을 찾으려 함 -> 사용한 가방에 대하여 remove() 처리가 필요했는데, Arr..

https://programmers.co.kr/learn/courses/30/lessons/42747 코딩테스트 연습 - H-Index H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표 programmers.co.kr import java.util.ArrayList; import java.util.Arrays; import java.util.stream.Collectors; public class Solution{ public static int solution(int[] citations) { int answer = 0; ArrayList a..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 작은 수끼리 합하여야 최종 합이 최소가 되므로 카드 숫자가 오름차순으로 정렬되도록 하기 위하여 PriorityQueue 사용 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader..