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

📑 문제🌱 아이디어숫자 정렬이 아닌 사전순(문자열) 정렬을 사용하자 "큰 수"의 기준이 아닌 사전순 정렬을 사용한다. 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 배열의 방문처리에는 한 가지 단점이 있다.- 먼저 도착한 노드가 최적값인지, 아닌지를 판단하지 못하고 무조건 먼저 도착한 노드만 통과시킨다. 하나..

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

📑 문제🌱 아이디어버블소트의 특징을 활용하자! 위 문제는 C++ 버블 소트 코드를 제공한다. 전형적인 버블 소트 알고리즘이며 O(N^2)의 시간복잡도를 가진다입력으로 1  즉 , 위 문제는 버블 소트를 구현하는 문제가 아닌 버블 소트의 특징을 이용하는 문제이다.  결국 정렬하는 문제이다 버블 소트의 정렬 특징을 생각해 보자 오른쪽 -> 왼쪽으로 숫자가 이동할 때, 한 턴에 연속적으로 다수의 칸을 이동한다.왼쪽 으로 숫자가 이동할 때, 한 턴에 단 한 번만 이동한다. 위 특징을 봤을 때, 결국 버블 소트의 실행 횟수는 왼쪽  그렇다면 어떻게 구현할까? 해당 숫자와  입력된 위치(인덱스)를 저장하고, 한 번에 정렬 후 현재 숫자 위치(인덱스) - 원래 위치(인덱스)의 차를 구한다그중 가장 큰 차가 바로 ..