Coding Diary

문제 및 코드 1. 생각 맨 처음에 오름차순 정렬 후 적은 사람들끼리 태우자! 이렇게 생각했는데 틀림... 2. 회고 한 구명보트에 2명만 탈 수 있다는 제한을 보지 못하고 문제를 끙끙거리며 풀어나갔다. 탐욕 분류니까 정렬해서 몸무게 적은 사람들부터 태우면 되겠군... 이러면서 풀었는데 테케는 통과해도 정답처리가 안 됨. 그래서 도저히 왜 그런지 몰라서 자세히보니 2명만 탈 수 있다는 제한이 있었음. 앞으로는 제한 사항을 잘 보자. 그리고 구명보트 수를 최소한으로 하기 위해 몸무게를 오름차순으로 정렬하고 제일 몸무게 적은 사람과 많은 사람을 함께 태워버리자는 탐욕법은 그래도 이해가 되었음... ---- 오름차순 정렬한 다음 몸무게 적은 사람들끼리 먼저 태우면 되지 않을까? 하면서 풀었는데 테케는 통과돼도..

문제 및 코드 회고 그리디로 어떻게 접근해야 하는지 판단이 잘 서지 않았음 그러다 다른 풀이를 참고해서 그리디를 적용해서 맨 앞에서부터 제일 큰 수를 찾아나가면 되겠다는 생각을 하게 되었음. 근데 그러면 제일 큰 수를 어떤 범위에서 찾아야 하지에 대한 생각을 하게 됨. 이때 총 만들어야 하는 숫자의 길이를 참고해서 해당 숫자의 길이의 맨 앞 숫자부터 구해나간다는 생각으로, 특정 시작점부터 만들어야 되는 숫자의 남은 길이를 남겨둔 곳까지 범위 중 최댓값을 찾아나감. 그 끝이 k+i이라고 할 수 있음. 다른 풀이 보고 그래도 이해는 되었는데 시간이 엄청 오래 걸렸다... 기억 number.charAt(j) - '0' 이렇게 숫자형태의 문자에서 '0'을 빼주면 int 형의 값을 얻을 수 있다. 체크 풀이 횟수..

1. 개념 현재 상태에서 문제를 해결할 수 있는 가장 좋은 해를 선택해나가면 최적의 답을 구할 수 있게 되는 알고리즘 2. 과정 1) 해 선택 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다 2) 적절성 검사 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다 3) 해 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다. 3. 특징 시간 복잡도는 O(n)이다. n개를 쭉 살펴보면서 하나를 해라고 선택한 후, 적절성 검사를 하고, 적절하면 해라고 인식, 적절하지 않으면 해라고 인식하지 않는 과정을 n개 동안 진행한다. 앞의 선택(해를 선택하는)이 뒤의 선택에 영향을 미치지 않을 때 사용 가능하다. 문..