Keep the Experience Natural, Easy, Light

#1 알고리즘순회 문제다. bfs 문제일 것이다. '인접한 토마토'들을 모두 순회하고나서 '인접한 토마토에 인접한 토마토들'로 나아가는 형태여야 할 테니. #2 여담이게 한국정보올림피아드 고등부 문제였다니... 정말 대단한 사람들이다. 나는 수학적 계산 능력이 뛰어난 편은 아니며, 그 능력은 내 가치가 직접적으로 지향하는 바도 아니다. 하지만 이 문제가 골드5 난이도인 것을 명심해야 한다. 즉 이 정도는 난이도는 일상적으로 풀어낼 수 있어야 한다는 말이다. 열심히, 꾸준히 하자. #3 코드 - 코틀린lateinit var tomatoes: Array>var M = -2var N = -2fun main() { val mAndN = readln().split(" ") M = mAndN[0].toI..

#1 알고리즘#1-1 '연결 요소의 개수'의 의미어떤 그래프에 탐색 알고리즘을 최소 n번 적용해야 모든 정점을 방문할 수 있다고 치자. 그 때 n의 값이 바로 '연결 요소의 개수'다. 즉, 본 문제는 미방문한 아무 정점을 골라서 탐색 알고리즘을 수행하는 걸 반복하고 그 반복 횟수를 출력하면 되는 문제다. #1-2 사용한 탐색 알고리즘 그래프 - 깊이 우선 탐색 (DFS, Depth-First Search)#1 그래프의 탐색 깊이 우선 탐색 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 깊이 우선 탐색 깊이 우선 탐색의 애니메이션 예시 깊이 우선 탐색( - 優先探索, 영어: depth-fkenel.tistory.com깊이 우선 탐색을 사용했다. 방문한 정점을 담는 Set을 외부에서 주..

#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 캐싱 객체의 구조와 재귀 호출 가지치기말..