내가 보려고 만듬

https://prpn97.tistory.com/88 [프로그래머스 | JavaScript] 소수 찾기 코테 문제를 풀다가 시간초과가 떴다. 테스트케이스는 금방 통과했는데, 1~8번 테스트케이스도 통과했는데, 9~12번은 시간초과가 떴다. 아마 답 자체는 맞았겠지만, 반복문을 3중으로 돌리고, 그 prpn97.tistory.com 이전에 소수 찾는 문제를 풀면서 에라토스테네스의 체를 사용했는데, 다른 방법으로 소수 관련된 문제를 풀어보고자 한다. 제곱근을 이용한 방법이다. 문제 설명 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개..

**이진탐색에 관한 설명만 필요하다면 가장 아래를 확인해주세요. 예시 여러 이름들이 나열된 배열이 있다. 이 중에서 특정 이름이 어디에 있는지 바로 알 수 있을까? 10개가 나열되어 있으면 처음부터 쭈욱 살펴보면 눈으로 금방 확인할 수 있을 것이다. 하지만 100개만 되더라도 특정 이름을 바로 확인하기엔 어렵다. 예를 들어서 전화번호부에서 원하는 이름을 찾고 싶은데, ㄱ부터 찾기 시작하는데 황씨인 사람을 찾으려면 처음부터 맨 끝까지 일일히 확인해야 한다. 하지만 우리는 황씨가 ㅎ으로 시작하므로 맨 마지막 쯔음에 있을 것을 짐작할 수 있다. 이처럼 힌트가 있다면 갈피를 잡는데 수월할 수 있지만, 힌트가 없다면 우리는 유추해야 한다. 100개의 이름을 찾는데 1부터 100을 찾아보는 것보다 좋은 방법이 있다..

https://prpn97.tistory.com/72 [Baekjoon | JavaScript] 10810 공 넣기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 매겨져 있다. 또, 1번부터 N번까지 번호가 적혀있는 공을 매우 많이 가지고 있다. 가장 처음 바구니에는 공이 prpn97.tistory.com **위 링크에 해당 문제가 있습니다. 조건에 따라 배열의 요소를 갱신하고 이전 요소는 상관이 없어지는 문제를 푸는데, 애초에 그 값을 구하지 않아도 되는데 굳이 반복을 하는 부분이 있다고 생각이 들었다. 문제로 예를 들어 순서대로 풀게 되면 다음과 같다. 3 3 0 0 0 3 3 4 4 0 1 1 1 1 0 1 2 1 1 0 3과 4를 처음에 추가하지만, 결과값인 ..

https://prpn97.tistory.com/63 [다이나믹 프로그래밍] LCS, LCSS 란? 그리면서 이해하기 - 1 처음 문제를 접하며 도무지 이해가 안되서 정리해서 포스팅하며 되새기기 위해, 또한 나처럼 헤매고 있는 사람들이 있다면 답을 알기보다 과정들을 통해 이 알고리즘에 대해 이해하는데 도움이 prpn97.tistory.com 1편에 설명이 있으니 참고해도 좋을 것 같다. Longest Common Subsequence 바로 최장 공통 부분수열에 대해 알아보려 한다. 먼저 최장 공통 부분수열의 길이에 대해 배워보자. 이번에는 LCS[i-1][j-1] 이전에 확인해야 하는 것이 있다. 두 문자가 다르다면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰값을 표시하고, 두 문자가 같..

처음 문제를 접하며 도무지 이해가 안되서 정리해서 포스팅하며 되새기기 위해, 또한 나처럼 헤매고 있는 사람들이 있다면 답을 알기보다 과정들을 통해 이 알고리즘에 대해 이해하는데 도움이 될까 싶어 하나하나 써내리려 한다. 구글링해보면, 많은 자료들이 있고, 함수로도 그림으로도 그려서 설명하는데, 바보인 나에겐 너무 어려워서, 초보의 시선에서 이해한대로 그려보려 한다. 먼저 LCS란 무엇인가. Longest Common Substring혹은, Subsequence 이다. 최장 공통 문자열 혹은 최장 공통 부분수열 이다. 문자열 ABCDEF / GBCDFE가 있다고 하자. 최장공통 문자열은 BCD / 최장 공통 부분수열은 BCDF, BCDE가 될 수 있다. 말 그대로 문자열을 비교해서 공통된 가장 긴 문자열 ..

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 작성. ex) 00시 00분 03초 = true 00시 04분 14초 = false let N = 5 let count = 0 let t = '' for(let i = 0; i

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있습니다. N에서 1을 뺍니다. N을 K로 나눕니다. 예를 들어 N이 17, K가 4라고 가정합시다. 이 때 1번의 과정을 한 번 수행하면 N은 16이 됩니다. 이후에 2번의 과정을 두번 수행하면 N은 1이 됩니다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 됩니다. 이는 N을 1로 만드는 최소 횟수입니다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하세요. N(2

첫 줄에는 숫자 3개가 주어진다. 각각 아래 배열의 크기, 주어진 수를 몇번 더할 것인지, 같은 수를 몇번 더할 수 있는지 주어진다. 이를 N,M,K라고 하자. 둘째 줄에는 N개의 숫자가 나열되어 있다. 같은 수를 K번을 초과하여 반복할 수 없다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 5 8 3 2 4 5 4 6 46 input = ['5 8 3','2 4 5 4 6'] let M = input[0].split(' ').map(Number)[1] //8 let K = input[0].split(' ').map(Number)[2] //3 let arr = input[1].split(' ').map(Number) let answer = 0; arr.sort((a,..

앞으로는 코딩테스트나 여러 루트로 알게 된 알고리즘에 대해 복습할 겸 따로 포스팅하려 한다. 물론 toString(3)으로 바로 3진법으로 바꿀 수 있겠지만, 내장함수를 쓰지 않고 수학과 친해져보는 시간을 가져보자. 아직 10진법보다 큰 수로 변환하는 방법은 내게 너무 어렵기 때문에 그 부분은 아쉽게도 내가 더 똑똑해지면 포스팅해보겠다.. function decimalToBaseN(n, base) { let result = ""; while (n > 0) { result = (n % base) + result; n = Math.floor(n / base); } return result || "0"; } 답은 이렇다. 위에 언급한 것처럼 10진법에서 3진법으로 바꾼다고 가정해보자. 9를 3진법으로 바꾸면,..