📑 문제 🌱 아이디어DP 문제처럼 생긴 그리디 문제.... 결국 알고리즘 분류 보고 풀었다.. 이 문제에서 생각해야 하는 부분은 2가지 정도 있다. 1. A메뉴, B메뉴를 어떤 기준으로 선택할 것 인지?2. 5000원 메뉴인 A메뉴를 돈이 부족해 선택을 하지 못할 때. [1번 경우]다른 그리디 문제는 정렬 시 데이터에서 하나의 기준을 잡아 정렬하는 경우가 많다.위 문제는 정렬의 기준을 (A메뉴 - B메뉴)의 차이를 기준으로 내림차순으로 정렬한다 ex) 1000 999 보다 10 1 이 우선순위가 되어야 한다. [2번 경우]1번 경우에서 5천 원 메뉴를 선택하다 보면 나머지 날은 밥을 먹지 못하는 경우가 생길 수도 있다.위 경우를 방지하기 위해 M - 5000 >= 남은 요소 * 1000으로 위 상황을..

📑 문제🌱 아이디어Xφ(X) = N , X의 범위는 N의 약수이다. 풀기 전 가장 크게 고민했던 점은 한 가지이다. X를 어떻게 찾아야 하는가이다.당연하게도 X는 N이하 일 것이다. 하지만 N이 1,000,000,000 경우 탐색범위가 커서, 시간초과가 날것이다 첫 번째 시도는 정수 'X'를 이분탐색으로 찾는 것이다. 물론 X마다 오일러의 피 수가 규칙적이지 않아서, 실패했다. 두 번째는 시도는 A * B = N이라면 -> 결국 A, B는 N의 약수이다. 라는 아이디어로 시작했다.당연하게도 두 수를 곱해서 N 이 되려면 두 수는 N의 약수일 것이다.  약수를 구할 때 제곱근까지만 탐색하여. O(logn)만큼 최적화하고X의 탐색범위를 N의 약수로 획기적으로 줄이고 오일러의 피함수 알고리즘으로 계산하여조..

📑 문제🌱 아이디어숫자 정렬이 아닌 사전순(문자열) 정렬을 사용하자 "큰 수"의 기준이 아닌 사전순 정렬을 사용한다. 9, 30 두 숫자가 있다. 두 수를 조합하여 만들 수 있는 가장 큰 수는930이다. 즉 문자열 정렬을 통해 가장 뒤서는 순(30, 9)부터 숫자를 합치며 풀면 된다. 하지만 하나의 반례가 있다. 3,30 두 숫자가 있다. 두 수를 조합하여 만들 수 있는 가장 큰 수는 330이다.하지만 문자열 정렬 시 가장 뒤서는 번호가 30이 된다 (3,30) 위처럼 출력 시 303이라는 숫자가 만들어진다. 이미 정렬된 문자열에서 앞의 숫자 '3', '3'0 같을 경우 330, 303이 큰지 판단하고, 결괏값에 따라 문자열을 서로 변경해 주는 형식으로 풀면 된다. 입력 값으로 1,000,000,00..

📑 문제  🌱 아이디어BFS 응용문제, 다른 문제들과 비슷하게 상, 하, 좌, 우를 이동할 수 있지만 좌, 우는 이동 횟수가 제한된다.그렇다면 총 이동할 수 있는 칸은 몇 칸인가? 를 물어보는 문제이다. 먼저 현재 좌표, 좌, 우 남은 이동 횟수를 담는 객체를 만들고 방문처리 및 0-1 BFS를 돌리면 된다고 생각했다.하지만 91%쯤 실패한다... 예상컨대 큰 틀에서 구현자체는 틀리지 않았지만, 히든케이스를 만족시키지 못할 만큼디테일하게 구현하지 못했던 것 같다 BFS 응용문제에선 대부분 방문처리에서 히든테스트케이스가 나온다. 기본적인 2차원 boolean 배열의 방문처리에는 한 가지 단점이 있다.- 먼저 도착한 노드가 최적값인지, 아닌지를 판단하지 못하고 무조건 먼저 도착한 노드만 통과시킨다. 하나..

🌱 옵셔널(Optional)이란? + 왜 사용해야 하는지? 자바 8에 추가된 기능이며, 결괏값이 없음(null)을 더 안전하고 명확히 전달하기 위해 등장했다.자바 8 이전까진 null로 표현했지만 알다시피 null은 시스템에 오류를 발생시킬 가능성이 매우 높다즉 시스템을 NPE(NullPointerException)로부터 안전하게 보호하기 위한 기능을 제공하는 래퍼(Wrapper) 클래스이다. Null safety를 고려하는 개발을 통해 에러를 방지하고 시스템의 안정성을 보장하기 위해 옵셔널을 사용한다.  🚨  사용 시 주의사항그렇다면 모든 변수, 반환값에 옵셔널로 래핑 해서 관리하면 되는 것 아닌가? 앞서 이야기했던 것처럼 옵셔널은 래퍼(Wrapper) 클래스이다. 반환값 등을 감싸고 (Wrappi..

📑 문제🌱 아이디어스위핑 유형의 문제, 일단 무엇을 기준으로 정렬할지 생각해 보자 위 문제에 핵심은 좌표의 범위 L이 주어질 때  end - start 이 만족해야 한다, 즉 구간마다 L범위에 해당하는선분의 개수를 세야 한다. 좌표 구간마다 선분이 해당하는지 판단하고, 범위체크까지 한다면 자칫 O(N^2) 시간복잡도를 가지게 구현할 수 있다.하지만 N의 범위가 100,000까지 이며 O(N) 이하로 구현해야 한다. 먼저 데이터를 정렬하는 과정이 필요하다. y축을 기준으로 정렬하고 한쪽 방향으로 쭉 스캔하면서 계산을 하면 된다즉 한쪽 -> 반대쪽으로 쭉 스캔을 하는 스위핑 방식으로 구현하면 O(N)의 시간복잡도로 빠르게 구현 가능하다.   정렬 후 가장 아래 (10, 20)부터 last에 x를 넣고 계..