문제 링크 1. 아이디어 n개의 섬 사이에 다리를 건설하는 비용 costs가 주어질 때, 최소 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하는 문제다. 최소 스패닝 트리의 대표적인 문제로 costs를 비용에 대해 오름차순 정렬한 후 크루스칼 알고리즘으로 간선을 선택하는 방식으로 해결했다. 2. 복잡도...

문제 링크 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...