🤖 옌지니어의 IT 기록 🤖

https://school.programmers.co.kr/learn/courses/30/lessons/76502

문제

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다.
  예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다.
  예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• s의 길이는 1이상 1,000이하입니다.

입출력 예

소스 코드

def solution(s):
    answer = 0
    n = len(s)

    for i in range(n):
        stack = []  
        for j in range(n):
            # 문자열 회전
            c = s[(i+j)%n]

            # 열린괄호의 경우
            if c=="(" or c=="[" or c=="{":
                stack.append(c)
            # 닫힌괄호의 경우
            else:
                # 스택이 비어있다면 0을 추가하고 종료
                if len(stack)==0:
                    stack.append(0)
                    break
                # 스택의 가장 마지막을 확인하고 짝이 맞다면 제거
                elif c==")" and stack[-1]=="(":     
                    stack.pop()
                elif c=="]" and stack[-1]=="[":
                    stack.pop()
                elif c=="}" and stack[-1]=="{":
                    stack.pop()
                # 짝이 맞지 않은 경우 0을 추가하고 종료
                else:
                    stack.append(0)
                    break
        
        # 중간에 종료되지 않았다면 스택은 비어있으므로 +1
        if not stack:
            answer += 1

    return answer

풀이

• for문에 따라 괄호 문자열을 회전
• 문자열이 열린괄호인 경우 스택에 괄호를 추가
• 문자열이 닫힌괄호인 경우
  • 닫힌괄호이면서 스택이 비어있다면 앞에 열린괄호가 없는 것이므로 스택에 0을 추가하고 종료
  • 닫힌괄호와 스택에 마지막 문자와 짝 맞추기 (짝이 맞다면 제거)
  • 짝이 맞지 않다면 스택에 0을 추가하고 종료
• 중간에 종료되었다면 스택에 0이 있을 것이고 아니라면 스택이 비어있을 것이므로 answer + 1

문자열을 회전하면서 짝을 맞춰야하는 문제였다. 경우의 수를 나누어서 생각하는 것이 좀 어려웠다... 알고리즘 책에서 스택의 예시 문제로 나와있어서 스택으로 풀어야겠다고 생각할 수 있었는데 문제만 봤을 때는 스택을 떠올리기 힘들었을 것 같다.

스택(Stack)이란?

먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조

• FILO(First In Last Out) : 먼저 들어간 것이 마지막에 나오는 규칙
• push : 스택에 삽입하는 연산 / pop : 스택에서 꺼내는 연산

스택의 동작원리

스택의 ADT (Abstract Data Type)

추상 자료형이라는 뜻으로 인터페이스만 있고 실제로 구현은 되지않은 자료형

스택의 세부동작

스택 구현하기

stack = []          # 스택 리스트 초기화
max_size = 10       # 스택의 최대크기

# 스택이 가득찼는지 확인하는 함수
def isFull(stack):
    return len(stack) == max_size

# 스택이 비어있는지 확인하는 함수
def isEmpty(stack):
    return len(stack) == 0

# 스택에 데이터를 추가하는 함수
def push(stack, item):
    if isFull(stack):
        print("스택이 가득 찼습니다.")
    else:
        stack.append(item)
        print("데이터가 추가되었습니다.")

# 스택에서 데이터를 꺼내는 함수
def pop(stack):
    if isEmpty(stack):
        print("스택이 비어있습니다.")
        return None
    else:
        return stack.pop()

• 파이썬의 리스트는 크기를 동적으로 관리하므로 실제 코드에서 max_size, isFull(), isEmpty() 함수 구현 X
• push(), pop() 함수가 하는 일은 리스트의 메서드를 호출하는 것 뿐이므로 굳이 구현 X
• 위의 코드를 아래 코드로 바꾸어서 사용

stack = []

# 스택에 데이터 추가
stack.append(1)
stack.append(2)
stack.append(3)

# 스택에서 데이터 꺼내기
top_element = stack.pop()	# top_element = 3
next_element = stack.pop()	# next_element = 2

# 스택의 크기 구하기
stack_size = len(stack)

→ 스택의 개념 자체는 어렵지 않지만 문제를 보고 스택을 떠올리기 위해 문제연습이 필요 !!

※ 참고 자료 ※

https://wikidocs.net/221191

“모두를 위한 AI 슈퍼컴” 애저 클라우드 AI 데이터센터의 내부 살펴보기 (링크)

기사 내용 요약

 빌드 컨퍼런스에서 마이크로소프트는 추론 가속기, 고대역폭 연결, 효율성과 안정성을 위한 각종 툴을 통해 애저 클라우드가 대규모 AI 워크로드를 어떻게 지원하는지 설명했다.

AI 슈퍼컴퓨터 구축
 AI 플랫폼을 실행하는 데 필요한 시스템의 규모는 엄청나다. 2024년 6월, 마이크로소프트는 전 세계 데이터센터에 30대 이상의 유사한 슈퍼컴퓨터를 보유하고 있다. 일단 모델이 구축되면 이를 사용해야 하는데, 추론에는 슈퍼컴퓨터 수준의 연산 능력이 필요하지 않지만 여전히 많은 컴퓨팅 성능이 필요하다. 이는 애저 클라우드가 많은 데이터를 최대한 빠르게 처리하기 위해 매우 구체적인 특성을 가진 많은 GPU가 필요하다는 것을 의미한다.

트레이닝을 넘어 추론을 위한 설계
 애저 클라우드의 프로젝트 POLCA는 최대 전력 소비에 대응하는 프로비저닝을 통해 여러 추론 작업을 동시에 실행할 수 있으므로 약 20%의 오버헤드를 줄일 수 있다. 이를 통해 서버 주파수와 전력을 조절해 데이터센터에 30% 더 많은 서버를 배치하여 AI 데이터센터의 컴퓨팅, 전력, 열 수요에 대해 보다 효율적이고 지속 가능한 접근 방식이 가능해졌다.
 또한, 마이크로소프트는 데이터를 관리하기 위해 스토리지 가속기라고 부르는 기능을 개발했다. 이 기능은 현재 작업을 방해하지 않으면서 가용 대역폭을 이용해 필요한 데이터를 로컬이나 클라우드에서 사용할지 결정하는 캐시를 통해 클러스터에 데이터를 분산하고 있다. 병렬 읽기를 사용해 데이터를 로드하면 대량의 학습 데이터를 기존 방식보다 거의 두 배 빠르게 로드할 수 있다.

AI에 필요한 고대역폭 네트워크
컴퓨팅과 스토리지도 중요하지만 수백 개의 GPU에서 작동하는 대규모 데이터 병렬 워크로드에서는 네트워킹이 여전히 중요하다. 마이크로소프트는 서버에서 1.2TBps의 내부 연결을 사용해 8개의 GPU를 연결하고 동시에 인피니밴드 기술을 이용해 개별 서버의 개별 GPU 간에 400Gbps를 연결한다.

신뢰할 수 있는 AI를 만드는 프로젝트 포지와 원풀
소프트웨어 스택은 기본 플랫폼 오케스트레이션 및 지원 툴을 제공한다. 이것이 바로 프로젝트 포지(Project Forge)가 등장하는 이유이다. 분산 인프라 전반에서 작업을 예약하는 동시에 필수 리소스 관리를 제공하고 다양한 유형의 AI 컴퓨팅에 부하를 분산하는 방법으로, 쿠버네티스와 같은 것으로 생각할 수 있다. 프로젝트 포지의 스케줄러는 AI 가속기를 가상 GPU 용량의 단일 풀로 취급하며 이를 원풀(One Pool)이라고 부른다. 각 워크로드에는 이런 가상 GPU에 대한 액세스를 제어하는 우선순위를 두어 관리한다. 또한 프로젝트 포지는 장애를 감지하고 작업을 다시 시작해 호스트 플랫폼을 복구하여 탄력적인 서비스를 실행할 수 있다.

일관성 및 보안 : AI 애플리케이션을 위한 준비 완료
애저의 프로젝트 플라이휠(Project Flywheel)은 성능을 보장하는 역할을 하는데, 가상 GPU에서 여러 프롬프트의 작업을 인터리빙해 호스트 물리 GPU에서 일관된 작업을 수행하면서도 일정한 처리량을 제공할 수 있다. 또 다른 기반 최적화로는 사용자 지정 모델을 학습할 때 적용하는 기밀 컴퓨팅 기능이 있는데, 신뢰할 수 있는 실행 환경에서 코드를 실행하고 데이터를 호스트할 수 있다.

핵심 용어

• Azure 데이터센터란?
  • Azure 데이터 네트워크로 연결된 컴퓨터 서버가 보관되어 있는 전 세계에 위치한 물리적 건물
• 슈퍼컴퓨터란?
  • 표준 컴퓨터보다 높은 성능으로 작동하는 컴퓨터
  • 오늘 날의 슈퍼컴퓨터는 초당 수십억 개까지 계산할 수 있는 수만 개의 프로세서로 구성
• 네트워킹(Networking) 이란?
  • 네트워크에 연결된 장비를 연결하고 네트워크를 통해 데이터 패킷을 전송하는데 사용되는 장비

※ Reference ※

https://azure.microsoft.com/ko-kr/explore/global-infrastructure (Azure 인프라 용어 가이드)

https://www.purestorage.com/kr/knowledge/what-is-a-supercomputer.html (슈퍼컴퓨터 관련 내용)

https://www.advancedenergy.com/ko-kr/applications/telecom-and-networking/networking/ (일반적인 네트워킹 관련 내용)

https://learn.microsoft.com/ko-kr/azure/networking/fundamentals/networking-overview (Azure 네트워킹 서비스 관련 내용)

진짜 잘 모르는 인프라 관련 기사도 읽어보기....모르는 용어 너무 많고 어떻게 구성됐는지 사실 잘 모르겠다. 각각의 구성요소에 대해 조금씩 찾아보긴 했는데 이런 내용들이 쌓이다 보면 인프라에 대해서도 어느 정도 알게 되지 않을까 싶다.

배열

인덱스와 값을 일대일 대응해 관리하는 자료구조

• 데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응
• 어떤 위치에 있는 데이터든 한 번에 접근 가능 → 임의 접근 (random access)

배열을 선언하는 방법

# 1. 일반적인 방법
arr = [0,0,0,0,0,0]
arr = [0] * 6

# 2. 리스트 생성자를 사용하는 방법
arr = list(range(6))			# [0,1,2,3,4,5]

# 3. 리스트 컴프리헨션을 활용하는 방법
arr = [0 for _ in range(6)]		# [0,0,0,0,0,0]

※ 파이썬의 경우 배열 대신 리스트를 사용 ※

배열과 차원

• 배열은 2차원, 3차원과 같이 다차원 배열로도 사용
• 컴퓨터 메모리 구조는 1차원이므로 다차원 배열도 1차원 공간에 저장
• 배열은 차원과 무관하게 메모리에 연속 할당

1차원 배열

• 가장 간단한 배열 형태
• 배열의 모습 = 메모리에 할당된 실제 배열의 모습

2차원 배열

• 1차원 배열을 확장한 것

# 2차원 배열을 리스트로 표현
arr = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]

# 저장된 값 출력
print(arr[2][3])

# 저장된 값을 변경
arr[2][3] = 15

# 리스트 컴프리헨션을 활용
arr = [[i]*4 for i in range(3)]

배열 연산의 시간 복잡도

• 배열은 임의 접근이라는 방법으로 모든 위치에 있는 데이터에 단 한 번에 접근 가능
• 데이터에 접근하기 위한 시간복잡도는 O(1)

배열에 데이터를 추가하는 경우

(1) 맨 뒤에 삽입할 경우

• 다른 데이터 위치에 영향 X
• 시간복잡도 = O(1)

(2) 맨 앞에 삽입할 경우

• 기존 데이터들을 뒤로 한 칸씩 미는 연산 필요
• 시간복잡도 = O(N)

(3) 중간에 삽입할 경우

• 현재 삽입한 데이터 뒤에 있는 데이터 개수만큼 미는 연산 필요
• 시간복잡도 = O(N)

배열을 선택할 때 고려할 점

• 할당할 수 있는 메모리 크기 확인
  • 표현하려는 데이터가 너무 많으면 런타임에서 배열 할당 실패
  • 보통 정수형 1차원 배열은 1000만개, 2차원 배열은 3000*3000 크기가 최대
• 중간에 데이터 삽입이 많은지 확인
  • 배열은 선형 자료구조이므로 빈번하게 삽입하면 시간 초과 발생

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

(알고리즘 수업 문제는 시간 복잡도가 무엇인지 확인하고 풀어보기)

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

→ 코드1 이 21회 수행되고 알고리즘의 수행 시간이 n²에 비례한다.

소스 코드

# 문제 시각화
n = int(input())
sum = 0
count = 0

for i in range(1,n):
    for j in range(i+1,n+1):
        sum += (i * j)    # 코드 1
        count += 1
        print("{:^4}+({}*{})={:^4} ({:^2}번 수행)\t".format(sum-(i*j),i,j,sum,count), end="   ")
    print()

# 정답 코드
n = int(input())

print(int(n*(n-1)/2))
print(2)

풀이

• 첫 번째 for문은 총 n번 수행
• 두 번째 for문은 n-i번 수행
  • i=1인 경우, n-1번 수행
  • i=2인 경우, n-2번 수행
• 수행 횟수 공식을 첫 번째 줄에 출력
  • 첫 번째 for문이 수행된 횟수 n과 두 번째 for문이 수행된 횟수 n-i를 곱한 값 (중복을 제거하기 위해 2로 나누기)
• 위의 공식에서 최고차항의 차수인 2를 두 번째 줄에 출력
  • 시간 복잡도(=코드1의 수행횟수)는 n*(n-1)/2이므로 최고차항의 차수는 2

이전 포스팅과 마찬가지로 시간 복잡도에 대해 알면 쉽게 풀 수 있는 문제였다. 익숙한 언어로 for문이 총 몇 번 수행되는지를 시각화해보면 좋을 것 같다.

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

(알고리즘 수업 문제는 시간 복잡도가 무엇인지 확인하고 풀어보기)

문제

오늘도 서준이는 알고리즘의 수행시간 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

입력의 크기 n이 주어지면 MenOfPassion 알고리즘 수행 시간을 예제 출력과 같은 방식으로 출력해보자.

MenOfPassion 알고리즘은 다음과 같다.

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

입력

첫째 줄에 입력의 크기 n(1 ≤ n ≤ 500,000)이 주어진다.

출력

첫째 줄에 코드1 의 수행 횟수를 출력한다.

둘째 줄에 코드1의 수행 횟수를 다항식으로 나타내었을 때, 최고차항의 차수를 출력한다. 단, 다항식으로 나타낼 수 없거나 최고차항의 차수가 3보다 크면 4를 출력한다.

→ 코드 1이 7회 수행되고 수행 시간이 n에 비례한다.

소스 코드

# 문제 시각화
n = int(input())
sum = 0

for i in range(1,n+1):
    sum += i    # 코드 1
    print(sum-i, "+", i, "=", sum, "\t", i,"번 수행")

# 정답 코드
n = int(input())

print(n)
print(1)

풀이

• 문제에서 코드1은 총 n번 수행
• 입력의 크기 n을 첫 번째 줄에 출력
• 최고차항의 차수인 1을 두 번째 줄에 출력
  • 시간 복잡도(=코드1의 수행횟수)는 n이므로 최고차항의 차수는 1

시간복잡도가 뭔지 몰랐을 때는 문제 이해가 아예 안됐는데 개념을 알고 나서 푸니까 쉽게 풀 수 있었다. 일단 문제의 내용을 시각화해서 코드가 총 몇 번 수행되는지 알면 쉽게 풀 수 있다!!!

코딩테스트 문제를 풀기 위해 "가장 효율적으로 해결하는 알고리즘" 필요

→ 효율적으로 푸는 것은 제한 시간과 관련이 있으며 문제를 빠르게 푸는 알고리즘 선택

알고리즘 수행 시간을 측정하는 방법

1) 절대 시간 측정 : 말 그대로 시간 측정

2) 시간 복잡도 측정 : 알고리즘 시작 순간부터 결괏값이 나올 때까지의 연산 횟수 측정

• 입력 크기 : 입력 크기가 다양하며 이에 따라 결과가 달라지므로 N으로 일반화
• 측정 결과 : 최선(best) / 보통(normal) / 최악(worst)
• 표현 방식 : 점근 표기법으로 사용

시간 복잡도 (Time Complexity)

알고리즘의 성능을 나타내는 지표로 입력 크기에 대한 연산 횟수

ex) 1차원 배열 검색

• 값을 가장 빨리 찾는 경우 : 검색 시작 위치에 찾을 값이 바로 위치한 경우
• 값을 가장 늦게 찾는 경우 : 찾으려는 값이 없거나 가장 마지막에 위치한 경우

점근적 표기법

입력 크기에 따른 연산 횟수의 추이를 활용해 시간 복잡도 표현

• 빅오(Big-O, O) 표기법 : 최악일 때 연산횟수 (수행시간의 상한)   ★ 주로 사용 ★
  • 모든 케이스를 통과해야하므로 주로 최악의 경우인 빅오를 기준으로 계산 
• 빅오메가(Big-Omega, Ω) 표기법 : 최선일 때 연산횟수 (수행시간의 하한)
• 빅세타(Big Theta, Θ) 표기법 : 보통일 때 연산횟수 (수행시간의 상한과 하한)

빅오 표기법의 종류

1. O(1) : 상수

입력 데이터 크기에 상관없이 일정한 시간 소요

ex) 스택의 Push / Pop

2. O(log N) : 로그

입력 데이터의 크기가 커질수록 처리 시간 감소

ex) 이진트리 / 순기능으로 이루어지는 재귀

3. O(N) : 선형

입력 데이터의 크기에 비례해 처리 시간 증가 (N크기만큼 처리 시간 증가)

ex) for문

4. O(N log N) : 선형 로그

입력 데이터가 많아질수록 처리 시간이 로그의 배만큼 증가

ex) 퀵 정렬(Quick Sort) / 합병 정렬(Merge Sort) / 힙 정렬(Heap Sort)

5. O( N² ) : 다항

입력 데이터를 N만큼 반복하고 그 안에서도 N만큼 반복하여 처리 시간이 급수적으로 증가

ex) 삽입 정렬(Insertion Sort) / 버블 정렬(Bubble Sort) / 선택 정렬(Selection Sort) / 이중 for문

6. O( 2ⁿ ) : 지수

입력 데이터가 많아질수록 처리 시간이 기하급수적으로 증가

ex) 피보나치(Fibonacci) 수열

엔비디아, 합성 데이터 생성하는 ‘네모트론-4 340B’ 출시..."비용 문제 해결한 오픈 소스 최강 성능" (링크)

기사 내용 요약

엔비디아가 대형언어모델(LLM) 학습용 합성 데이터를 생성하도록 설계한 모델 ‘네모트론-4 340B(Nemotron-4 340B)'를 공개했다. 이를 통해 비용이 많이 드는 실제 데이터셋 없이도 도메인별 LLM을 구축할 수 있게 됐다는 설명이다. 네모트론-4 340B는 9조 토큰을 사용해 사전 훈련했으며, 4000토큰의 컨텍스트 창을 제공하고 50개 이상의 언어와 40개 프로그래밍 언어를 지원한다.
네모트론-4 340B 베이스 모델은 맞춤형 합성 데이터를 생성하기 위한 기본 프레임워크 역할을 한다. 독점 데이터와 다양한 데이터셋를 사용해 특정 사용 사례에 맞게 미세 조정할 수 있다. 
네모트론-4 340B 인스트럭트 모델은 실제 데이터를 모방하는 합성 데이터를 생성, 데이터 품질을 개선하고 다양한 도메인에서 맞춤형 LLM의 성능을 향상한다. 
네모트론-4 340B 리워드 모델은 생성 데이터의 품질을 필터링하고 향상하는 역할을 한다. 유용성, 정확성, 일관성, 복잡성 및 자세한 정도에 따라 응답을 평가해 생성 데이터가 고품질 표준을 충족하는지 확인한다.

핵심 용어

• 합성 데이터란?
  • 실제 데이터를 모방한, 인간이 생성하지 않은 데이터
  • 생성형 인공 지능 기술을 기반으로 한 컴퓨팅 알고리즘 및 시뮬레이션을 통해 생성
• 합성 데이터 생성 방식
  • 통계적 분포 : 실제 데이터를 분석하여 기본 통계 분포를 식별하고 합성 샘플을 생성
  • 모델 기반 : 실제 데이터 특성을 이해하고 이를 복제하는 기계 학습 모델을 사용
  • 딥러닝 방식 : 생성형 대립 네트워크(GAN), 변이형 오토인코더(VAE) 등의 기술을 통해 합성 데이터 생성
• 컨텍스트 창이란?
  • 프롬프트에 대한 응답을 생성할 때 입력으로 사용할 수 있는 토큰의 수
  • 컨텍스트 창이 클수록 컨텍스트 내 학습 수행 기능(in-context learning) 향상 →  더 큰 예제를 제공해 성능 향상

※ Reference ※

https://aws.amazon.com/ko/what-is/synthetic-data/ (합성 데이터 관련 내용 - AWS)

https://blogs.nvidia.co.kr/blog/what-is-synthetic-data-2/ (합성 데이터 관련 내용 - NVDIA)

https://www.aitimes.com/news/articleView.html?idxno=152588 (컨텍스트 창 관련 기사)

생성형 AI를 도입할 때 데이터에 따라서 성능이 좌우되므로 데이터 수집은 중요하다. 합성 데이터를 생성하는 모델이 출시되어 데이터를 준비하는 것도 수월하게 할 수 있다니...너무 좋은데....사람이 할 일이 점점 줄어드는 것 같아서 슬프다.