하이 나윤

Start CommonPrimeDivisors 문제 어제 답을 보고도 이해하지 못했기 때문에 다시 이해하는 시간을 가질거다.. 틀린 답을 내놓고 있다는데 이해가 잘 가지 않는다..

Start CommonPrimeDivisors 문제 풀다가 못 풀어서 다른 사람의 풀이를 봤는데 이것도 이해를 못했다.. 일단 gcd(a, b) = gcd(b, a%b)는 이해했고 gcd(a, b) = 1이면 공유하는 소수가 없다는 것도 이해했다. FibFrog 문제 끄엉

Start ChocolatesByNumbers 문제 N과 M의 최대 공약수를 구해야하는 문제였다. 유클리드 호제법을 이용해서 빠르게 최대 공약수를 구했다. CommonPrimeDivisors 문제 각각 나눠지는 소수가 같은지 파악하는 문제이다. 아니 근데..왜이렇게 풀었는지 이해가 안간다.. // 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[] B) { int resul..

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억이라.. 시간 초과에 직면할 것이다.