Lindeblad.

난이도: Normal총평: O(n) 풀이를 생각해내기 힘들다. 풀이는 https://leetcode.com/problems/gas-station/editorial 을 보았다.문제 설명n개의 가스 스테이션이 원형의 경로를 따라 배치되어 있다. i번째 가스 스테이션에는 gas[i] 만큼의 가스가 있다.당신은 무제한의 가스가 들어가는 탱크가 탑재된 차로 원형의 경로를 따라 여행을 하려고 한다. 이 때, i번째 가스 스테이션에서 (i+1)번째 가스 스테이션으로 이동하는데 cost[i] 만큼의 가스가 필요하다. 빈 가스 탱크를 가지고 경로에 있는 가스 스테이션 중에 하나에서 출발할 수 있다.gas와 cost로 이루어진 두 배열이 주어졌을 때, 어떤 가스 스테이션에서 출발해야 시계방향으로 한 바퀴 돌 수 있을까? ..

Candy총평: O(n)짜리 풀이가 생각하기 힘들다. 특정 유형을 적용해서 푸는 문제라기보다는 직접 관찰하고 알고리즘을 설계하는 게 중요한 편에 속한다.난이도: Hard문제 설명There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.You are giving candies to these children subjected to the following requirements:Each child must have at least one candy.Children with a higher rating get more candies than their neighb..

문제 설명다음과 같이 막대가 일정 간격으로 배치되어 있다. 이 중 가장 많은 물을 담을 수 있는 컨테이너를 두 개의 막대를 이용해서 만드려고 한다. 이 때 들어가는 최대 물의 양은 얼마인가?풀이가장 기본적인 접근은 모든 막대 쌍을 brute-force로 완전 탐색하는 방법으로, \(O(n^2)\)만큼의 시간이 걸린다. 이것을 더 빠르게 작동하도록 계산할 수 있을까? 이 문제는 탐욕법을 통해서 O(n) 안에 푸는 알고리즘으로 해결 가능하다. (아직까지 탐욕법으로 접근해야 하는 이유에 대해서는 명확히 찾지 못하였다) 알고리즘은 다음과 같다:1. 두 막대로 첫 번째 막대와 마지막 막대를 이용했을 때로 문제를 처음 시작한다.2. 두 막대 중 짧은 쪽을 선택한다.3. 선택한 막대 안쪽으로 한 칸씩 순회하며 그 막..