Keep the Experience Natural, Easy, Light

#1 알고리즘#1-1 탐색 문제누가봐도 탐색 문제처럼 생겼다. 그렇다면 어떤 탐색을 수행할 것인가? #1-2 탐색 목표RRRBBGGBBBBBBRRBBRRRRRRRR나는 위 테스트 케이스에서 각 알파벳 하나씩을 순회하며, 1113322333333443344444444∴ 색맹 아닌 기준으로 구역의 수는 총 4개와 같은 식으로 변경할 것이다. '인접한 같은 색'끼리는 같은 숫자를 공유하고, '인접한 다른 색'은 서로 다른 숫자를 지닌다. 이렇게 만들려면, 인접한 다른 색으로 가기 전에 먼저 인접한 같은 색에 서로 같은 숫자를 마킹하는 로직이 필요하다. #1-3 Deque 활용 Double-ended queue - WikipediaFrom Wikipedia, the free encyclopedia Abstrac..

#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 '최단 거리'의 의미이 문제에서 '최단 거리'란, '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다. 1차원에서는 간단하다. 검은색 선의 길이와 '최단 거리'가 비례하기 때문이다 (이미 방문한 지역은 다시 방문하지 않는다). 2차원이라면 문제가 복잡해진다. 선의 길이와 '최단 거리'가 비례하지 않는다. 2에서 1로 가는 빨간색 선은 '최단 거리'면서 동시에 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다. 초록색 선은 '최단 거리'는 아니지만, 빨간색 선과 마찬가지로 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다. 정리하면, 2차원에서 '최단 거리'는 반드시 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이지만, 역으로 '목표 지점(2)..

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

#1 알고리즘#1-1 '정렬' 문제결국 제일 작은 원소는 0이라는 값으로 '압축'될 것이고, 그 다음 순서로 큰 원소는 1이 된다. 즉, 이 문제는 순서 문제고 순서를 부여하기 위해선 정렬이 요구된다. 따라서 이 문제는 정렬 문제다. #1-2 병합 정렬 정렬 - 병합 정렬 (Merge Sort)#1 알고리즘#1-1 #1-2 #1-3 #1-4 #1-5병합 정렬의 총 비교 횟수는, 최악의 경우 nlog2n이다 #2 코드#2-1 자바public static void mergeSort(int[] array, int startIndex, int endIndex) { // (startIndex #2-2 코틀린fun mergeSort(arrakenel.tistory.com정렬 알고리즘으로 병합 정렬을 사용했다. #1..

#1 알고리즘 Longest increasing subsequence - WikipediaFrom Wikipedia, the free encyclopedia Computer science problem In computer science, the longest increasing subsequence problem aims to find a subsequence of a given sequence in which the subsequence's elements are sorted in an ascending order and in whichen.wikipedia.org위키백과에도 등재된 유명한 문제다. 위 링크에 문제 풀이 알고리즘을 표현한 GIF 이미지가 있다. 보자마자 문제 풀이 방향을 알게 된다. ..

#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..