태야

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

1번째 풀이 - O(N^2)

import sys

input = sys.stdin.readline

S = input().rstrip()

for i in range(len(S)):
    if S[i] in result:
        result[S[i]] += 1
    else:
        result[S[i]] = 1

    if i == len(S) - 1:
        break

    current_string = S[i]

    for j in range(i + 1, len(S)):
        current_string = current_string + S[j]
        if current_string in result:
            result[current_string] += 1
        else:
            result[current_string] = 1

print(len(result))

시간복잡도 O(n^2)이 걸리는 풀이로 작성했다. 해당 코드를 python의 set 자료형을 활용하면 간단하게 작성할 수 있다. 

python set() 활용 풀이 - O(N^2)

import sys

input = sys.stdin.readline

S = input().rstrip()

result = set()

for i in range(len(S)):
    for j in range(i + 1, len(S) + 1):
        result.add(S[i:j])
print(len(result))

set(집합) 자료형은 집합의 중복을 제거하고 순서를 보장하지 않는 리터럴 객체를 생성한다.

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

1차 풀이

from collections import deque
import sys
input = sys.stdin.readline
[N, K] = list(map(int, input().strip().split()))

def get_answer():
    numbers = deque(range(1, N+1, 1))
    deleted_numbers = []

    i = -1
    count = 0
    while len(deleted_numbers) != N:
        i += 1

        if i >= N:
            i = 0

        if numbers[i] not in deleted_numbers:
            count += 1
            if count == K:
                count = 0
                deleted_numbers.append(numbers[i])
                continue
    return "<" + ", ".join(map(str, deleted_numbers)) + ">"

print(get_answer())

문제점

- 효율성 문제

• 삭제 여부 확인 방식:
  코드에서는 원래의 numbers 데크에서 값을 제거하지 않고, 별도의 deleted_numbers 리스트에 추가한 후, 매번 if numbers[i] not in deleted_numbers:로 삭제 여부를 확인한다. 이 방식은 리스트의 멤버십 검사가 O(n) 시간 복잡도를 가지므로, N이 5000과 같이 큰 경우 불필요하게 많은 연산을 수행하게 되어 성능 문제가 발생할 수 있다.
• 불필요한 자료구조 사용:
  데크(deque)를 선언해두었지만, 데크의 효율적인 회전(rotate) 기능이나 popleft() 등을 활용하지 않고 단순히 인덱스 접근 방식으로 사용하고 있습니다

개선된 코드

from collections import deque
import sys
input = sys.stdin.readline
[N, K] = list(map(int, input().strip().split()))

def get_answer():
    dq = deque(range(1, N+1, 1))
    result = []

    while dq:
        for _ in range(K - 1):
            dq.append(dq.popleft())
        result.append(dq.popleft())


    return "<" + ", ".join(map(str, result)) + ">"

print(get_answer())

개선 효과

- 매번 불필요한 인덱스 접근이나 멤버십 검사를 하지 않아 시간 복잡도를 O(N)으로 줄일 수 있다.

Python rotate 메서드 활용 코드

from collections import deque
import sys

input = sys.stdin.readline
N, K = map(int, input().split())
dq = deque(range(1, N + 1))
result = []

while dq:
    dq.rotate(-(K - 1))  # K-1번 왼쪽으로 회전
    result.append(dq.popleft())

print("<" + ", ".join(map(str, result)) + ">")

요세푸스 문제는 원형 구조를 활용해 특정 규칙에 따라 요소들을 제거하는 시뮬레이션 문제인데, 그 개념 자체는 원형 연결 리스트 (circular linked list)와 매우 유사하다.

주요 포인트

• 원형 연결 리스트:
  노드들이 원형으로 연결되어 있어 마지막 노드의 다음이 첫 번째 노드가 된다. 요세푸스 문제에서는 이 구조를 통해 K번째 원소를 계속해서 찾아 제거하는 과정을 구현한다.
• 시뮬레이션:
  문제의 해결 방법은 실제로 원형 연결 리스트를 사용해 구현할 수도 있고, Python의 deque 같은 자료구조를 이용해 원형 큐의 동작(회전 및 제거)을 시뮬레이션하는 방식으로도 구현할 수 있다.
  예를 들어, deque를 사용하면 rotate()나 popleft() 같은 메서드로 간단하게 원형 구조를 흉내낼 수 있다.
• 알고리즘 선택:
  요세푸스 문제는 원형 연결 리스트를 이용하는 시뮬레이션 문제로 접근할 수 있지만, 경우에 따라 수학적인 공식을 활용해 더 효율적으로 풀 수도 있다. 단, 일반적으로 K가 임의의 값일 때는 시뮬레이션 방법이 가장 직관적이다.

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

import sys

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

def get_answer():
    stack = [] #(높이, 동일 높이 연속 개수) 집합
    result = 0
    for h in heights:
        same_count = 1
        #현재 h보다 작은 사람들은 볼 수 없으므로 pop하고, 그들이 형성헀던 쌍의 수를 더함
        while stack and stack[-1][0] < h:
            result += stack[-1][1]
            stack.pop()

        # 같은 높이의 경우, 같은 높이 그룹의 사람들과는 모두 볼 수 있음
        if stack and stack[-1][0] == h:
            cnt = stack[-1][1]
            stack.pop()
            result += cnt # 같은 높이 사람들과의 쌍 추가

            # 만약 스택에 아직 사람이 남아 있다면, 그 다음 높이 같은 사람과도 볼 수 있음
            if stack:
                result += 1
            same_count = cnt + 1
        else:
            # 스택이 비어있지 않다면, 바로 앞 사람과는 항상 볼 수 있음
            if stack:
                result += 1
        stack.append((h, same_count))
    return result

print(get_answer())

이 알고리즘의 핵심은:

• 왼쪽부터 순회하면서 스택에 (높이, 동일 높이 연속 개수)를 저장한다.
• 현재 사람보다 작은 사람들은 pop하여 그동안 형성된 쌍을 결과에 더하고,
  동일한 높이의 사람들은 하나의 그룹으로 묶어 개수를 관리한다.
• 남아 있는 스택의 최상단이 있다면 그 사람과는 볼 수 있으므로 1을 더한다.

이 방식은 각 사람을 한 번씩만 처리하여 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)으로 최적화할 수 있다.
• 이 방법은 각 빌딩이 스택에 단 한 번 들어가고 한 번씩만 제거되므로 효율적이다.

<내 코드>

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

A.sort()
B.sort(reverse=True)

num = 0
for i in range(N):
    num += A[i]*B[i]

print(num)

<내 코드>

N = int(input())
cards = list(map(int, input().split()))
M = int(input())
nums = list(map(int, input().split()))

cards.sort()


for i in range(M):
    low, high = 0, N-1
    while low <= high:
        mid = (low + high) // 2
        if cards[mid] == nums[i]:
            print(1, end=" ")
            break
        elif cards[mid] < nums[i]:
            low = mid + 1
        else:
            high = mid - 1

        if low > high:
            print(0, end=" ")
            break

처음에 데이터 양을 생각하지 못하고 브루트포스처럼 풀었었다..

정렬된 리스트를 이분탐색으로 범위를 줄여나가면 많은 데이터에서 빠른 시간에 탐색이 가능하다.

<내 코드>

from collections import deque


def bfs(s):
    q = deque()
    visited = [0 for _ in range(n+1)]

    q.append(s)
    visited[s] = 1

    while q:
        x = q.popleft()

        for i in tree[x]:
            if visited[i] == 0:
                visited[i] = 1
                result[i] = result[x] + 1
                q.append(i)


n = int(input())
a, b = map(int, input().split())
m = int(input())
tree = [[] for _ in range(n+1)]
result = [0 for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    tree[x].append(y)
    tree[y].append(x)

bfs(a)
if result[b] != 0:
    print(result[b])
else:
    print(-1)

BFS로 그래프를 탐색하며 현재 탐색하는 노드와 연결된 노드에 현재 노드 값의 +1을 한다. 즉, 연결된 노드를 이동하는 것을 의미한다.

이런 식으로 모든 노드들을 탐색을 마치면 찾고자 하는 노드의 인덱스의 값을 출력해주면 된다.

<내 코드>

import sys
sys.setrecursionlimit(10**6)

n = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

pos = [0]*(n+1)
for i in range(n):
    pos[in_order[i]] = i

# 전위 순회
def divide(in_start, in_end, p_start, p_end):

    if(in_start > in_end) or (p_start > p_end):
        return

    parents = post_order[p_end]  # 후위순회에서 부모노드 찾기
    print(parents, end=" ")

    left = pos[parents] - in_start  # 왼쪽인자 갯수
    right = in_end - pos[parents]  # 오른쪽인자 갯수

    divide(in_start, in_start+left-1, p_start, p_start+left-1)  # 왼쪽 노드
    divide(in_end-right+1, in_end, p_end-right, p_end-1)  # 오른쪽 노드


divide(0, n-1, 0, n-1)

후위 순회에서 부모 노드를 찾아 중위 순회에서 기준으로 삼아 왼쪽, 오른쪽 나눈다. 그리고 왼쪽 자식 트리 노드, 오른쪽 자식 트리 노드를 순회하며 앞의 과정을 반복한다.