Keep the Experience Natural, Easy, Light

#1 알고리즘#1-1 직관적인 풀이와 그 한계#3-1에 있는 50점 짜리 코드는 누구나 생각할만한 직관적인 풀이다. 문제는, L이 큰 경우다. L이 큰 경우는 나머지 연산을 연산 중간 중간에 끼워서 수가 너무 커지지 않게 조절해야 한다. 하지만, 예를 들어 L이 30이라면 3130라는 엄청나게 큰 수를 계산해야하는데 이건 말이 안 된다. 따라서 이 문제는 #3-1에 있는 직관적인 풀이가 아닌 새로운 방식으로 풀어야 한다는 분위기를 풍긴다. 다행히, 문제의 힌트에서 무언가가 보인다. #1-2 힌트abcde의 해시 값은 1 × 310 + 2 × 311 + 3 × 312 + 4 × 313 + 5 × 314 = 1 + 62 + 2883 + 119164 + 4617605 = 4739715이다.반복되는 숫자가 눈에..

#1 알고리즘#1-1 그리디 알고리즘을 적용할 수 있는가? 그리디 알고리즘 (Greedy Algorithm)#1 알고리즘#1-1 개요while(정답 도출) { 현 시점 가장 좋아 보이는 선택}눈 앞의 이익만 추구(= Greedy(탐욕스러운, 욕심 많은))하는 방식의 접근법을 말한다. 위 코드의 형식을 갖추기만 하면 그리디kenel.tistory.com위와 같은 그리디 알고리즘을 구현하면 일단 (정답인지 아닌진 몰라도) 일단 풀리긴할 것 같이 생긴 문제다. 하지만, 그리디 알고리즘을 적용할 수 있는 지에 대한 확신이 들지 않는다. 이 문제가 그리디 알고리즘임을 증명할 수 있다면, 마음 편히 그리디 알고리즘을 적용해 풀 수 있을테다. 따라서, 이 문제에서 최선의 선택이 곧 최적해가 되는 지의 여부를 증명해보..

#1 알고리즘#1-1 그리디 알고리즘 그리디 알고리즘 (Greedy Algorithm)#1 알고리즘#1-1 개요while(정답 도출) { 현 시점 가장 좋아 보이는 선택}눈 앞의 이익만 추구(= Greedy(탐욕스러운, 욕심 많은))하는 방식의 접근법을 말한다. 어떤 구체성을 띄지 않는, 굉장히 추상적kenel.tistory.com #1-2 최적해가장 많은 회의 갯수가 최적해다. 딱 봐도 정렬을 요구하는 문제다. 회의를 시작 시각 기준으로 정렬하면 문제가 동적 프로그래밍 문제가 된다. 반면, 종료 시각을 기준으로 정렬하면 문제가 그리디 알고리즘 문제가 된다. 전자의 접근이 틀렸다고는 볼 수 없지만 시간 초과로 인해 문제 풀이가 불가능하다. 따라서 종료 시각을 기준으로 정렬해야 한다. 또, 일반적으로 그리..

#1 알고리즘#1-1 문제의 목적 찾기과일이 전부 꽂혀있는 탕후루의 앞쪽 또는 뒤쪽에서, 과일을 하나씩 빼는 문제라고 생각하면 도저히 문제 해결의 실마리가 안 보인다. 너무 복잡하기 때문이다. 하지만, 이 문제를 아래와 같이 2개의 Index를 사용하는 순회 문제라고 생각하면 문제의 해결 방식이 명료해진다. 아래의 예시를 보자. #1-2 순회 시작Input으로부터 도출한 Array에서 startIndex ~ endIndex에 해당하는 부분을 탕후루라고 생각한다. startIndex 및 endIndex는 각각 0부터 시작한다. 그리고 endIndex를 뒤로 한칸 씩 밀어가며 전체 배열을 순회한다. #1-3 endIndex++endIndex를 뒤로 밀어나가다가 과일의 종류가 3개 이상이 되면, endInde..

#1 알고리즘#1-1 개요먼저, Input으로부터 '듣지 못한 사람'들을 읽어 들여 명단을 만든다. 그리고 '보지 못한 사람'들을 한 명씩 읽어 들이며, '듣지 못한 사람'의 명단에 존재하는지 확인한다. 존재한다면, 해당 이름을 '듣지도 보지도 못한 사람' 명단에 추가한다. 마지막으로, '듣지도 보지도 못한 사람' 명단을 (사전 순으로) 정렬한다. #1-2 배열 대신 HashSet 사용 Hash table - WikipediaFrom Wikipedia, the free encyclopedia Associative array for storing key-value pairs Hash tableTypeUnordered associative arrayInvented1953Operation Average Wor..

#1 알고리즘배열을 실제로 뒤집거나, 원소를 삭제하는 연산은 높은 처리 시간을 요구한다. 따라서 배열을 실제로 뒤집는 대신 reversed = !reversed 연산으로 대체한다. 그리고 원소를 삭제하는 대신 reversed == false라면 startIndex++, reversed == true라면 endIndex--를 수행한다. #2 코드 - 코틀린lateinit var p: Arrayvar n: Int = -1lateinit var array: Arrayfun main() { val t = readln().toInt() for (i: Int in 0.. { val inputted = readln() val submit: Array = Array(inputted.length) ..

#1 알고리즘색종이를 정직하게 가로 절반 세로 절반씩 자르기 때문에 어렵지 않은 문제다. 이 정직한 조건이 없었더라면 훨씬 까다로웠을 것이다. 아래의 재귀 함수를 이용해 문제를 풀었다. 1. 색종이가 단색인 지 확인하고, 맞다면 해당 색의 갯수를 +1 하고 함수를 종료한다.2-1. 현재 색종이를 가로 절반 세로 절반 자른 좌측 상단(↖) 색종이 범위에 대해 재귀 호출을 수행한다.2-2. 현재 색종이를 가로 절반 세로 절반 자른 좌측 하단(↙) 색종이 범위에 대해 재귀 호출을 수행한다.2-3. 현재 색종이를 가로 절반 세로 절반 자른 우측 상단(↗) 색종이 범위에 대해 재귀 호출을 수행한다.2-4. 현재 색종이를 가로 절반 세로 절반 자른 우측 하단(↘) 색종이 범위에 대해 재귀 호출을 수행한다. #2 코..

#1 알고리즘재귀 함수를 이용해 푼다. 그 함수의 시작점은 도연이의 좌표다. 함수의 내용은 아래와 같다. 1. 매개변수로 받은 좌표가 캠퍼스 영역을 벗어났거나, 값이 'X'면 함수를 종료한다.2. 해당 좌표에 새내기가 있다면 '새내기 카운트'를 +1한다.3. 이제 해당 좌표는 더 볼 일 없으므로 좌푯값에 'X'를 대입한다.4-1. 현재 좌표에서 한 칸 동쪽 좌표를 인수로 가지는 재귀 호출을 수행한다. 4-2. 현재 좌표에서 한 칸 서쪽 좌표를 인수로 가지는 재귀 호출을 수행한다.4-3. 현재 좌표에서 한 칸 남쪽 좌표를 인수로 가지는 재귀 호출을 수행한다.4-4. 현재 좌표에서 한 칸 북쪽 좌표를 인수로 가지는 재귀 호출을 수행한다. #2 코드 - 코틀린var n: Int = -1var m: Int = ..

#1 알고리즘N = 2 이상인 큰 문제를, N = 1이 될 때까지 작은 문제로 쪼개어 푼다. 그러려면 f(큰 문제) = 작은 문제인 f(x)를 알아야 한다. 규칙을 수식으로 표현해내어야 한다. '바둑판'의 영역을 4개로 나누어보자. 그리고 각 영역의 맨 ↖에 있는, 영역의 첫 원소들을 비교한다. 영역 m ~ 영역 (m + 1) 간 첫 원소의 값 차이는 N = 1일 때 1, N = 2일 때 4, N = 3일 때 16, N = 4일 때 64 ... 다. 이를 일반화하면 영역 간 첫 원소의 값 차이(interAreaFirstElementDifference)는 2(N-1)*2이다. 즉 어떤 영역 m에 있어, 칸마다 써진 수는 (영역 0의 수) + m * 2(N-1)*2다. 보라색 글씨 부분을 축적된(accumu..

#1 코드 - 코틀린import java.lang.StringBuilderfun main() {    // Initiation    val n = readln().toInt()    val cardNumberInputs = readln().split(" ")    val cardNumbers = Array(n) {0}    for(i: Int in 0..()    for(cardNumber in cardNumbers) {        if(cardCountMap[cardNumber] == null) {            cardCountMap[cardNumber] = 1        } else {            cardCountMap[cardNumber] = cardCountMap[cardNum..