Intuition 두 배열을 각각 살펴보고 공통되는 것을 결과배열에 담아주면 되겠다고 생각했다. Approach >두 배열을 순회하며 등장할 수 있는 숫자 0~1000을 count하는 배열 n1, n2를 만들었다. 이때, 원소 i의 개수는 n[i]에 저장된다. res는 결과값을 담을 배열, cnt는 공통 element 개수를 세는 변수다. >n1과 n2에...

Intuition 최대로 나올 수 있는 Number of Nodes가 30개이기 때문에 연결 리스트를 순회하면서 각각의 Node를 포인터 배열에 저장해놓는다면, 원하는 위치의 Node를 지우는 작업은 $O(1)$에 수행할 수 있을 것이라 생각했다. Approach >연결 리스트를 순회하며 각각의 node를 배열에 저장한다. >이제 뒤에서부터 n번째 nod...

Intuition 더하기를 진행할 때 일의 자리부터 진행하게 되는데, 문제에서도 역순으로 된 linked list를 input으로 주고 있기 때문에 주어진 linked list를 순서대로 순회하며 더하면 될 것이라 생각했다. 이때, carry와 남는 자리수들에 대해서 신경쓰면서 풀이했다. Approach >결과값을 담을 Node를 매번 새로 생성해야 하기...

Intuition 자릿수를 중요하게 생각해야 한다. 더 큰 자릿수에 있는 수는 더 큰 영향력을 갖는다. 따라서 rough하게 생각했을 때 자릿수가 클 수록 작은 수를 가져야한다고 예상해볼 수 있다. 조금 더 구체화하면 숫자 $abcd\cdots$가 $a\leq b\le

Intuition 일단, gas[i]보다 cost[i]가 크다면 시작자체가 불가능하므로 그 지점은 답이 될 수 없다. 마찬가지로 $i^{th}$ station에서 $(i+1)^{th}$ station으로 이동할때에도 gas[i]만큼 채우고 cost[i]만큼 소모하므로,

엘리스 스쿨 코딩 테스트에서 골드바흐의 추측 문제를 접했고 해당 문제를 그대로 사용할 수는 없어, 백준의 비슷한 문제(6588. 골드바흐의 추측)를 풀이하는 포스팅을 하게 되었다. Intuition 문제를 처음봤을 때 두 가지 옵션 중에서 무엇이 나을까 고민을 하게

Intuition 반복을 피하기 위해서는 이전에 해당 문자가 나왔는지를 알아야한다. 마침, 등장할 수 있는 문자는 ASCII Table에 있는 128개가 전부이니 등장여부를 체크하는 배열을 만들 수 있다. 문자열을 돌다가 중복된 문자라면, 해당 문자가 나왔던 위치의 다

Introduction 문제해결을 듣다가 거듭제곱을 빠르게 계산하는 방법에 대해 교수님이 짧게 언급을 하셔서 따로 더 찾아서 공부를 해보았다. $a^n$을 계산하는 가장 쉬운 방법은 $a$를 $n$번 곱하는 $O(n)$이 걸리는 방식이다. 그러나 지금부터 설명할 방법

Intuition A부터 Z까지가 하나의 사이클이고 그 다음은 AA, AB $\cdots$ 이므로 26진법으로 처리하면 되겠다고 생각했다. Approach > 어떤 문자 n이 들어오면 시작점인 'A'만큼 빼주고 +1을 해주면 우리가 원하는 대로 값이 변환된다. 문자도

로마 숫자 종류가 7개로 한정되어 있고,기본 규칙은 무조건 큰 숫자에서 작은 숫자의 흐름인데, 그것에 반할 때에만 특수하게 처리하므로숫자 7개를 따로 dictionary처럼 사용하면서 문제를 풀면 되겠다고 생각했다.우선 숫자 7개를 dictionary처럼 쓸 수 있도록

Intuition 배열의 길이가 50000개로 제한되어있기 때문에 지금까지 배열에 등장한 숫자를 저장해서 그게 몇 개 나왔는지 체크하는 것이 가능할 것이라고 생각했다. Approach > 어떤 숫자가 몇개 나왔는지 저장하기 위해서 구조체를 만들었다. num은 배열의 첫

subarray 형태를 찾아야하니 누적합을 활용하면 좋을 것 같다는 생각이 들었다.누적합 배열을 만들면 $an$부터 $a{n+k}$까지의 합은 $pre{n+k}-pre{n-1}$으로 $O(1)$에 구할 수 있다.예를 들어, 아래와 같은 배열이 있을 때$$5,9,-1,-

숫자 개수만큼 배열을 만들어 놓고 해당 숫자가 등장할때마다 배열을 +1하면 어떤 것이 1개 나왔는지 알 수 있을 것이라고 생각했다.문제가 constant extra space로 제한을 두고 있으므로 숫자의 범위가 중요해졌다.다행히 숫자가 $-3 104 \\leq nu

순서를 유지하면서 0만 뒤로 보내면 되는 것이니, 앞에서 부터 순차적으로 읽으면서 0이 아닌 숫자를 앞으로 가져오면 되겠다고 생각했다.앞에서부터 읽어가면서 0이 아닌 숫자를 0과 바꾸면서 순서는 유지시키기 위해,이동할 위치(0을 가리키는)의 인덱스와 0이 아닌 숫자의

에라토스테네스의 체의 시간복잡도 증명과정에서 소수의 역수들의 합에 대해 공부하는 과정에서 비슷하지만 다른 형태인 자연수들의 제곱의 역수의 합 문제를 발견하게 되었는데, $\\sin x$ 식의 변형이 흥미로워서 포스팅해보게 되었다.문제는 매우 간단하다.다음 급수의 값을

테일러 급수의 예시에 대해 공부하다가 고등수준에서의 증명이 궁금해서 포스팅하게 되었다. 그림 출처 : Gribozavr, Public domain, via Wikimedia Commons 부채꼴 $ABC$와 $\overline{AC}$의 연장선과 점$B$에서 수

에라토스테네스의 체의 시간복잡도를 증명하기 위해 공부하다보니 테일러 급수에 대한 개념이 필요해서 포스팅을 하게 되었다. 테일러 급수와 테일러 정리란? 가령, 우리가 $\int_{0}^{1}\sin(x^2)dx$을 계산해야 한다고 가정해보자. 아마 쉽지 않을 것이다. 그러나, 다항함수의 급수로 이를 근사한 값은 구할 수 있다. $\int{0}^{1}\sin(...

문제를 보자마자 에라토스테네스의 체가 떠올랐다.숫자 하나의 소수 여부를 판별하은 제곱근까지 나누어서 나누어 떨어지지 않는다면 소수라고 판단할 수 있다. 그러나 여러개의 소수를 대량으로 판별하는 데에는 에라토스테네스의 체가 훨씬 효과적이다.에라토스테네스의 체는 배수를 지

Intuition 팩토리얼의 계산결과 마지막에 붙는 0인 trailing zero가 몇개인지 세면된다. 기본적으로 0이 붙으면서 자릿수가 생기려면 10이 곱해져야한다. Approach && Solution 따라서 우리는 5의 배수에 집중하면 된다. 왜냐하면 2는 5보다

문제는 간단했다.n을 1과 2로 이루어진 합으로 계산할 때 과연 몇가지 경우의수가 가능한가를 구하면 된다.처음에는 규칙을 찾아보니 $nC_0+{n-1}C1+{n-2}C_2+...$ 이런식의 규칙을 발견해서 이를 토대로조합 함수를 만들고 다 더해보려했다.그러나 이 코드는