문제 링크 1. 아이디어 자연수 x를 y로 변환하는 최소 연산 횟수를 구하는 문제로 bfs를 활용해도 되고 dp를 활용해도 된다. bfs의 경우 노드를 연산 결과인 숫자로 정의했을 때 x에서 출발해서 y를 발견하는 최단 거리가 최소 연산 횟수가 된다. 따라서 x인 경우 거리를 0으로 두고 x + n, x * 2, x * 3을 x에 연결된 노드...

문제 링크 1. 아이디어 i번째 일의 주식 가격이 담긴 배열 prices에서 두 날을 골라서 앞 날에 주식을 사고 뒷 날에 주식을 팔 때 최대 수익을 구하는 문제다. 첫째 날부터 마지막 날까지 순회하며 현재 날 이전까지 등장했던 최소 주식 가격을 기억하고 있으면 해당 가격에 샀다고 치고 오늘 팔았을 때 수익을 구해서 이들 중 최댓값을 구하면 해...

문제 링크 1. 아이디어 주어진 등산로에 대해 출입구에서 다른 출입구를 거치지 않으면서 산봉우리를 발견한 후 다시 출발한 곳으로 돌아오는 경우 최소 intensity를 구하는 문제로 왔던 길을 다시 갈 수 있으므로 각 출입구에서 최소 intensity로 산봉우리를 갈 수 있는 모든 경로를 찾아서 그중에서 최소 intensity이면서, inten...

문제 링크 1. 아이디어 주어진 모든 문제를 풀 수 있는 알고력과 코딩력을 쌓는 데 필요한 최단시간을 구하는 문제로 다이나믹 프로그래밍을 활용하면 효율적으로 해결할 수 있다. dp 테이블의 경우 dp[i][j]를 $i$ 의 알고력과 $j$ 의 코딩력을 쌓는 데 필요한 최단시간으로 정의하면 되며, 이때 주어진 문제 중 알고력의 상한을 alp_ma...

문제 링크 1. 아이디어 두 큐의 합을 같게 만드는 문제로 queue1의 합이 더 크면 queue1의 앞 원소를 queue2의 뒤에 삽입하고, queue2의 합이 더 크면 queue2의 앞 원소를 queue1의 뒤에 삽입하는 과정을 반복만 해주면 된다. 어느 쪽을 옮길지가 매 순간 하나로 정해지므로 탐색이 아니라 단순 반복으로 처리할 수 있다....

문제 링크 1. 아이디어 주어진 설문조사와 선택을 통해 성격 유형을 구하는 문제로 지표별로 어떤 유형이 더 우세한지를 구해주기만 하면 된다. 이를 위해 해시맵을 활용해 key에 성격 유형, value에 점수를 담은 후 각 지표별로 더 우세한 유형을 찾아서 문자열로 반환해줬다. 지표 내에서 동점 시 사전 순으로 빠른 유형을 선택해야 함에 주의해야...

문제 링크 1. 아이디어 주어진 광물들을 앞에서부터 연속으로 캐야하며 하나의 곡괭이가 5개의 광물까지 캘 수 있다는 점에서 주어진 광물들을 앞에서부터 5개씩 그룹을 묶어주는 것으로 시작했다. 그룹핑 이후에는 백트래킹 또는 그리디를 활용하면 해결할 수 있는데 먼저 백트래킹의 경우 5개씩 묶은 광물 그룹에 대해 앞에서부터 순서대로 곡괭이를 배치해...

문제 링크 1. 아이디어 지도에서 연결된 땅들의 값의 합을 오름차순으로 정렬하는 문제로 bfs 또는 dfs를 활용해서 해결할 수 있다. 주어진 지도를 순회하며 bfs, dfs로 땅을 발견하면 연결된 땅까지 전부 방문 체크하고 값의 합을 구해 저장한 후 순회가 끝났을 때, 땅이 존재하지 않으면 -1을 담은 배열을, 땅이 존재하면 오름차순으로 정렬...

문제 링크 1. 아이디어 이분 탐색을 직접 구현해보는 문제로 이분 탐색 과정에서 mid가 target이 되면 해당 인덱스를, 양 끝 포인터가 교차할 때까지 target을 찾지 못하면 -1을 반환만 해주면 된다. nums가 오름차순으로 정렬된채로 주어지기 때문에 바로 이분 탐색을 구현해줬다. 이분 탐색 과정에서 구간이 절반씩 줄어드므로 $O(\l...

문제 링크 1. 아이디어 주어진 문자열이 팰린드롬인지 판단하는 문제로 이때 알파벳이나 숫자가 아닌 문자는 제거하고 알파벳은 소문자로 치환한 후 팰린드롬이 되는지 판단하는 문제다. 해당 문제는 투 포인터를 활용하면 해결할 수 있는데 주어진 문자열의 양 끝에서부터 서로 교차하는 방향으로 포인터를 진행시키는데 알파벳이나 숫자가 아닌 문자는 건너뛰고 ...