문제해결 자체 재수강

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Intuition 이미 정렬되어 있는 배열을 합쳐서 다시 정렬시킨다는 상황자체가 Merge Sort의 후반부 과정과 유사한 상황이다. 그러나 코드를 조금 더 직관적으로 작성하기 위해 두 개씩 배열을 비교하는 병합 정렬과 달리, 한번에 모든 배열을 비교하는 방식을 채택하

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

Detecting the First Element in the Loop Description 위 그림과 같이 Single Linked List에서 한 개 이하의 loop가 존재한다고 가정했을 때, 그 loop가 시작하는 위치를 찾는 문제이다. 단, loop의 마지막은 마지막 index이다. Naïve Approach 연결 리스트 일순 과정에서 각각의 no...

Intuition 값이 올라가기 시작하는 지점부터 내려오는 지점까지의 길이의 최댓값을 구하는 문제이다. Literally 산을 찾으면 된다. 그러기 위해선 올라가는 부분과 내려가는 부분, 그리고 하산이 끝나는 지점을 특정시켜줄 수 있어야 한다. Approach 올라가

Intuition 이 문제를 한 줄로 요약하면 (길이)*(최솟값)을 최대로 만드는 것이다. 길이를 확정시킨다음 최솟값을 결정할 수도 있고, 최솟값을 결정한 다음 길이를 최대화시킬 수도 있다. 나는 전자의 경우 $O(N)$, 후자의 경우 그보다는 효율적일 것이라고 판단해서 후자의 방식을 택했다. 물론 막상 코드를 짜고나니 후자도 $O(N)$이 소요됐다. A...

Intuition left, mid, right의 범위를 지정해주는 것이 우선적으로 필요하다. 한번에 지정하기는 힘들기 때문에, left를 먼저 지정하고 나머지 mid와 right를 지정하는 느낌으로 생각했다. Approach >본격적으로 시작하기에 앞서, 그때그때 각 범위에 따른 합을 구해줘야하는 경우가 있으므로, 이 합을 $O(1)$에 구하기 위해 누...