태야

배열이나 리스트에서 각 원소에 대해 오른쪽에 있는 원소들 중 자신보다 크거나 같은(또는 보통은 '큰' 경우가 많지만, 변형으로 '크거나 같은' 조건을 쓰기도 한다) 첫 번째 원소를 찾는 문제다.

예시 문제 설명

예를 들어, 배열 A가 주어졌을 때A = [3, 5, 2, 7, 5]각 원소에 대해 오른쪽으로 이동하며, 처음 만나는 자신보다 크거나 같은 원소를 찾습니다.

- 3의 오른쪽에는 5, 2, 7, 5가 있는데, 처음으로 3보다 크거나 같은 수는 5입니다.
- 5의 오른쪽에는 2, 7, 5가 있는데, 2는 작으므로 건너뛰고, 다음 7은 5보다 크므로 7이 됩니다.
- 2의 오른쪽에는 7, 5가 있으므로 7이 첫 번째 큰(또는 같은) 수입니다.
- 7의 오른쪽에는 5만 있으나 5는 7보다 작으므로, 7은 오른쪽에 조건을 만족하는 원소가 없는 것으로 처리합니다.
- 마지막 원소인 5는 오른쪽에 아무 원소도 없으므로 조건을 만족하는 원소가 없습니다.

보통 조건을 만족하는 원소가 없을 경우 -1 또는 0 등 특정 값을 반환합니다.

단순하게 이중 반복문을 사용하면, 각 원소마다 오른쪽의 모든 원소를 확인해야 하므로 시간복잡도가 O(n^2)가 된다. 하지만 스택(stack)을 이용하면, 한 번의 순회로 각 원소를 효율적으로 처리할 수 있다.

스택을 사용하는 이유

• 스택의 특징
  
  • 스택은 후입선출(LIFO) 구조다. 이 특성을 이용하면, 배열을 한 번 순회하면서 "아직 답을 찾지 못한 원소들의 인덱스"를 스택에 저장해 두고, 새로운 원소가 들어올 때마다 이전 원소들과 비교하여 조건(큰 혹은 큰/같은)을 만족하는지 빠르게 확인할 수 있다.
• 시간복잡도
  • 각 원소는 스택에 한 번 push되고, 조건이 맞으면 pop되므로 각 원소가 스택에 들어가고 나오는 과정이 한 번씩 이루어집니다. 따라서 전체 시간 복잡도는 O(n)이 됩니다.

알고리즘 동작 과정

1. 초기화:
   빈 스택을 준비하고, 결과를 저장할 배열을 초기화한다. 결과 배열은 각 원소의 "다음 큰(또는 같은) 수"의 인덱스나 값을 저장할 수 있다.
2. 배열 순회:
   배열의 인덱스를 0부터 n-1까지 순회한다.
   • 현재 원소와 비교:
     현재 원소(A[i])가 들어왔을 때, 스택의 최상단에 있는 인덱스(예: j)를 확인한다.
     • 만약 A[i]가 A[j]보다 크거나(또는 크거나 같은) 하면, A[i]는 A[j]의 조건(다음 큰 또는 같은 수)을 만족하는 원소가 된다.
       따라서 결과 배열의 j번째 위치에 A[i] 또는 인덱스 i를 저장하고, 스택에서 j를 pop한다.
     • 이 과정을 스택이 비거나, 스택의 최상단 원소가 현재 원소보다 크거나 같은 조건을 만족할 때까지 반복한다.
   • 현재 인덱스 push:
     그 후, 현재 인덱스 i를 스택에 push한다.
3. 후처리:
   배열 순회가 끝난 후에도 스택에 남아있는 인덱스들은 오른쪽에 조건을 만족하는 원소가 없는 경우다. 이 경우, 결과 배열에 -1 또는 0을 기록한다.

Python 코드 예시

def next_greater_or_equal(arr):
    n = len(arr)
    result = [-1] * n  # 조건을 만족하는 원소가 없으면 -1로 처리
    stack = []  # 인덱스를 저장하는 스택

    for i in range(n):
        # 현재 원소 arr[i]가 스택의 최상단 원소보다 크거나 같으면 조건을 만족
        while stack and arr[stack[-1]] <= arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    
    return result

# 예시 실행
A = [3, 5, 2, 7, 5]
print(next_greater_or_equal(A))  # 출력 예: [5, 7, 7, -1, -1]

위 글을 요약하자면 다음과 같다.

• 문제: 각 원소에 대해 오른쪽에서 처음으로 자신보다 크거나 같은 원소를 찾는 문제.
• 단순 방법: 이중 반복문을 사용하면 O(n^2) 시간복잡도.
• 스택 사용: 스택을 이용하면 각 원소가 한 번씩만 처리되므로 O(n) 시간복잡도로 해결 가능.
• 핵심: 스택에 아직 답을 찾지 못한 원소의 인덱스를 저장하고, 새 원소가 들어올 때마다 조건에 맞는 이전 원소들을 처리.

https://www.acmicpc.net/problem/6198

이 문제는 "다음 큰(또는 같은) 수(Next Greater or Equal Element)" 문제다. 배열이나 리스트에서 각 원소에 대해 오른쪽에 있는 원소들 중 자신보다 크거나 같은(또는 보통은 '큰' 경우가 많지만, 변형으로 '크거나 같은' 조건을 쓰기도 한다) 첫 번째 원소를 찾는 문제이다.

1. 단순 탐색 풀이 - O(n^2)

from functools import reduce
import sys

input = sys.stdin.readline
N = int(input().strip())
heights = list(int(input().strip()) for _ in range(N))

def get_answer():
    results = []

    while heights:
        height = heights.pop(0)
        count = 0
        for i in range(len(heights)):
            if heights[i] < height:
                count += 1
            else:
                break
        results.append(count)
    print(reduce(lambda acc, value: acc + value, results))

2. 스택 이용 최적화 풀이 - O(n)

from functools import reduce
import sys

input = sys.stdin.readline
N = int(input().strip())
heights = list(int(input().strip()) for _ in range(N))

def get_answer():
    stack = []
    total_visible = 0

    for i in range(N - 1, -1, -1):
        # 현재 빌딩보다 낮은 빌딩들은 스택에서 제거
        while stack and heights[stack[-1]] < heights[i]:
            stack.pop()

        # 스택에 차단 빌딩이 있으면 그 위치까지 빌딩 수 계산
        if stack:
            visible = stack[-1] - i - 1
        else:
            # 오른쪽의 모든 빌딩이 보이는 경우
            visible = N - i - 1
        total_visible += visible

        # 현재 빌딩 인덱스를 추가
        stack.append(i)

    return total_visible

print(get_answer())

• 스택을 활용하면 오른쪽에서 왼쪽으로 한 번의 순회로 각 빌딩의 보이는 옥상 수를 구할 수 있어 전체 시간복잡도를 O(n)으로 최적화할 수 있다.
• 이 방법은 각 빌딩이 스택에 단 한 번 들어가고 한 번씩만 제거되므로 효율적이다.

https://www.acmicpc.net/problem/2493

1. 단순 탐색 풀이 - O(n^2)

시간복잡도 O(n^2)를 가지는 모든 요소를 탐색하는 방식으로 풀이했다. 당연히, 시간초과로 실패했다.

N = int(input().strip())
heights = list(map(int, input().strip().split()))

def get_answer():
    answer = [0 for _ in range(N)]
    for i in range(len(heights), 0, -1):
        if i == 1:
            break
        current_top = heights[i - 1]
        for j in range(i - 1, 0, -1):
            left_top = heights[j - 1]
            if left_top >= current_top:
                answer[i - 1] = j
                break
    print(" ".join(map(str, answer)))

get_answer()

2. 스택 이용한 풀이 - 최악 O(n^2), 최선 O(n)

스택을 사용하면 각 요소를 한 번만 처리(삽입/삭제)하게 되어, 이미 검사한 요소들을 재검사하지 않아도 된다.

일반적으로 스택 기반 알고리즘에서는 리스트를 한 번 순회하며, 현재 요소보다 작은(또는 큰) 후보들은 스택에서 제거하는 식으로 진행하여, 각 요소가 스택에 한 번 push되고 최대 한 번 pop되도록 한다.

최악의 경우:
예를 들어, 만약 리스트가 내림차순 정렬되어 있다면, 각 요소마다 내부 for 루프가 거의 전체 남은 요소를 검사하게 된다.
따라서 전체 연산 횟수는 약 n+(n−1)+(n−2)+…+1=O(n^2)가 된다.

N = int(input().strip())
heights = list(map(int, input().strip().split()))

def get_answer():
    answer = [0 for _ in range(N)]

    while heights:
        height = heights.pop()

        for i in range(len(heights) - 1, -1, -1):
            if height < heights[i]:
                answer[len(heights)] = i + 1
                break

    print(" ".join(map(str, answer)))

get_answer()

3. 스택 이용한 풀이 - 최적화 O(n)

N = int(input().strip())
heights = list(map(int, input().strip().split()))

def get_answer():
    answer = [0 for _ in range(N)]
    stack = [] # 인덱스 저장

    for i in range(len(heights)):
        height = heights[i]
        # 스택에 있는 인덱스의 높이가 현재보다 작으면, 이들은 현재 탑의 신호를 받을 수 없음
        while stack and heights[stack[-1]] < height:
            stack.pop()

        # 스택이 남아 있으면, 스택의 최상단 인덱스가 현재 탑의 신호를 수신하는 탑이다
        if stack:
            answer[i] = stack[-1] + 1
        else:
            answer[i] = 0

        stack.append(i) # 현재 탑 인덱스 추가

    print(" ".join(map(str, answer)))

get_answer()

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프나 트리 탐색에서 사용하는 대표적인 탐색 알고리즘이다. 두 알고리즘 모두 특정 노드를 방문하고, 그 노드와 연결된 다른 노드들을 탐색하는 방식으로 동작한다. DFS는 깊이를 우선으로 탐색하고, BFS는 너비를 우선으로 탐색한다.

1. DFS (Depth-First Search, 깊이 우선 탐색)

DFS는 탐색할 때 가능한 한 깊게 들어가는 방식으로 탐색한다. 즉, 한 경로를 따라 끝까지 가고, 더 이상 갈 곳이 없으면 다시 돌아와 다른 경로를 탐색한다. 이 방식은 재귀나 스택을 사용해 구현할 수 있다.

DFS 예시: 그래프 탐색

function dfs(graph, start, visited = new Set()) {
    // 현재 노드 방문 처리
    visited.add(start);
    console.log(start);

    // 현재 노드와 연결된 노드들을 재귀적으로 방문
    for (let neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}
// 그래프 표현 (인접 리스트)
const graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
}

dfs(graph, 1);  // 출력: 1 2 4 3 5

DFS의 시간 복잡도

• 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 그래프의 모든 노드를 방문하고 모든 간선을 처리해야 하기 때문에, 위와 같은 복잡도를 가진다.

2. BFS (Breadth-First Search, 너비 우선 탐색)

BFS는 탐색할 때 가까운 노드부터 차례대로 방문한다. 즉, 특정 노드에서 연결된 모든 노드를 먼저 탐색한 후, 그 다음 깊이의 노드들을 탐색한다. 이 방식은 큐(Queue) 자료 구조를 사용해 구현한다.

BFS 예시: 최단 경로 탐색

function bfs(graph, start) {
    const queue = [start]; // 탐색할 노드를 저장할 큐
    const visited = new Set(); // 방문한 노드를 저장할 집합
    visited.add(start);

    while (queue.length > 0) {
        const node = queue.shift(); // 탐색할 노드를 큐에서 꺼냄
        console.log(node);

        for (let neighbor of graph[node]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
}

// 그래프 표현 (인접 리스트)
const graph = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [],
    5: []
};

bfs(graph, 1);  // 출력: 1 2 3 4 5

BFS의 시간 복잡도

• 시간 복잡도: O(V + E) (V는 노드 수, E는 간선 수)
• 모든 노드와 모든 간선을 한 번씩 방문하기 때문에 DFS와 마찬가지로 같은 복잡도를 가진다.

DFS와 BFS의 차이

• 탐색 방식: DFS는 깊이 우선으로 탐색하며, BFS는 너비 우선으로 탐색한다.
• 구현 방식: DFS는 재귀나 스택을 사용하고, BFS는 큐를 사용해 구현한다.
• 사용 사례:
  • DFS는 경로 탐색(예: 미로 찾기)나 백트래킹이 필요한 문제에 적합하다.
  • BFS는 그래프에서 최단 경로를 찾는 문제에 적합하다.

예시 문제

1. 미로 찾기

문제: N x M 크기의 미로가 주어질 때, 출발점에서 도착점까지 최단 경로를 찾으세요. 벽은 통과할 수 없으며, 상하좌우로만 이동할 수 있습니다.

// BFS
function shortestPath(maze, start, end) {
    const directions = [[0, 1], [1, 0], [0, -1], [1, 0]];
    const queue = [[start, 0]]; // [현재위치, 이동거리]
    const visited = new Set();
    visited.add(start.toString());

    while (queue.length > 0) {
        const [[x, y], distance] = queue.shift();

        if (x === end[0] && y === end[1]) return distance;

        for (let [dx, dy] of directions) {
            const newX = x + dx;
            const newY = y + dy;

            if (newX >= 0 && newY >= 0 &&
                newX < maze.length && newY < maze[0].length &&
                maze[newX][newY] === 0 && !visited.has([newX, newY].toString())
            ) {
                visited.add([newX, newY].toString());
                queue.push([[newX, newY], distance + 1]);
            }
        }
    }

    return -1; // 도착할 수 없는 경우
}

const maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
];

console.log(shortestPath(maze, [0, 0], [4, 4]));  // 출력: 8 (최단 경로 거리)

2. 섬 개수 세기

문제: 2차원 배열에서 육지를 1, 바다를 0으로 나타내는 섬의 지도에서, 섬(연결된 1의 집합)의 개수를 구하세요.

// DFS
function numIslands(grid) {
    let count = 0;

    function dfs(grid, x, y) {
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] === '0') {
            return;
        }

        grid[x][y] = '0'; // 방문한 곳은 0 처리
        dfs(grid, x + 1, y);
        dfs(grid, x - 1, y);
        dfs(grid, x, y + 1);
        dfs(grid, x, y - 1);
    }

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }

    return count;
}

const grid = [
    ['1', '1', '0', '0', '0'],
    ['1', '1', '0', '0', '0'],
    ['0', '0', '1', '0', '0'],
    ['0', '0', '0', '1', '1']
];

console.log(numIslands(grid));  // 출력: 3 (3개의 섬)