본문 바로가기

알고리즘

(54)
프로그래머스42885 - 이중 for문 성능 올리기 size(), length(), length등 길이를 계산하는 함수를 최소화한다. (특히 종료조건에서) 반복문 안에서 배열 사용을 최소화 -> 임시 변수를 사용하자 break, continue문을 활용하자 정말 이중 for문이 필요할까? 다시 생각해보자 효율성 테스트에서 막혀서 계속 고쳐보았다. 원래 코드 import java.util.*; class Solution { public int solution(int[] people, int limit) { int count = people.length; Arrays.sort(people); int tempI; for(int i=count-1; i>0; i--){ tempI = people[i]; for(int j=i-1; j>=0 ; j--){ if(tem..
배열 내림차순 정렬 문제: 배열을 오름차순으로 정렬하려면 import java.util.Arrays; Arrays.sort(배열); 내림차순으로 정렬하려면 Arrays.sort(배열, Collections.reverseOrder()); 로 알고 있었는데 오류가 났다. /Solution.java:7: error: no suitable method found for sort(int[],Comparator) Arrays.sort(people, Collections.reverseOrder()); ^ method Arrays.sort(T#1[],Comparator
백준 11399 String[] -> Int[] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); String input2 = br.readLine(); int num = Integer.parseInt(input); String[] arr2 = input2.split(" "); in..
백준 16435 BufferedReader와 Scanner BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); String input2 = br.readLine(); int num = Integer.parseInt(input.split(" ")[0]); int length = Integer.parseInt(input.split(" ")[1]); String[] arr = input2.split(" "); Arrays.sort(arr); for(int i=0; i
탐욕(그리디) 알고리즘 쉬운 문제라서 한 번에 맞혔다. 근데 그리디로 푼 건지 모르겠어서 더 좋은 방법이 있나 찾아보는 중 class Solution { public int solution(int n, int[] lost, int[] reserve) { int[] student = new int[n]; for(int i : lost){ student[i-1] -=1; } for(int i : reserve){ student[i-1] +=1; } for(int i=0; i
1로 만들기 1. N = N - 1 로 만드는 방법 (비용 A) 2. N = N / K 로 만드는 방법 (비용 B , 나누어지는 경우에만 가능) N을 1로 만들 수 있는 최소 비용을 찾는 문제이다. while문의 첫번째 if문 조건이 핵심이라고 볼 수 있는데, n을 k로 나눌 수 없는 경우 선택지가 a밖에 없으므로 n을 k로 나누었을 때의 나머지 * 비용 a < 비용 b 이면 1번 방법을, 아니면 2번 방법을 택하는 방식이다. 사실 여기까지만 해서 틀렸다. 즉, n%k==0인 경우를 조건에 넣어주지 않았기 때문에 n이 k로 나누어 지는 경우 0으로 판단되어 2번째 방법이 아예 실행되지 않았기 때문이다. 여기까지는 내가 작성한 코드인데 DP로 짜는 방법이 궁금해서 찾아보았다. (사실 테스트에서 돌려보지 않아서 100%..
알고리즘27 LCA 보호되어 있는 글입니다.
알고리즘26-2 lowest common ancestor 한 단계 한 단계에 집중을 하자. a와 b의 공통 조상 중 제일 낮은 것 = LCA 노드 번호 2개를 주고 LCA x를 찾아라. 느린 방법: 각각 루트까지 올라간다. a에서 루트까지 타고 올라간 번호와 b에서 루트까지 타고 올라간 번호 중 겹치는 가장 낮은 번호 최악의 경우가 있을 수 있으므로 O(n) 하나의 트리에서 여러 경우를 찾아야 하는 경우가 많으므로 사실상 오래걸림 a에서 DFS에서 b를 찾는 방법도 있음 (또다른 느린 방법) 1,2,4,8...위의 노드를 기억한다. 모든 노드는 O(log n)개의 값을 가지고 있게 된다. 노드는 n개이므로 계산해야하는 값의 갯수는 O(nlog n) i는 모든 노드에 대해서 다 수행한다. A[i][0]는 한칸 위 이므로 parent임, root인 경우 -1로 표..