분류 전체보기(754)
-
[CS] 크루스칼 알고리즘 시간 복잡도에 대한 이해
E를 정렬하는데 걸리는 시간 O(ElogE), 그리고 E를 loop하며 union-find를 하는 시간 O(E) = O(ElogE + E) = O(ElogE)
2023.08.20 -
[CS] DFS, BFS의 O(V+E)에 대한 이해
인접리스트를 이용해 구현시 DFS, BFS 모두 O(V+E)의 시간복잡도를 가진다. 이는 다음과 같이 이해해볼 수 있다. V가 1억개 있고 E는 0 즉 간선이 하나도 없다고 생각해보자. 그러면 탐색하기 위해서는 V를 모두 돌며 결국 하나도 연결되지 않았다는 것을 알아야 할 것이다. 그래서 이 경우에는 O(V)가 될 것이다. 이번에는 V가 1억개 있고 서로 모두 연결 되어 있다고 생각해보자. 그러면 모든 간선에 대해서 확인하는 절차(이 노드가 이미 방문했던 노드라도 바로 그걸 '확인'해야 한다)가 들어가기 때문에 간선의 개수는 O(V+E)가 된다. 그런데 여기서 E는 V * (V-1)이므로 O(V)보다 훨씬 크게 된다. 그래서 O(E)가 된다. 결국 O(V+E)가 의미하는 것은 간선이 연결되어 있는 상황에..
2023.08.20 -
[알고리즘][2] 큰 수 만들기
문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 2자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예 numberkreturn "1924"2"94" "123..
2023.08.20 -
[알고리즘][2][X] 조이스틱
문제 설명 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서) 예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다. - 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다. - 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다. - 마지막 위치에서 조이스틱을 아래로 1번 조..
2023.08.19 -
[CS] Red-Black Tree
BST의 일종 BST의 문제점을 해결하기 위해 탄생 BST의 문제점이란? BST는 부모 노드의 왼쪽 자식 노드는 부모보다 작아야 하고 오른쪽 자식 노드는 부모보다 커야 한다. 이 조건을 만족하는 BST 중 다음을 생각해보자. 부모 노드보다 작은 자식만 생기게 되는 경우. 이 경우 왼쪽으로만 쭉 길어지게 된다. 탐색에 걸리는 시간 복잡도 또한 O(n)이 되고 만다. 삭제와 삽입 또한 마찬가지다. 이러한 상황을 불균형이라고 하는데 불균형을 해결하기 위해 red-black tree가 나오게 되었다. Red-Black tree는 어떻게 해결했는가? red-black tree를 활용하게 되면 worst case에서도 탐색, 삽입, 삭제를 모두 O(logn)에 할 수 있게 된다. 그 이유는 불균형이 발생하게 되면 ..
2023.08.17 -
[알고리즘][2] 체육복
체육복 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution..
2023.08.17