내가 보려고 만듬

서두 코딩테스트 문제를 푸는데 중복된 문자열을 제외해야 쉽게 풀 수 있는 문제가 있었다. 문제에서는 그룹단어를 판별하는 문제였는데, 그룹 단어는 문자열이 반복되거나 1개만 나오면 괜찮은데 다른 문자열이 나열된 이후 기존 문자열이 있으면 그룹단어가 아니다. ex1) acsssc 여기서 c가 처음에 등장하고, 뒤에 다시 등장하기 때문에 그룹단어가 아니다. ex2) acsssd 다시 반복되는 문자열이 없기 때문에 그룹단어다. 배열로 반복문 돌리면서 인덱스에 1을 더해가며 확인하고, 별짓을 다해서 어찌 풀긴 풀었는데 아무리 봐도 이게 효율적이라고 느껴지지는 않았다. 다른 풀이는 어떻게 되는지 구글링을 하는데, 꽤 문제를 오래걸려서 풀면서 여러 방법을 고민하다보니 다들 생각이 비슷했다. slice이나 split을..

cs에 대해 처음 공부하면서, 가장 많이 접한 것들 중 하나는 배열이다. array를 정의해보면 다음과 같다. Array 가장 기본적인 자료구조로, 논리적 저장 순서와 물리적 저장 순서가 일치한다. 그렇기 때문에 index로 해당 element에 접근할 수 있다. 찾고자 하는 element의 index를 알고 있으면 Big-O(1)에 해당 원소로 접근할 수 있다. array에서 맨 앞이나 맨 끝이 아닌 중간에 원소를 삽입, 혹은 삭제하는 과정을 생각해보자. 원초적인 방법은 자리를 만들어서 더하는 과정이다. 1. 해당 원소에 접근하여 O(1)로 작업 완료, 2. 더하거나 빼는 작업O(n)으로 구분된다. 접근하는 과정이 필요한 이유는, index를 알아야 하기 때문에 삽입할 자리를 만들기 위해서 기존 ind..

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

코테 문제를 풀다가 시간초과가 떴다. 테스트케이스는 금방 통과했는데, 1~8번 테스트케이스도 통과했는데, 9~12번은 시간초과가 떴다. 아마 답 자체는 맞았겠지만, 반복문을 3중으로 돌리고, 그 안에 조건문도 있고 여러 경우가 들어있어서 복잡해서 그런게 아닌가 싶다. 조금 간추려보기도 했는데, 각 수의 약수를 한 배열에 담아서 1과 자신이 바로 나오면 (소수의 조건대로) answer에 누적해보기도 했지만 10~12번이 시간초과가 떴다. 조건을 살펴보니 n은 2이상 1000000이하의 자연수이다. 어떻게 해도 알고리즘 생각하지 않고 풀면 시간초과가 뜨는 것 같다. 소수를 구하는 방법은 다양하겠지만 에라토스테네스의 체를 이용한 풀이가 일반적인 것 같다. 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전..

**이진탐색에 관한 설명만 필요하다면 가장 아래를 확인해주세요. 예시 여러 이름들이 나열된 배열이 있다. 이 중에서 특정 이름이 어디에 있는지 바로 알 수 있을까? 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를 처음에 추가하지만, 결과값인 ..

A 주머니에는 빨간 공 2개, 검은 공 2개가 들어있고, B 주머니에는 빨간 공 3개, 검은 공 1개가 들어있다. 주사위를 던져 3의 배수가 나오면 A주머니에서 공을 2개 꺼내고, 3의 배수가 나오지 않으면 B주머니에서 공을 2개 꺼낼 때, 주사위를 던져서 빨간 공과 검은 공을 1개씩 뽑을 확률을 고르시오. 1. 1/2 2. 9/5 3. 11/18 4.2/3 5. 13/18 주사위의 눈금 중 3의 배수는 3,6이므로 A주머니에서 공을 뽑을 확률은 2/6 = 1/3, B주머니에서 공을 뽑을 확률은 2/3이다. A주머니에는 빨간 공 2개, 검은 공 2개가 들어있고, B주머니에는 빨간 공 3개, 검은 공 1개가 들어 있으므로 각 주머니에서 2개의 공을 꺼냈을 때, 빨간 공과 검은..

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