점프게임 1과 조건은 같지만, last index까진 무조건 도착한다는 전제이다. 이때 0부터 시작해서 가장 적은 횟수로 last index까지 가려면 몇회가 소모되느냐이다 Greed를 쓸껀데 여기에서 착각하지 말아야 하는 점은 범위단위로 움직인다는 것이다. count, now, max라는 세가지 변수를 두었다 순서대로 배열을 하나씩 돌면서 이를 업데이트 해줄 것이다. max를 local마다 업데이트 할 것이고, 이는 각 지점에서 최대로 갈 수 있는 지점까지의 값이다 모든 배열에서 로직이 돌면 global max를 찾을 수 있다. index=0에서 시작하니 count가 하나 올라가고 max가 변경된다. 이때 주의점은 범위단위라는 것인데, now와 실제 minmum이 별개로 움직인다는 뜻이다. 예컨데 문제..

각 element의 값은 해당 index로부터 element의 값만큼 떨어진 index로 점프할 수 있음을 나타낸다 이때 마지막 index로 갈 수 있는지의 여부를 묻는 문제이다. 이렇게 단순히 배열을 순회하는 케이스에서는 greedy로 풀어내면 수월하다. target을 배열의 마지막 index로 설정한다. target을 배열의 맨뒤부터 설정하고, 각 원소로부터 target까지 갈 수 있는지 여부를 판단한다 한곳에서라도 방법이 있다면 해당 위치로 타겟을 바꾸어 검사한다 예컨데 [3,2,1,0,4] 은 false인데, 0,1,2,3 위치에서 어떻게 하더라도 index=4로 갈 수 없기 때문이다. 만약 [3,3,1,0,4] 라면 true일 것이다. index=1의 위치에서 index=4로 갈 수 있기 때문이..

2차원 배열로 이루어져있는 데이터의 각 원소는 [height, number]로 구성되어 있다. 이때 number는 특정 원소보다 앞에 있는 원소의 height가 같거나 높은 원소의 갯수를 말한다. 예를들어 [ [1,0], [2,0], [1,2] ] 이라는 배열이 있다면, 세번째 원소는 height가 1이고, 그 앞에(in front) 1보다 크거나 같은 원소가 두개 있으므로 number가 2가 된다. order가 무작위로 들어오는 이 이차원 배열을 순서대로 reconstruct하라는 것이 문제이다. 그저 데이터를 queue로 관리하기만 하면 되는 간단한 문제다. 일단 height에 대해 내림차순으로 정렬한 후, 같은 숫자에 대해서는 number에 대해 내림차순으로 정렬한다. 이 문제가 greedy인 이유..

특정 string이 input으로 들어왔을 때, 최대한 하나의 part로 보이게끔 string을 나누면 몇개가 되느냐를 묻는 문제이다. 다시말해, 각 part에 포함된 각각의 string이 겹치지 않도록 part를 나누는 방법을 구하라는 뜻. 이때 리턴값은 각 part의 갯수로 구성된 배열이 된다. 이렇게 part에 대한 maximum을 찾는 문제는 greedy algorithm의 활용으로 귀결된다. greedy algorithm은 원소들을 순회하되, 각 순회 시점에서 global solution만을 고려하며 매 순회마다 비교하는 방식이다 따라서 한번의 순회로 도출된 global solution이 모든 경우에 대한 global solution인 경우에 적용될 수 있다. 위와 같은 문제도 이러한 유형에 해..