이 문제는 n개의 노드(점)로 이루어진 무방향 스타 그래프에 관한 것입니다. 스타 그래프는 하나의 중심 노드가 있고, 나머지 n-1개의 노드가 그 중심 노드와 연결된 구조를 가집니다.
edges라는 2차원 정수 배열이 주어집니다. edges[i] = [ui, vi]는 노드 ui와 노드 vi 사이에 엣지가 있다는 것을 나타냅니다. 주어진 스타 그래프의 중심 노드를 반환하는 것이 이 문제의 목표입니다.
예시
예시 1:
입력: edges = [[1,2],[2,3],[4,2]]
출력: 2
설명: 노드 2는 다른 모든 노드와 연결되어 있으므로 중심 노드입니다.
예시 2:
입력: edges = [[1,2],[5,1],[1,3],[1,4]]
출력: 1
설명: 노드 1은 다른 모든 노드와 연결되어 있으므로 중심 노드입니다.
해결 방안
중심 노드를 찾기 위해서는 각 엣지에서 공통적으로 등장하는 노드를 찾으면 됩니다. 왜냐하면 스타 그래프에서 중심 노드는 모든 엣지에 등장하기 때문입니다. 아래의 방법으로 문제를 해결할 수 있습니다:
첫 번째 엣지를 선택합니다. (edges[0])
첫 번째 엣지의 두 노드 중 하나는 중심 노드입니다.
두 번째 엣지에서도 이 두 노드 중 하나가 등장하는지를 확인합니다.
등장한다면 그 노드가 중심 노드입니다.
코드
def findCenter(edges):
# 첫 번째 엣지의 두 노드를 선택합니다.
a, b = edges[0]
# 두 번째 엣지에서 a 또는 b가 등장하는지를 확인합니다.
# 만약 a가 등장하면 a가 중심 노드입니다.
if edges[1][0] == a or edges[1][1] == a:
return a
# 그렇지 않으면 b가 중심 노드입니다.
else:
return b
# 예시 테스트
print(findCenter([[1, 2], [2, 3], [4, 2]])) # 출력: 2
print(findCenter([[1, 2], [5, 1], [1, 3], [1, 4]])) # 출력: 1
코드 설명
edges[0]에서 두 노드를 가져옵니다. 여기서 a와 b는 첫 번째 엣지의 노드입니다.
두 번째 엣지(edges[1])에서 첫 번째 엣지의 노드 a 또는 b가 있는지 확인합니다.
만약 a가 두 번째 엣지에 포함되어 있다면 a가 중심 노드입니다.
그렇지 않다면 b가 중심 노드입니다.
최종적으로 중심 노드를 반환합니다.
이 방법은 매우 효율적이며, 두 번째 엣지만 확인하면 중심 노드를 찾을 수 있으므로 O(1)의 시간 복잡도를 가집니다.
음수를 찾으면, 그 열 이하의 모든 값이 음수라는 것을 알 수 있습니다(왜냐하면 내림차순이기 때문입니다).
따라서 그 지점에서 남은 모든 값을 음수로 간주하고, 음수의 개수를 누적합니다.
구체적인 단계는 다음과 같습니다:
행(row)별로 반복합니다.
각 행의 오른쪽 끝부터 시작하여 왼쪽으로 이동합니다.
음수를 만나면 해당 지점에서 그 행의 끝까지 남은 요소의 개수를 더합니다.
다음 행으로 이동하여 동일한 과정을 반복합니다.
예제
위의 예제 행렬을 통해 설명하면:
첫 번째 행: [-1]에서 음수를 만나므로 1개의 음수 발견
두 번째 행: [-1]에서 음수를 만나므로 1개의 음수 발견
세 번째 행: [-1, -2]에서 음수를 만나므로 2개의 음수 발견
네 번째 행: [-1, -1, -2, -3]에서 음수를 만나므로 4개의 음수 발견
이렇게 총 8개의 음수를 발견하게 됩니다.
코드
from typing import List
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
# 시작은 마지막 열의 처음 행
row, col = 0, n - 1
while row < m and col >= 0:
if grid[row][col] < 0:
# 음수를 만나면, 해당 열 아래 모든 행이 음수이므로 추가
count += (m - row)
col -= 1
else:
# 음수를 만나지 않으면 다음 행으로 이동
row += 1
return count
# 예제 테스트
solution = Solution()
grid1 = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
print(solution.countNegatives(grid1)) # 8
grid2 = [[3,2],[1,0]]
print(solution.countNegatives(grid2)) # 0
설명
시작 지점: 맨 위 행(row)의 마지막 열(col)에서 시작합니다.
탐색 방식:
현재 위치의 값이 음수일 경우, 해당 열 이하의 모든 값이 음수임을 알 수 있으므로, 그 수만큼 카운트합니다. 그리고 왼쪽 열로 이동합니다.
현재 위치의 값이 음수가 아닐 경우, 다음 행으로 이동합니다.
반복: 행(row) 또는 열(col)의 끝에 도달할 때까지 반복합니다.
결과 반환: 모든 음수의 개수를 반환합니다.
이 방식은 매번 음수를 만날 때마다 그 아래 모든 값을 계산하기 때문에 더 효율적이며, 시간 복잡도는 최악의 경우 O(m+n))입니다.
초기 설정: 배열의 처음과 끝을 가리키는 두 개의 포인터(left와 right)를 설정합니다.
중간 요소 찾기: left와 right의 중간 지점을 계산하여 mid로 설정합니다.
비교:
nums[mid]가 타겟 값과 같으면, mid를 반환합니다.
nums[mid]가 타겟 값보다 작으면, 타겟 값은 mid의 오른쪽에 있으므로 left를 mid + 1로 이동시킵니다.
nums[mid]가 타겟 값보다 크면, 타겟 값은 mid의 왼쪽에 있으므로 right를 mid - 1로 이동시킵니다.
반복: left가 right보다 작거나 같을 때까지 2-3 단계를 반복합니다.
결과: 탐색 범위가 없으면 타겟 값이 배열에 없음을 의미하며, 이때 삽입 위치를 반환할 수 있습니다.
예시
정렬된 배열 nums = [1, 3, 5, 7, 9]와 타겟 값 target = 7을 찾는 예시를 통해 설명하겠습니다:
초기 설정: left = 0, right = 4 (배열의 인덱스 범위)
중간 요소 찾기: mid = (0 + 4) // 2 = 2
nums[2] = 5
비교: 5 (nums[mid]) < 7 (target)
left = mid + 1 = 3
반복:
새로운 중간 요소 찾기: mid = (3 + 4) // 2 = 3
nums[3] = 7
비교: 7 (nums[mid]) == 7 (target)
타겟 값을 찾았으므로 mid = 3 반환
이 과정에서 타겟 값을 효율적으로 찾을 수 있습니다.
35. Search Insert Position
이 문제는 주어진 정렬된 배열에서 특정 값을 찾는 문제입니다. 만약 해당 값을 찾으면 그 인덱스를 반환하고, 찾지 못하면 그 값을 정렬된 순서에 맞게 삽입할 때의 인덱스를 반환하는 문제입니다. 이 문제는 이진 탐색 알고리즘을 사용하면 O(log n)의 시간 복잡도로 해결할 수 있습니다.
이진 탐색은 배열의 중간 요소와 타겟 값을 비교하고, 비교 결과에 따라 탐색 범위를 절반으로 줄여가는 방식으로 동작합니다. 정렬된 배열에서 빠르게 값을 찾거나 삽입할 위치를 찾기에 적합합니다.
피보나치 수열은 수학에서 매우 유명한 수열 중 하나로, 각 숫자가 그 앞의 두 숫자의 합으로 이루어진 수열입니다. 이 수열은 이탈리아의 수학자 피보나치(Leonardo of Pisa, 피사르 피보나치)에 의해 서양에 소개되었습니다. 피보나치 수열은 다음과 같은 규칙을 따릅니다
첫 번째 숫자 (F(0))는 0입니다.
두 번째 숫자 (F(1))는 1입니다.
세 번째 숫자부터는 이전 두 숫자의 합입니다. 즉, F(n) = F(n-1) + F(n-2) (n > 1인 경우).
