Keep the Experience Natural, Easy, Light

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

#1 알고리즘#1-1 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘#1-1 정의동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com상향식 동적 프로그래밍을 이용해 풀었다. #1-2 색깔 조건약간 어렵게 쓰여있는 것 같지만, "모든 지붕은 그 직전 지붕과 색이 달라야 한다"라는 말로 압축된다. 현재 순회중인 지붕의 색과는 다른 색의 지붕을 재귀 호출하는 방식으로 색깔 조건을 구현할 수 있겠다. #1-3 캐싱 객체의 구조와 재귀 호출 가지치기말..

#1 알고리즘DFS 및 BFS 알고리즘을 알고 있는지 묻는 간단한 문제다. 하지만, 약간 신경 쓸 점이 3가지 있다. 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 인접 배열을 정렬하면 된다. 나는 퀵 정렬을 이용했다.2. 정점의 개수 N(1 ≤ N ≤ 1,000) 문제에서 출제되는 정점은 1부터 시작한다. 즉, 1-based indexing을 사용하고 있다. 나는 이 문제를 풀기 위해 예전에 정리해 게시글로 남겨두었던 BFS 및 DFS 알고리즘 코드를 그대로 가져다 쓸 건데, 문제는 해당 코드들은 정점이 0부터 시작한다는 조건 하에 짜여진 코드들이다. 즉, 정점이 0-based indexing을 사용하고 있다. 이 차이를 해소하기 위해서 '인접 배열들의 리스트(lis..

#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 알고리즘#1-1 하향식 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 #1-1 정의 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com하향식 동적 프로그래밍을 구현해 풀었다. Caching을 위한 객체로 HashMap를 사용했다. 예를 들어, 1 + 2 + 3 - 4 + 5 - 6 + 7라는 수식을 Caching하기 위해 makeListToKey()라는 함수를 만들었다 (#2 참조). 수식 makeListToKey()에 넣으면 "+1..

#1 알고리즘#1-1 상향식 동적 프로그래밍 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 #1-1 정의 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com상향식 동적 프로그래밍을 구현해 풀었다.  #1-2 수열의 규칙(점화식) 찾기1, 1, 1, 2, 2, 3, 4, 5, 7, 9, ...문제에 제시된 위 수열은 p[n] + p[n+1] = p[n+3] 라는 간단한 점화식을 지니고 있다. #2 코드 - 코틀린/*수열 p가1, 1, 1, 2, 2, 3, ..

#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 문제 이해'나무를 자르는 높이(cuttingHeight)'가 무엇인지를 묻는 문제다. 그리고 cuttingHeight의 범위는 0 ~ 1,000,000,000이다. 따라서, cuttingHeight를 1씩 증가시켜서 일일히 확인하는 방법은 시간 관계상 힘들다. 다행인 것은 cuttingHeight가 증가함에 따라, 얻어지는 '목재의 량(woodQuantity)'의 감소한다는 사실이다. cuttingHeight가 감소하면 woodQuantity는 그대로거나 감소한다. cuttingHeight가 index고, woodQuantity는 value인 배열 woods가 있다고 가정하자. 그 배열의 모습은 아래와 같다. #1-2 가상의 배열 'woods'M이 285라고 가정한다. 그리고 M값을 만..

#1 알고리즘 동적 프로그래밍 (Dynamic Programming), 상향식(Bottom-up) 및 하향식(Top-down) 접근#1 알고리즘 #1-1 정의 동적 프로그래밍을 한 줄 요약하면 중복의 제거다. 정적(static)이라는 개념과 반대되는 개념으로서, 동적(dynamic)이라는 단어가 이름에 붙었다. 확실히 static이 붙을 만한 작업kenel.tistory.com하향식 동적 프로그래밍을 구현해 풀었다. 이 문제가 까다로운 이유는, 하향식 동적 프로그래밍에서 캐싱(Caching)을 할 때, 어떤 값을 캐싱해야할 지 난감하다는 것이다. 여러가지 경우들 중에서 최솟값을 골라서 캐싱해야 하는데 그 구현이 처음 문제를 봤을 땐 꽤 복잡해보였다. 나는 ArrayList에 재귀호출의 return값들을 ..