자료구조 및 알고리즘

문제풀이특정 노드 간의 최단 거리를 구하는 문제로 BFS로 풀 수 있긴 하지만, 간선의 값이 일정하지 않기 때문에 (0일 수 있기 때문) 0-1 BFS 방식으로 풀 수도 있고 다익스트라 알고리즘으로 풀 수도 있다.0-1 BFS로 풀 경우, 일반적으로 그래프 문제에서 BFS를 이용해 최단거리를 구하는 경우에는 항상 간선이 1이라는 전제가 깔린 문제가 많아 목적지값이 poll될 때, 큐를 더이상 돌리지 않아도 된다. 하지만 이 문제에서는 간선 값이 0인 경우가 존재하므로, 모든 값이 큐에 들어갔다 나와야 한다. (이 부분을 놓쳐서 여러 번 틀렸다..)이는, 현재 위치가 `X`라고 하고 `X * 2`만큼 이동할 때에는 시간(이동에 소요되는 비용)이 증가하지 않기 때문에 더 나중에 찾아진 경우에도 이미 찾아진 ..

해시를 사용하면 공간 복잡도를 많이 줄일 수 있는 간단한 문제입니다.class Solution { public int[][] solution(int[][] data, String ext, int val_ext, String sort_by) { Map fields = new HashMap(); fields.put("code", 0); fields.put("date", 1); fields.put("maximum", 2); fields.put("remain", 3); int[][] list = new int[data.length][fields.size()]; int j = 0; for (int i = 0; i ..

문제 설명매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.제한 사항scoville의 길이..

힙 정렬(Heap Sort)힙의 성질을 이용해 정렬하는 정렬 방식입니다.Cf. 힙의 성질: 힙은 항상 느슨한 정렬 상태를 유지하고, 루트 노드의 key값이 트리 내에서 가장 높거나 낮다(최대/최소힙)일반적으로 \(O(n\log{n})\)의 시간 복잡도를 가집니다. (노드 하나를 재정렬 하는데에 \(O(\log{n})\)의 시간 복잡도 소요)구현 코드처음에는 Heap을 구현해서 Array를 인자로 받아 Heap을 채워 heapify 한 뒤, 하나씩 delete해서 루트를 얻어내 값을 정렬할 생각이었습니다. 그런데 그러자니 Heap 내부의 Array를 생성하는 과정이 들기 때문에 추가로 메모리가 들게 되어 추가 메모리가 사용되지 않게 해보자는 취지로 아래와 같이 작성했습니다.먼저, Array를 받아다가 he..

힙(Heap)은 배열 또는 연결 리스트(Linked List)로 구현할 수 있다. 연결 리스트 보다는 배열로 구현하는 것이 연산시 노드를 탐색하는 과정에서 비교적 간단하여 배열로 구현했다. 연결 리스트로 구현하는 경우 인덱스가 비교적 복잡해진다.Cf. 리스트로 구현하면 `resize()` 메서드를 따로 둘 필요가 없어진다. `capacity`값도 마땅히 필요하지 않아진다.Cf. 리스트로 구현하면 인덱스는 0 이상 `this.size` 미만이며, 자식 노드는 특정 노드의 인덱스가 \(n\)이라면, \(n * 2 + 1\), \(n * 2 + 2\)가 된다.필요시 참고용도로 리스트로 힙을 구현하는 코드를 일부 작성해두신 분의 블로그 게시글 링크를 첨부한다. 전체 코드(최소힙을 구현하여 루트값이 가장 작은 형..

문제 설명네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.제한사항컴퓨터의 개수 n은 `1` 이상 `200` 이하인 자연수입니다.각 컴퓨터는 `0`부터 `n-1`인 정수로 표현합니다.`i`번 컴퓨터와 `j`번 컴퓨터가 연결되어 있으면 `com..

문제 설명n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.제한사항주어지는 숫자의 개수는 2개 이상 20개 이하입니다.각 숫자는 1 이상 50 이하인 자연수입니다.타겟 넘버는 1 이상 1000 이하인 자연수입니..

문제 설명선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다.두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다.예를 들어 A가 B에게 선물을 5번 줬고, B가 A에게 선물을 3번 줬다면 다음 달엔 A가 B에게 선물을 하나 받습니다.두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수가 더 작은 사람에게 선물을 하나 받습니다.선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값입니다.예를..

문제 ✨ 문제의 개수 N(1

문제 ✨ N개의 여러 단위 동전이 주어질 때 거스름돈 M을 거슬러 줄 동전의 최소 개수를 구해라 Cf. 첫 번째 줄에는 동전 종류 수 N(1