Keep the Experience Natural, Easy, Light

#1 알고리즘인덱스가 0 ~ 1000000 (문제에서 주어진 최댓값)인 Boolean형 배열 isPrimes을 선언한다. 이 배열은 이 배열의 어떤 index가 소수인지 아닌지를 true or false로 저장하기 위한 배열이다. 우선 isPrimes의 모든 index의 값을 true로 초기화한다. isPrimes[0]은 사용하지 않으며, isPrimes[1]에는 false를 대입한다. 이제 isPrimes[2]부터 시작해 오름차순으로 배열을 순회한다. isPrimes[x]이 true면 해당 x을 저장한다. 그리고 isPrimes[x * 2], isPrimes[x * 3], isPrimes[x * 4], ...에는 false를 대입한다. x++을 하고 다시, isPrimes[x]이 true면 해당 x을 ..

#1 알고리즘#1-1 문제의 핵심이 문제의 핵심은, x!가 가지고 있는 2*5 쌍의 갯수만큼 뒤에 0이 붙는다는 규칙의 파악이다. #1-2 상향식 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 #1-1 정의 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com상향식 동적 프로그래밍을 구현해 풀었다.  #2 코드 - 코틀린val twoCounts = Array(501) {0}val fiveCounts = Array(501) {0}// 2*5 ..

#1 알고리즘 힙 정렬 (Heap Sort)#1 알고리즘 #1-1 힙(heap)이라는 영어 단어의 사전적 의미는 쌓아 놓은 무더기다. 그리고 이 단어는 프로그래밍에서도 사용된다. 첫째로 메모리 영역에서, 둘째로 자료구조에서다. 이 둘은 서로 다kenel.tistory.com힙 정렬을 사용했다. 힙 정렬 대신 병합 정렬을 사용할 수도 있다. #2 여담문제는 쉬워보이는데, 2024년 1월 8일 기준 정답률이 26퍼센트 밖에 되지 않는다. 그래서 문제를 풀기 전에 함정이 숨어있나싶었다. 그런 건 없었다. 문제의 이름이 solved.ac라서 사람들의 관심을 샀나보다. 그리곤 그 사람들이 그대로 가볍게 코드 제출을 해본 게 아닐까? 문제의 조건 자체는 쉽지만, 시간 초과가 나지 않게 하기 위한 빠른 정렬 기법 그..

#1 알고리즘1. 어떤 스택에는 '이상한' 규칙이 있다. 바로 해당 스택에 push하는 원소의 값이 순서대로 1, 2, 3, ... , n여야 한다는 규칙이다. 즉, 맨 처음 스택에 push하는 값은 반드시 1이어야 하며, 1 다음에는 2, 2 다음에는 3, ... , 62 다음에는 63을 push해야 한다.
2. 반면, pop에 대한 규칙은 없다. 스택이 비어있는 상태에서 pop을 하는게 아닌 이상, 아무렇게나 해도 된다.
3. (1)의 규칙은 (스택에 들어 있는 원소들 중 가장 나중에 push된 값 + 1)을 push하는 규칙이 아님에 유의한다. 예를 들어 1, 2, 3을 차례대로 push하고 pop을 2번 한 상황이 있다. 여기서 추가적으로 push를 하려는 경우, 그 값은 2가 아니라 4다.4. ..

#1 알고리즘#1-1 큐 [백준] 10845 - 큐#1 알고리즘 java.util.Stack과는 달리 java.util.Queue는 클래스가 아니라 인터페이스다. 나는 java.util.Queue 인터페이스를 구현한 클래스인 LinkedList를 Queue로서 사용했다. last()는 확장 함수(Extension functions)kenel.tistory.com큐(Queue)가 사용되었다는 점에서 비슷한 문제다. #1-2 목표 문서의 인덱스프린트할 목표 문서의 인덱스를 어떤 변수 A로 두고 추적할 수도 있다. 하지만 이러면 Queue가 offer되거나 poll될 때에 바뀌는 목표 문서의 위치에 맞게 A의 값을 계속 조정해주어야 한다. 이는 가독성에 나쁜 영향을 미치고, 그래서 에러의 여지를 키운다. 나는..

#1 알고리즘#1-1 17626번 문제의 함정n이 18인 경우를 예로 든다. 경우 a보다 b의 '제곱수 합의 최소 갯수'가 더 작다. 즉, 무작정 제곱수의 밑을 큰 수로 둔다고 그게 반드시 정답인 것은 아니다. #1-2 점화식x의 제곱수 합의 최소 갯수를 반환하는 함수 f(x)를 가정한다. 이러면, a와 b 각각의 42와 32를 f(x)에 넣으면 f(42) = 1이고 f(32) = 1이다. 즉, 모든 빨간 부분은 f(x)에 넣으면 1로 그 값이 같다. 여기에서 f(x) = 1 + f(y)라는 식을 도출할 수 있다. y값은 a의 경우 18 - 42, b의 경우 18 - 32, c의 경우 18 - 22다. 이를 일반화하면 f(x) = 1 + f(x - i2)다. i의 범위는 1 ~ (x의 제곱근을 넘지 않는..

#1 알고리즘#1-1 병합 정렬 (Merge Sort)#1 알고리즘 병합 정렬의 총 비교 횟수는, 최악의 경우 nlog2n이다 #2 코드 (자바) public static void mergeSort(int[] array, int startIndex, int endIndex) { // (startIndex kenel.tistory.com우선 손님 별 돈을 인출하는 시간들을 정렬해야 한다. 이 문제에서는 병합 정렬을 사용했다. #1-21번 열 + 2번 열 + 3번 열 + ... + personCount번 열로 모든 손님들의 대기 시간 총합을 구한다. #2 코드 - 코틀린fun main() { val personCount = readln().toInt() val timeStrings = re..

#1 알고리즘먼저, 모든 배추에 번호 0을 부여한다. 그리고 배추들을 순회하며 해당 배추의 번호가 0이면 1부터 시작하는 번호를 부여한다. 번호가 부여된 배추는 자신을 기준으로 동, 서, 남, 북에 있는 번호가 0인 배추에 같은 번호를 전달한다. 그리고 전달된 배추 또한 재귀적으로 동, 서, 남, 북에 같은 번호를 전달한다. 같은 번호가 부여된 배추를 하나의 '배추 그룹'으로 생각한다. 여러 개의 '배추 그룹'에 부여된 번호 중 가장 큰 것을 출력하면 그것이 곧 지렁이의 최소 마릿수다.  #2 코드 - 코틀린/* count = 갯수 * number = 번호 */lateinit var cabbageMap : HashMap, Int>fun main() { val testCaseCount = readln..

#1 코드 - 코틀린import java.util.Stackfun main() {    val testCaseCount = readln().toInt()    for(i : Int in 0.. = Stack()    for(char in testCase) {        if(char == '(') {            stack.push('(')        } else { // char == ')'            if(stack.isEmpty()) {                return false            }            stack.pop()        }    }    return stack.isEmpty()}'('을 만나면 스택에 push하고, ')'을 만나면 스택을..

#1 알고리즘#1-1 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 이름을 붙었다. 확실히 static이 붙을 만한 작업은 아니지만, 그kenel.tistory.com상향식 동적 프로그래밍을 구현해 풀었다. 이 문제에서 가장 핵심적인 부분은 점화식을 구하는 것이다. 나는 먼저 점화식 calculateCombination(sum) = calculateCombination(sum - 1) + calculateCombination(sum - 2) + calculateCombination(sum - ..