최근 즐기고 있는 게임에서 단순하지만 게임의 재미를 배가시키는 기능이 있습니다. 바로 AI 기반 실시간 번역 기능입니다. 채팅을 하다가 번역이 필요할 때, 말풍선 우측 하단의 AI 버튼만 누르면 됩니다.

이 기능 덕분에 전 세계 유저들이 각자 모국어로 대화해도 문제없이 소통할 수 있습니다. 위의 이미지만 봐도 아랍어, 포루투갈어, 독어 등 여러 언어가 섞여 있는데, 모두가 한 서버에서 실시간으로 대화하며 게임을 즐깁니다. 이는 과거의 다국적 게임과는 매우 다른 경험입니다.

예전의 게임 산업에서는 언어 장벽이 커서, 국가별로 서버를 분리하고 마케팅도 따로 진행해야 했습니다. 그 결과, 특정 국가에서의 성공 여부가 게임사의 수익성에 크게 영향을 미쳤습니다.

하지만 이제는 AI 번역 기술 덕분에 한 서버에서 다양한 국가의 유저들이 언어의 장벽을 넘어 소통하게 되면서, 게임사들은 글로벌 시장으로의 확장을 더욱 유연하게 꾀할 수 있습니다. 이로 인해 마케팅 비용 절감, 더 많은 유저 유입, 그리고 더 긴 리텐션으로 이어질 수 있습니다. 국가 간 경계를 초월한 글로벌 커뮤니티의 형성은 유저 경험을 확장하고, 게임의 수명까지 연장시킬 가능성이 큽니다.

뿐만 아니라, 실시간 AI 번역은 단순히 언어의 문제를 넘어서, 문화적 차이도 좁혀줍니다. 서로 다른 배경을 가진 유저들이 자연스럽게 소통하면서, 게임 안에서 새로운 협력과 경쟁의 장을 열고 있습니다. 이러한 경험은 유저들 간의 교류를 촉진하고, 게임 세계를 더욱 다채롭게 만듭니다.

사람들은 보통 AI 기술을 프로덕트에 적용한다고 하면, 아주 거창한 변화를 기대하기 마련입니다. 하지만 이렇게 번역과 같은 간단한 변화만으로도 충분히 큰 임팩트를 만들어낼 수 있습니다. 실시간 AI 번역은 그 자체로 게임 유저 경험을 혁신하고, 글로벌 확장과 같은 비즈니스 전략에도 지대한 영향을 미치고 있습니다. 복잡한 기술 도입이 아니더라도, 유저들에게 실질적인 가치를 제공하는 작은 변화가 어떻게 더 큰 결과를 만들어낼 수 있는지, 이 사례가 잘 보여주는 것 같습니다.

매일 무언갈 꾸준히 쌓는건 누구나 할 수 있지만 또 마냥 쉽지많은 않은 참 어려운 일입니다. 매번 마음을 다잡고도 1~2주 있다가 헤이해지기 마련이죠.

여러번 실패하고, 방법을 찾아보다가 제가 정착한 방법을 공유드립니다.

저는 '챌린저스'라는 앱을 사용하면서 재미있게 루틴을 지키고 있습니다!
이 앱에서는 제가 유지하고 싶은 습관을 고르고 참가금을 걸어요. 그리고 정해진 기간 동안 100% 달성하면, 미션에 실패한 사람들의 참가금을 상금으로 받을 수 있어요. 💸 동기부여가 확실하죠?

하지만 반대로 85% 미만으로 달성하면 참가금의 일부를 환급받지 못하게 되니, 손해를 보지 않기 위해서라도 열심히 미션을 수행하게 되더라고요! 😅

무엇보다 좋은 습관을 지키면서도 초소액이지만 수익을 얻을 수 있단 점에서 일석이조입니다!

루틴을 지키는 게 힘들고 지루하게 느껴진다면, 이런 방법으로 재미있게 도전해보세요!

관심이 있으신 분들은 아래 링크 봐보세요!

지금 친구의 링크로 가입하면 챌린지 인증패스(인증 실패 만회권)와 만보기 포인트를 최대 10배까지 추가 적립받을 수 있는 부스팅 티켓을 받아요!

가입 시 추천인 닉네임란에 [gumbee]을 꼭 입력해주세요.

● 챌린저스 시작하기 ●

https://chlngers.onelink.me/Ju7U/rbbk5wcf?af_web_dp=https://web.chlngers.com



감기 때문에 목소리를 내기 힘든 저녁, 아이가 자꾸 잠에 들지 않고 재밌는 이야기를 해달라고 보챕니다.

예전에는 챗GPT를 이용해서 아이가 원하는 요소들을 넣어 이야기를 생성하고, 제가 직접 읽어줬었던 것이 생각나서 혹시나..하는 생각에 Voice 기능을 켜고 '방구공주의 모험' 이야기를 들려 달라 했습니다.

몇 가지 손 볼 점들이 있었지만, 아이는 재미나하면서 침대에 누워 30분 넘게 새로운 에피소드를 듣다 꿈나라로 향했습니다~


AI 도구의 발전은 여러 분야에서 효율성을 크게 향상시켰습니다. 순기능도 많지만 역기능도 있는데, 저는 그 중 하나가 인간의 가장 중요한 기술 중 하나인 "글쓰기"능력의 저하일거라 생각합니다. 사람들이 ChatGPT와 같은 도구에 지나치게 의존하면, 글쓰기 능력이 저하될 수 있다란 뜻입니다.

최근에 해외 재학중인 대학생인데, 2년간 과제를 모두 ChatGPT를 통해 진행하다가 3학년이 되어 논문을 준비해야 해서 부랴부랴 뒤늦게 영어 작문 과외를 받는다는 학생을 본 적이 있습니다. 제 와이프가 가르치게 된 학생인데, 이를 보면 AI 활용이 더 활발해질 5년, 10년 후에는 이런 학생이 더 많아질거란 생각과 함께 와이프의 고객저변은 쭉 확대가 되지 않을까 싶습니다 😉

반면, '직접 모든 단어, 문장을 작성하는 능력'이 글쓰기 능력이라 정의하는 것이 시대착오적인 것은 아닐까 싶기도 합니다. 글쓰기는 단순히 문장을 생성하는 것이 아니라, 논리적 사고와 비판적 분석 과정을 포함하는 활동입니다.
AI 도구가 쉽게 초안을 작성해주고, 그 결과물을 비판적으로 읽고, 분석하며, 수정하여 좋은 글이랑 결과를 낼 능력이 있다면 글쓰기 능력이 충분하다 볼 수 있지 않을까 싶습니다. 이는 개발 과정에서 코파일럿을 활용하더라도 코드 리뷰를 통해 수정하고 개선할 수 있는 능력이 있으면 된다고 여기는 것과 유사합니다.

그렇다면 AI 도구를 적절하게 활용하면서도 개인의 사고와 기술 개발을 촉진하는 균형 잡힌 접근 방식이 중요해질것 같습니다.이러한 측면은 앞으로의 교육에서 점점 더 강조되어야 할 것입니다.

저는 이렇게 글쓰기 교육을 하면 될거라 생각합니다.
1. 주제에 대해 비판적으로 읽고 사고하기  
2. AI 프롬프트를 사용하여 초기 콘텐츠 생성하기  
3. AI가 생성한 텍스트 평가하기  
4. 스스로 또는 AI를 사용하여 원본 내용을 수정하고 개선하기  
5. 필요에 따라 반복하기  

핵심은 글에 대한 비판적 사고와, 수정 능력을 개발하는 데 중점을 두는 것입니다. 사실 백지장 위에 한 글자 한 글자 채우는게 마냥 쉽지 않은데, 이 방법을 통해서 많은 사람들이 글쓰기에 대한 두려움도 극복하고, 또 다양한 글쓰기 스타일을 접하는 데 도움이 될 거라 생각합니다.

AI가 사람과 대화하고 감정을 이해하는 시대가 다가오고 있는듯 합니다. 이는 많은 이들에게 두려움의 대상이지만, 저는 이 기술이 가진 잠재력에 주목하고 싶습니다.

왜일까요? 바로 사회적 소외계층을 위해서입니다.

노환, 질병, 장애 등으로 인해 사회와 단절된 분들이 많습니다. 이분들도 대화와 정서적 교류에 대한 욕구가 있지만, 현실적으로 이를 충족시키기 어렵습니다.

AI의 장점:
• 지치지 않는 인내심
• 반복에도 변함없는 대응
• 편견 없는 소통 가능
• 시간&장소 제약 없이 대응 가능

이러한 AI의 특성은 소셜케어 분야에 혁명을 일으킬 수 있다 생각합니다. 소외된 이들에게 끊임없는 관심과 지지를 제공할 수 있기 때문입니다.

물론 AI가 인간의 touch를 완전히 대체할 순 없겠지만, 보완재로서 큰 역할을 할 수 있을 것입니다.

한편으로는 사람이 필요한 자리를 기계로 대체한다는 아이디어가 꺼림칙하긴 합니다. 근본적인 불쾌한골짜기와 같은 사유로 거부감이 들 수도 있을거라 생각합니다.
하지만 그걸 알면서도 따뜻한 손길을 충분히 보내지 못하는 현황을 방치하고 두는것보단 기계의 도움이라도 받는게 낫겠다는 생각입니다


**AI 도구의 발전은 많은 분야에서 생산성과 효율성을 크게 향상시켰습니다. 하지만, 이러한 기술을 무분별하게 사용하는 것은 필수적인 능력을 저하시킬 위험이 있습니다. 이 게시물에서 강조된 사례는 그 중 하나의 예입니다.**

**저는 이 문제가 인간에게 가장 중요한 능력 중 하나인 '글쓰기'에도 적용된다고 생각합니다. 사람들이 ChatGPT와 같은 도구에 지나치게 의존하면, 글쓰기 능력이 저하될 수 있습니다. 글쓰기는 단순히 문장을 생성하는 것이 아니라, 논리적 사고와 비판적 분석 과정을 포함합니다.**

**AI 도구가 결과물을 쉽게 생성할 수 있더라도, 그 결과물을 비판적으로 읽고 분석하며 수정할 수 있는 능력은 점점 더 중요해지고 있습니다. 이는 개발에서 코드 리뷰의 중요성과 유사하며, 개선하고 발전시키는 능력이 핵심입니다. AI 도구를 적절히 활용하면서도 개인의 사고력과 능력을 발전시키는 균형 잡힌 접근이 필요합니다. 이러한 측면은 앞으로의 교육과 훈련에서 더욱 강조되어야 합니다.**

**AI는 단지 도구일 뿐, 사고하고 판단하는 책임은 여전히 인간에게 있습니다.**.

문제출처

https://leetcode.com/problems/valid-anagram/description/

문제

Given two strings s and t, return true if t is an anagram of s, and false otherwise.  
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.  

Example 1:  
Input: s = "anagram", t = "nagaram"  
Output: true  

Example 2:  
Input: s = "rat", t = "car"  
Output: false  

Constraints:  
1 <= s.length, t.length <= 5 \* 104  
s and t consist of lowercase English letters.  

Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Anagram은 하나의 단어를 철자 순서를 바꿔 다른 단어로 바꾸는 것이다.
한글로 친다면 고무 - 무고 이 두 단어가 anagram이다.

풀이

#1 Sorting - O(n log n)

첫번째 방식은 Sorting을 이용하는 것이다.
s와 t가 결국 같은 철자 & 개수로 이루어지면 True를 반환한다란 점을 활용한다.
코드는 간단하지만, time complexity가 O(nlogn)이란 단점이 있다.

  1. s와 t를 sorting한다
  2. s(sort) == t(sort) 의 값을 return한다.
def isAnagram(s: str, t: str) -> bool: 
    return sorted(s) == sorted(t)

#2 Hashmap - O(n)

이번엔 Hashmap을 이용해 time complexity를 nlogn을 n으로 줄여보자.

  1. Hashmap을 만들어 놓고, s의 각 알파벳의 종류 / 개수를 업데이트한다.
  2. t의 알파벳 종류 / 개수를 hashmap으로 부터 제거한다.
  3. hashmap이 0이 아닐 경우 (다른 알파벳이 있거나 알파벳 개수가 달랐단 뜻이니) False를 반환한다.
def isAnagram(s: str, t: str) -> bool:
    count = {}
    for i in s:
        count[i] += 1
    for i int:
        count[i] -= 1

    for val in count.values():
        if val != 0:
            return False
    return True

#3 Hashmap, using Counter - O(n)

Python에 내장된 Counter이란 기능이 있다.
Hashable object counting하는데 특화된 딕셔너리이다.
한 줄로 끝나서 for문을 사용하는 것보다 간단하고, time complexity도 동일하다.
다만 #2 번 솔루션은 n이 길 경우, iterate 하는 도중에 맞지 않은 값이 나오면 빨리 False를 return할 수 있단 점이 장점이 될 수도 있다.

def isAnagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

Follow up :

What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

위 솔루션 모두 unicode와 ASCII 상관없이 동일하게 동작한다.
따라서 코드를 수정할 필요는 없으다.

하지만 "é" 같이 accent가 붙은 알파벳을 "e"로 표현하고 싶다면 Normalize를 고려할 수 있다.

import unicodedata
from collections import Counter

def isAnagram(s: str, t: str) -> bool:
# Normalize the strings to NFC
    s = unicodedata.normalize('NFC', s)
    t = unicodedata.normalize('NFC', t)
    return Counter(s) == Counter(t)

1. Facts (사실)

  • 이번 주에 어떤 일이 있었나요?
    • 후쿠오카 여행계획에 집중한 한 주였음
      • 와이프와 여행계획 및 예산 관련해서 많은 얘기를 나누었고, 갈등도 있었지만, 결국 타협점을 찾음
    • 가족 여행을 계획하는 데 시간과 노력을 기울인 대신, 여타 스터디에 많이 소홀해졌음
      • GCC 스터디 스킵, Kaggle 스터디 스킵, SQL는 절반정도면 풀어고, DS Python 스터디는 미션을 진행X
    • 업무적으로는 나름 재미를 찾음
      • Omega 발주를 할지에 대한 의사결정을 내리는 과정에서, 데이터 분석을 하며 체계적으로 논리의 흐름을 만들고, 숫자 이면의 숫자를 찾아 의사결정을 내렸을 때, 재미있고 보람이 느껴졌음.
      • FabriX 이용 권한을 받고, 그래도 삼성 그룹에서 일하는 덕을 보겠다란 생각을 해봄. 다만, 이를 업무에 어떻게 적용할지 좀 더 고민을 하지 않으면, 의미가 없을것이라 느낌
    • ACT GPT 동호회 활동 진행 : Make로 youtube 자막을 크롤링해와서, GPT api로 요약하여 Discord로 메시지를 남기는 자동화 프로세스를 만들어 보았음
    • 2주간의 챌린저스 루틴이 종료됨
      • 여행계획 짜고 동호회 활동 준비하느라 하루 밤샘한 탓에 생체리듬이 망가져서 몇몇 챌린지를 100% 완수 못한 것이 안타까움

2. Feelings (감정)

  • 이번 주에 어떤 감정을 느꼈나요?
    • 긍정적 감정 (기쁨, 성취감, 자신감 등)
      • 오메가 발주 필요 여부 분석해서 성취감을 느꼈고, FabriX를 접하며 재미를 느낌.
      • DS Python 스터디의 월요일 코치 라이브에서 박조은 코치님의 얘기를 들으며 열정을 느끼고 본받고 싶다, 더 많은 교류를 하고 싶다 생각함
      • 뉴스레터를 발행하는 Josh님의 링크드인 포스트를 보며 많은 영감을 받음
    • 부정적 감정 (스트레스, 불안, 좌절 등)
      • 하루 루틴 깨진 것으로 챌린져스의 몇 가지 챌린지에서 100% 달성을 실패해서 상금을 놓치게 되어 많은 아쉬움을 느낌
      • 여행계획을 하고, 매일 가계부를 쓰며, 줄어들지 않는 지출에 대해서 크나큰 스트레스를 느낌
      • 여러 스터디를 스킵하고, 계획했던 학습을 제대로 하지 못한 스스로에 대한 한심함을 느낌

3. Findings (발견)

  • 어떤 통찰이나 교훈을 얻었나요?
    • 회사가 아무리 어렵고 안좋은 환경이라 하더라도, 결국 내 마음가짐에 따라 내가 얻어가는 것은 다르단 것을 다시금 깨달음
    • 회사 상황이 안좋음은, 문제해결점이 많다는 것이고, 곧 내 포트폴리오를 만들기 적합한 환경이란 것을 다시금 상기함

4. Future (미래)

  • 다음 주에 달성하고자 하는 목표는 무엇인가요?
    • 루틴 회복하기 (스터디, 운동)
    • 여전히 안하고 있는 시간표 짜기 & Tell me about yourself 꼭 완수하기
  • 이번 주의 교훈을 바탕으로 다음 주에 어떻게 개선할 수 있을까요?
    • 게임 앱을 삭제한다
    • 규칙적인 생활을 한다 (놀 때, 집중할 때, 잘 때를 정해서 지킨다)
    • 집중력을 기르기 위해 타이머 같은 것을 세팅해보자.

5. Feedback (피드백)

  • 스스로에게 주고 싶은 피드백은 무엇인가요?
    • 자신에게 칭찬할 점
      • 반성하는 모습은 칭찬할만하고, 포기하지 않고 생각을 멈추지 않는 점도 칭찬할만하다.
    • 개선이 필요한 점
      • 여러번 reflection에 작성했던 부분 (시간표 짜기, tell me about yourself 작성하기)를 아직도 실천하지 않았다. 꼭 실천하자.
      • 부족한 집중력을 개선하자

'검비의 회고 > 주간 검비' 카테고리의 다른 글

주간 검비 : 24.08-W1  (0) 2024.08.11
주간 검비 : 24.07-W5  (0) 2024.08.05

행렬 곱셈(Matrix Multiplication)은 컴퓨터 과학에서 매우 중요한 연산 중 하나입니다. 일반적인 행렬 곱셈 알고리즘은 (O(n^3))의 시간복잡성을 가지지만, Strassen's Algorithm은 이를 개선하여 시간복잡성을 (O(n^{2.81}))로 줄인 알고리즘입니다. 이번 글에서는 Strassen's 알고리즘이 어떻게 작동하는지, 그리고 그 작동 원리를 이해하기 쉽게 설명하겠습니다.

일반적인 행렬 곱셈

행렬 곱셈의 기본 원리를 먼저 이해해 봅시다. 두 (n \times n) 행렬 (A)와 (B)를 곱하는 경우, 결과는 또 다른 (n \times n) 행렬 (C)가 됩니다. 각 (C[i][j]) 원소는 (A)의 i번째 행과 (B)의 j번째 열의 곱의 합으로 계산됩니다.

def matrix_multiply(A, B):
    n = len(A)
    C = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]

    return C

이 알고리즘은 (O(n^3))의 시간복잡성을 가지며, 큰 행렬에 대해서는 매우 많은 계산이 필요합니다.

Strassen's Algorithm이란?

Strassen's Algorithm은 1969년에 Volker Strassen이 개발한 행렬 곱셈 알고리즘으로, 행렬 곱셈을 더 적은 계산으로 처리할 수 있는 방법을 제안했습니다. 이를 통해 시간복잡성을 (O(n^{2.81}))로 줄일 수 있습니다.

기본 개념

Strassen's Algorithm은 행렬을 단순히 나누고 정교하게 결합하여 곱셈 연산을 줄이는 방식을 사용합니다. 두 (n \times n) 행렬 (A)와 (B)를 곱할 때, 행렬을 4개의 작은 부분 행렬로 나누어 작업합니다.

즉, (A)와 (B)를 다음과 같이 분할합니다:

[
A = \begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix}, \quad B = \begin{pmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \end{pmatrix}
]

여기서 (A_{11}, A_{12}, A_{21}, A_{22})는 각각 (n/2 \times n/2) 크기의 부분 행렬입니다.

일반적인 행렬 곱셈에서는 8개의 행렬 곱셈이 필요합니다. 하지만 Strassen의 알고리즘은 7개의 곱셈만으로 결과를 얻을 수 있습니다.

Strassen's Algorithm 단계

  1. 7개의 곱셈 계산:
    [
    M_1 = (A_{11} + A_{22}) \times (B_{11} + B_{22})
    ]
    [
    M_2 = (A_{21} + A_{22}) \times B_{11}
    ]
    [
    M_3 = A_{11} \times (B_{12} - B_{22})
    ]
    [
    M_4 = A_{22} \times (B_{21} - B_{11})
    ]
    [
    M_5 = (A_{11} + A_{12}) \times B_{22}
    ]
    [
    M_6 = (A_{21} - A_{11}) \times (B_{11} + B_{12})
    ]
    [
    M_7 = (A_{12} - A_{22}) \times (B_{21} + B_{22})
    ]

  2. 결과 행렬 계산:
    [
    C_{11} = M_1 + M_4 - M_5 + M_7
    ]
    [
    C_{12} = M_3 + M_5
    ]
    [
    C_{21} = M_2 + M_4
    ]
    [
    C_{22} = M_1 - M_2 + M_3 + M_6
    ]

    최종적으로 행렬 (C)는 다음과 같이 구성됩니다:
    [
    C = \begin{pmatrix} C_{11} & C_{12} \ C_{21} & C_{22} \end{pmatrix}
    ]

Strassen's Algorithm의 구현

def add_matrix(A, B):
    n = len(A)
    C = [[A[i][j] + B[i][j] for j in range(n)] for i in range(n)]
    return C

def subtract_matrix(A, B):
    n = len(A)
    C = [[A[i][j] - B[i][j] for j in range(n)] for i in range(n)]
    return C

def strassen(A, B):
    n = len(A)

    if n == 1:
        return [[A[0][0] * B[0][0]]]

    mid = n // 2

    A11 = [row[:mid] for row in A[:mid]]
    A12 = [row[mid:] for row in A[:mid]]
    A21 = [row[:mid] for row in A[mid:]]
    A22 = [row[mid:] for row in A[mid:]]

    B11 = [row[:mid] for row in B[:mid]]
    B12 = [row[mid:] for row in B[:mid]]
    B21 = [row[:mid] for row in B[mid:]]
    B22 = [row[mid:] for row in B[mid:]]

    M1 = strassen(add_matrix(A11, A22), add_matrix(B11, B22))
    M2 = strassen(add_matrix(A21, A22), B11)
    M3 = strassen(A11, subtract_matrix(B12, B22))
    M4 = strassen(A22, subtract_matrix(B21, B11))
    M5 = strassen(add_matrix(A11, A12), B22)
    M6 = strassen(subtract_matrix(A21, A11), add_matrix(B11, B12))
    M7 = strassen(subtract_matrix(A12, A22), add_matrix(B21, B22))

    C11 = add_matrix(subtract_matrix(add_matrix(M1, M4), M5), M7)
    C12 = add_matrix(M3, M5)
    C21 = add_matrix(M2, M4)
    C22 = add_matrix(subtract_matrix(add_matrix(M1, M3), M2), M6)

    C = []
    for i in range(mid):
        C.append(C11[i] + C12[i])
    for i in range(mid):
        C.append(C21[i] + C22[i])

    return C

Strassen's Algorithm의 장단점

장점

  • 시간복잡성 개선: 일반적인 행렬 곱셈 알고리즘의 (O(n^3))보다 더 빠른 (O(n^{2.81}))의 시간복잡성을 가집니다.
  • 큰 행렬에 유리: 매우 큰 행렬에 대해서는 상당한 성능 향상을 기대할 수 있습니다.

단점

  • 복잡한 구현: 일반적인 행렬 곱셈 알고리즘보다 구현이 복잡합니다.
  • 메모리 사용량 증가: 행렬을 반복적으로 분할하고 계산하기 때문에 추가적인 메모리가 필요합니다.
  • 작은 행렬에는 비효율적: 작은 행렬에서는 오히려 일반적인 행렬 곱셈이 더 효율적일 수 있습니다.

결론

Strassen's Algorithm은 행렬 곱셈에서 시간복잡성을 줄일 수 있는 중요한 기법입니다. 큰 행렬에 대해서는 상당한 성능 향상을 제공할 수 있지만, 복잡한 구현과 메모리 사용량 증가 등의 단점도 존재합니다. 따라서 특정 상황에서 적절하게 활용하는 것이 중요합니다.

Counting Inversion이란?

Counting Inversion은 배열 내에서 순서가 뒤바뀐 쌍의 개수를 세는 알고리즘입니다. 두 원소의 순서가 원래의 순서와 반대일 때, 이를 'inversion'이라고 부릅니다.

쉬운 예시

예를 들어, 배열 [2, 4, 1, 3, 5]를 봅시다:

  • (2, 1)은 inversion입니다. 2가 1보다 앞에 있기 때문입니다.
  • (4, 1)과 (4, 3)도 inversion입니다.

따라서 이 배열의 총 inversion 개수는 3입니다.

알고리즘 구현

Counting Inversion을 구현하는 효율적인 방법 중 하나는 merge sort 알고리즘을 변형하여 사용하는 것입니다. 이 방법을 통해 O(n log n)의 시간 복잡도로 문제를 해결할 수 있습니다.

파이썬 코드

다음은 merge sort를 이용한 counting inversion의 파이썬 구현입니다:

def merge_and_count(left, right):
    result = []
    count = 0
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += len(left) - i
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result, count

def sort_and_count(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left, left_count = sort_and_count(arr[:mid])
    right, right_count = sort_and_count(arr[mid:])
    merged, merge_count = merge_and_count(left, right)
    return merged, left_count + right_count + merge_count

def count_inversions(arr):
    _, count = sort_and_count(arr)
    return count

코드 설명

  1. merge_and_count 함수:
    • 두 정렬된 배열을 병합하면서 inversion을 세는 함수입니다.
    • 오른쪽 배열의 원소가 왼쪽 배열의 원소보다 작을 때마다 inversion을 세줍니다.
  2. sort_and_count 함수:
    • 배열을 재귀적으로 분할하고 병합하면서 inversion을 세는 함수입니다.
    • 분할 정복(divide and conquer) 방식을 사용합니다.
  3. count_inversions 함수:
    • 주어진 배열의 총 inversion 개수를 반환하는 메인 함수입니다.

사용 예시

arr = [2, 4, 1, 3, 5]
inversions = count_inversions(arr)
print(f"배열 {arr}의 inversion 개수: {inversions}")

이 코드를 실행하면 다음과 같은 결과가 출력됩니다:

배열 [2, 4, 1, 3, 5]의 inversion 개수: 3

결론

Counting Inversion 알고리즘은 데이터의 정렬 상태를 분석하는 데 유용합니다. 이 알고리즘은 merge sort의 아이디어를 활용하여 효율적으로 구현할 수 있으며, 데이터 분석, 정렬 알고리즘의 성능 평가 등 다양한 분야에서 활용될 수 있습니다.

+ Recent posts