하이 나윤

Start 성능 개선을 하러 가보겠습니다. CountNonDivisible 문제 에라토스테네스의 체 방법을 통해 소수를 구하는 방법을 알고 있었는데, 까먹었다... 1. 소수를 찾고 2. 배열에서 각 요소마다의 개수를 찾고 3. 1이나 소수일 경우 전체 요소의 개수에서 1과 소수의 개수를 뺀다. 4. 그렇지 않을 경우 배열에서 나눠본다. 했는데, 아래와 같은 결과가 나왔다. 시간복잡도가 N^2인데 이전 풀이도 N^2였는데, 좀 더 안 좋은 풀이인가보다.. 소수가 아닐 경우 전체 배열을 돌면서 나눠보는 방법 대신 소수가 아닌 수의 공약수를 구해서 배열에 존재할 경우 빼도록 구했다. 공약수를 구하는 방식은 이전 lesson이었던 lesson 10에서의 방법을 통해 구했다. 성능은 괜찮아진 것 같은데, 런타임..

야무지게 설날 잘 쉬고..Start flags 문제 정상마다 flag를 꽂고 싶어도 distance와 flag를 고려해서 꽂아야하는 문제. 많은 flag를 들고 등산을 가면 distance를 그만큼 넓게 해야하고 적은 flag를 들고 등산을 가면 distance는 좁아지는 대신 많은 flag를 꽂지 못한다. 퇴화라는 게 이런걸까.. 설날이 뭐..얼마나 된다고..이지경으로 퇴화할 수 있는걸까.. peak가 하나도 없을 경우 peak 목록을 구한 ArrayList에서 get 메소드로 element를 구해오면 안 되었다.. 아래 네모 부분을 추가해서 예외처리하였다. 정확도에서 또 체크해보니 정답보다 큰 값을 리턴하고 있었다. 현재 나는 최소 flag 계산식을 바탕으로 가장 큰 peak 인덱스에서 가장 작은 p..

Start Flags 문제 peak P는 배열 A에서 A[P - 1] A[P + 1] 을 만족해야한다. 이 peak P 위치에는 Flag를 꽂을 수 있고 꽂으려고 하는 Flag의 수만큼 간격을 띄워야한다. 어제 마지막보다 정확도는 조금 올랐는데 내가 짠 로직 자체가 문제가 있는 것 같아서 새롭게 다시 짜려고 한다. 1. peak 수와 위치를 파악했다. 2. 파악한 peak 수만큼을 최대 Flag 개수라고 두고 '최대 Flag 개수'에서 1까지 대입해보며 꽂을 수 있는 가장 큰 Flag를 구한다. 최대 flag 일 경우 flag 개수는 많지만 그만큼 distance를 띄워야하기 때문에 많은 flag를 꽂을 수가 없다. 그래서 최대 flag 개수부터 1까지 대입해보면서 꽂을 수 ..

Start [2023-01-18] 시작 화면과 동일하게.. // you can also use imports, for example: import java.util.*; // you can write to stdout for debugging purposes, e.g. // System.out.println("this is a debug message"); class Solution { public int solution(int[] A) { int size = A.length; boolean isPeak = false; int peakSize = 0; int result = 0; boolean[] peaks = new boolean[size]; if (size A[i+1]) { peaks[i] = tru..

Start Flags 문제 flag를 들고 산에 가서 peak에 flag를 꽂을건데 flag와 flag간에는 distance는 flag의 개수보다 크거나 같아야한다. 그래서 최고로 많이 들고 갈 수 있는 flag는 몇 개인 것인가..? 하는 부분인데.. flag를 적당히 들고가야지 안그러면 오히려 가지고 간 것보다 더 적게 꽂고 올 수 있고 flag를 조금 들고 가면 더 꽂을 수 있는데 더 못 꽂고 올 수 있다.. 최대 입력값이 400,000이라서 peak는 단일 for문으로 찾을 수 있을 것 같다. 문제는 flag인데 peak는 400,000일 경우 최악의 경우 199,999개가 나오고 약 200,000개라고 쳤을 때 flag의 개수를 구하기 위해 이중 for문을 돌릴 경우 400억 가까이..? 나올 ..

Start 어제 풀다가 내팽겨친 [2023-01-16]..그대로.. MinPerimeterRectangle 문제 A * B = N으로 약수를 구해서 푸는 문제라고 생각했다. 문제는 내가 아는 약수를 구하는 알고리즘은 시간복잡도가 너무 컸다. 1부터 하나씩 대입해보는 방식으로 O(N)이라 입력값이 너무 클 경우 제한된 시간을 초과하게 된다. 그래서 찾아보았는데, [알고리즘] 효율적으로 약수를 찾는 알고리즘 이라는 글을 찾아보게 되었다. 블로그에서 알게된 방법인데 1부터 N의 제곱근까지만 0으로 나누어 떨어지는지 확인하면 된다고 한다..! 나누어떨어진 수를 N에 나누면 추가로 약수를 구할 수 있다. 그래서 위의 방식을 이용해서 문제를 풀 수 있었다. 1부터 N의 제곱근까지의 수까지만 N에 나눠서 0이 나오면..

Start CountFactors 문제 공약수를 구하는 문제인데, 1부터 하나씩 나눠보면 구할 수 있겠지만 입력값이 20억이라.. 시간 초과에 직면할 것이다.

Start Codility는 내가 문제 푸는 과정을 전부 다 저장하는 Task timeline기능을 제공하는데 대부분 다 저런 느낌이다.. 영어라.. 해석하는데 시간을 한바가지 쓰고 좀 이해됐다 싶으면 와다다다다다다다다 푸는 식.. MaxProfit 문제 A[P] - A[Q]를 해서 최댓값을 구하는 문제 0

Start Dominator 문제 배열에서 가장 많이 나온 요소의 인덱스를 찾는 문제. 정확도에서 문제가 있었는데.. 빈 배열에 대한 처리를 해주지 않아서 그런가 싶다 빈배열 처리를 해줘도 문제가 풀리지 않는다.. 위와 같이 해서 문제를 풀었다. 1. 빈 배열을 처리를 하지 않아서 문제가 되었다. 2. dominator는 배열의 절반을 넘어서는 요소를 말하는 건데 처음 구현했을 때는 배열의 절반 이상으로 해서 문제가 되었다.

Start Brackets 문제 스택하면 많이 만나게 되는 괄호 문제였다. 그렇다고 잘 풀거라는 뜻은 아니고.. 반례에 대한 고려를 전혀 하지 않아서 그런 것 같다 내가 한 반례 처리는 오로지 empty일 경우만.. 했다.. 찾아보니 peek을 했을 때 stack의 크기가 0일 경우 EmptyStackException 예외를 던진다. 그러니까 내 코드에서 닫힘 괄호({, (, [)가 빈 문자열에 들어가는 경우 런타임에러가 났을 거다. stack이 empty가 아닐 경우에만 peek 메소드를 호출하도록 조건을 추가해주니 통과했다. Fish 문제 아래로 내려오는 물고기(1)와 위로 올라가는 물고기(0)를 고려하기 위해 위로 올라가는 물고기 직전에 아래로 내려오는 물고기가 있을 경우에만 조건 고려하도록 했다...