오늘 다룬 문제는 단순한 '순서 바꾸기'처럼 보이지만, 그 이면에는 데이터 검색 속도와 성능 최적화라는 알고리즘의 핵심 과제가 숨어 있습니다. 대규모 서비스 환경에서 특정 사용자의 상태를 업데이트할 때마다 전체 명단을 처음부터 끝까지 뒤져야 한다면 어떻게 될까요? 데이터가 100만 개라면, 단 한 번의 업데이트를 위해 100만 번의 연산이 필요해집니다.

오늘은 리스트의 물리적 순서를 유지하면서도, 검색 성능을 $O(1)$로 끌어올리는 해시 테이블(Hash Table) 기반의 딕셔너리 활용법을 정리해 보았습니다.

🔍 The Challenge (Deep Dive): 리스트 순회, 무엇이 병목(Bottleneck)인가?

처음 문제를 접했을 때 가장 직관적인 접근은 for문을 돌려 타겟을 찾는 방식이었습니다. 하지만 여기서 두 가지 기술적 병목을 마주했습니다.

1. 데이터 유실의 위험: 단순 대입(=)은 추월을 구현하는 것이 아니라 기존 데이터를 '덮어쓰기' 때문에 선수의 정보가 유실됩니다. 즉, 데이터의 정합성을 지키기 위한 Swap(교환) 로직이 필수적이었습니다.
2. 선형 탐색(Linear Search)의 한계: answer[i] == c를 찾기 위해 매번 리스트 전체를 순회하는 이중 반복문 구조는 시간 복잡도 $O(N \times M)$을 유발합니다. $N$(선수 수)이 5만, $M$(호출 수)이 10만일 경우 연산 횟수는 최대 50억 번에 달하며, 이는 반드시 시간 초과(Time Limit Exceeded)로 이어집니다.

💡 Technical Insight: 자료구조의 트레이드 오프(Trade-off)

이 병목을 해결하기 위해 파이썬의 dict 자료구조를 도입했습니다. 파이썬의 딕셔너리는 내부적으로 해시 테이블로 구현되어 있어, Key를 통해 Value를 찾는 과정이 평균적으로 $O(1)$에 수행됩니다.

내가 지금 손에 든 정보(선수 이름)로 무엇(인덱스)을 찾고 싶은지를 고민하여 {Name: Index} 형태의 '역색인' 구조를 설계했습니다.

📊 자료구조 비교: List vs Dict (Hash Map)

단, 딕셔너리만으로는 최종 정답인 '선수들의 순서'를 즉각 반환하기 어렵기 때문에, 순서를 담당하는 리스트와 검색을 담당하는 딕셔너리를 동시에 업데이트하는 '이중 장부' 전략을 선택했습니다.

✅ The Solution & Code

최종 구현 코드

def solution(players, callings):
    # 1. '이름: 등수' 형태의 해시 맵(rank_dict) 초기화 (O(N))
    # 이름표(Key)를 주면 등수(Value)를 광속으로 찾아주는 '거꾸로 사전'
    rank_dict = {player: i for i, player in enumerate(players)}

    for c in callings:
        # 2. 호명된 선수의 현재 인덱스를 해시 맵에서 O(1)로 조회
        i = rank_dict[c]

        # 3. Swap을 위해 앞 순서 선수(Target) 식별
        # 자리를 바꾼 뒤에도 장부를 수정해야 하므로 이름을 미리 메모해둠(front_player)
        front_player = players[i - 1]

        # 4. List 데이터 업데이트: 실제 물리적 위치 교체 (O(1))
        # 파이썬의 튜플 언패킹을 활용한 우아한 Swap
        players[i - 1], players[i] = players[i], players[i - 1]

        # 5. Dict 데이터 업데이트: 해시 맵 내 인덱스 정보 동기화
        # 내 인덱스는 줄이고, 밀려난 앞 선수의 인덱스는 늘려줌
        rank_dict[c] -= 1
        rank_dict[front_player] += 1

    return players

📈 Summary

• 시간 복잡도: 딕셔너리 초기화($O(N)$) + 호출 순회($O(M)$) = $O(N + M)$. 최악의 상황에서도 약 15만 번의 연산으로 해결 가능합니다.
• 공간 복잡도: 리스트 외에 별도의 딕셔너리를 사용하므로 $O(N)$의 추가 공간이 필요하지만, 성능 최적화를 위한 합리적인 비용(Trade-off)입니다.

본 내용은 웹 기준으로 작성되었습니다. 앱의 경우 gtag.js가 아닌 firebase로 해주세요.

Google Analytics 접속

1. Google Analytics 페이지에 접속해 줍니다.

2. 시작 a. 처음 시작이라면 측정 시작을 눌러주세요. b. 이미 만들어 두었다면 오른쪽 상단 네모 버튼을 눌러 애널리틱스를 클릭해 주세요.

필요한 매개변수 찾기

측정 프로토콜 참조  |  Google 애널리틱스  |  Google for Developers

1. 생성한 애널리틱스로 들어가 왼쪽 메뉴바에서 관리로 들어가줍니다.

2. 속성 설정 → 데이터 수집 및 수정 → 데이터 스트림 선택

3. 해당하는 플랫폼을 선택해 주세요.

4. 웹사이트 URL과 스트림 이름을 작성한 뒤 하단에 스트림 만들기 클릭

5. 측정 ID 복사 후 메모장에 붙여넣어 주세요. a. 측정 ID가 measurement_id가 됩니다.

6. 스크롤을 내린 후 측정 프로토콜 API 비밀번호를 클릭해주세요.

7. 비밀번호 값 을 복사 후 메모장에 붙여넣어주세요. a. 비밀번호 값이 ap_secret이 됩니다.

Postman으로 테스트 하기

1. Postman method를 Post로 지정해줍니다.

2. URL에 https://www.google-analytics.com/mp/collect 을 넣어줍니다.

3. body → raw → JSON 선택 아래와 같이 원하는 키와 값을 넣어줍니다. a. 측정 프로토콜 참조  |  Google 애널리틱스  |  Google for Developers 참조

4. 보고서 → 실시간으로 들어가 주세요. a. 실시간이 아니면 내역이 바로뜨지 않습니다. b. 실시간 또한 약 10~30초 정도 딜레이가 있습니다.

5. 실시간에서 여러 요소 중 이벤트를 확인할 수 있습니다.

연동 안될 경우 해결법

Postman에서 204가 떴는데 실시간에 아무런 변화가 없을 경우

• Postman에서 204가 뜨는건 정상이지만 아무런 변화가 없을 경우 Params의 값들을 다시 확인해 주세요.
• Postman의 URL 주소를 https://www.google-analytics.com/debug/mp/collect 로 바꿔주세요. 에러 내용을 확인할 수 있습니다.

Params의 값에 아무런 문제가 없고, 204만 뜰 경우

1. Event Builder에 접속해 주세요. ga-dev-tools.google

2. client를 gtag.js로 해주세요.

3. 위쪽 빨간칸에 해당하는 내용을 작성해 주세요.
   1. 아래 칸은 자동으로 맞춰 채워집니다.
   2. client_id는 임의의 값을 입력해도 괜찮습니다.
   3. *표시가 없다면 입력하지 않아도괜찮습니다.

4. event_name을 정해주세요.

5. 스크롤을 아래로 내려 VALIDATE EVENT 버튼을 클릭해 주세요.

6. 유효하지 않다면 다음과 같이 메세지를 줍니다.

7. 값이 유효하다면 다음과 같이 뜨고,** SEND TO GA**를 클릭하면 Postman과 같이 값이 전달 됩니다.

8. COPY PAYLOAD를 클릭하면 Body를 JSON 형태로 보여주며, Postman에 붙여 넣을 수 있습니다.

FFmpeg은 멀티미디어 분야에서 가장 많이 사용되는 오픈소스 광범위한 멀티미디어 데이터를 다루는 데 사용되는 강력한 오픈 소스 소프트웨어 비디오, 오디오, 이미지 파일 등 다양한 형식의 멀티미디어 파일을 처리, 변환, 스트리밍하는 데 사용 Michael Niedermayer의 주도하여 개발되고 있다.

디코더

• 동영상을 재생할때 쓰이는 코덱

FFmpeg 기반 동영상 플레이어

• iOS: AV player, nPlayer
• 안드로이드: Dice Player, MX 플레이어, 안드로이드용 곰플레이어, 안드로이드용 KMPlayer
• Microsoft Windows: 팟플레이어, 곰플레이어, KMPlayer, MPC-HC, 콘플레이어
• macOS: 무비스트, IINA
• 크로스 플랫폼: VLC, MPlayer

외에 더 많은 플레이어들이 있다.

FFmpeg 기반 코덱

• LAVFilters
• FFDshow

외에 LAVFilters, FFDshow를 기반으로 한 코덱들

인코더

동영상 편집 프로그램에서 최종 결과물을 내보낼때 거치는 도구

FFmpeg 기반 인코더

• 제트오디오VX(무료 혹은 유료, 코원)
• 유마일
• 엔젤인코더
• 샤나인코더
• Freemake - 서양에서 유명한 인코딩 프로그램. 그러나 랜섬웨어 유포 위험이 있다.
• Mencoder
• 곰인코더
• 다음팟인코더
• Handbrake - 세계에서 가장 많이 쓰이는 인코더
• WInff - FFmpeg를 GUI로 만든 프로그램

FFmpeg 기능

• 변환(Transcoding): FFmpeg는 한 형식의 비디오나 오디오 파일을 다른 형식으로 변환할 수 있다. 예를 들어, AVI 파일을 MP4로 변환하거나 WAV 오디오 파일을 MP3로 변환하는 것이 가능

• 스트리밍(Streaming): FFmpeg를 사용하여 라이브 비디오와 오디오 스트림을 인코딩하고, 인터넷을 통해 방송할 수 있다.

• 비디오 편집(Video Editing): FFmpeg는 기본적인 비디오 편집 기능을 제공 예를 들어, 비디오를 자르거나, 여러 클립을 합치거나, 비디오에서 오디오를 분리하는 것이 가능

• 오디오 편집(Audio Editing): 오디오 파일의 볼륨 조절, 샘플레이트 변경, 채널 조정 등 기본적인 오디오 편집 기능

• 비디오 필터(Video Filters): 다양한 비디오 필터를 사용하여 비디오의 모습을 변경할 수 있습니다. 예를 들어, 컬러 조정, 이미지 오버레이, 텍스트 추가 등이 있다.

• 오디오 필터(Audio Filters): 오디오에 대한 다양한 필터링 기능을 제공하여 소리를 변경하거나 개선할 수 있다.

• 프레임 추출(Frame Extraction): 비디오에서 특정 프레임을 이미지 파일로 추출하는 기능 제공

• 메타데이터 관리(Metadata Handling): 멀티미디어 파일의 메타데이터를 조회하거나 수정할 수 있다.

• 코덱 정보 조회(Codec Information): 다양한 코덱과 포맷에 대한 정보를 조회할 수 있으며, FFmpeg는 많은 코덱을 지원

• 배치 처리(Batch Processing): 스크립트를 사용하여 대량의 파일을 자동으로 처리할 수 있다.

FFmpeg 설치

1. 홈페이지 들어가기 FFmpeg 공식 홈페이지

2. 다운로드 클릭

3. 윈도우 -> Windows builds from gyan.dev 클릭

4. ffmpeg-git 파일 중 원하는 것 클릭 essentials은 많이 사용되는 패키지만 포함되어 있다.

• 다운로드

5. 개발용은 Release 파일 사용

6. 원하는 경로에 압축을 해제해 줍니다.

실행 방법

두 가지의 경우가 있는데 편한 방법으로 사용하면 된다.

1. 해당 파일 경로로 실행
2. 환경 변수 설정

경로로 실행

1. ffmpeg bin 폴더로 이동

2. 경로 클릭

3. cmd 입력 후 엔터

4. 해당 경로에 cmd 창이 나옵니다.

5. cmd창에서 cd를 이용하여 경로설정도 가능

환경 변수 설정

1. 윈도우 검색 창에 '환경 변수' 검색

2. 시스템 속성에서 '환경 변수' 클릭

3. 시스템 변수 -> Path 선택 후 편집 클릭

4. 새로만들기 클릭 후 bin폴더 경로 입력 후 확인

5. 나머지 창들도 확인 눌러서 적용

설치 확인

cmd창에서 ffmpeg 입력 후 사진처럼 뜬다면 완료!

ShellExecute 함수는 Windows API로, Microsoft Windows 운영체제에서 외부 프로그램 또는 파일을 실행하는 데 사용되는 함수

• 함수는 주어진 파일을 실행하는 데 필요한 프로그램을 찾아서 실행하거나, 웹 페이지를 열고 특정 URL을 브라우저로 연결하는 데 사용된다.

ShellExecute 함수 원형

HINSTANCE ShellExecute(
  HWND hwnd,
  LPCTSTR lpOperation,
  LPCTSTR lpFile,
  LPCTSTR lpParameters,
  LPCTSTR lpDirectory,
  INT nShowCmd
);

ShellExecute의 주요 기능

파일 열기

• 사용자의 시스템에 연결된 기본 프로그램을 사용하여 파일을 연다.
• 예를 들어, PDF 파일을 열 경우 기본 PDF 뷰어가 실행된다.

  URL 열기

• 기본 웹 브라우저에서 URL을 연다.

  프로그램 실행

• 특정 프로그램을 실행한다.

  시스템 명령 수행

• 'explore', 'find', 'print'와 같은 명령을 수행하여 파일 탐색기를 열거나, 파일을 검색하거나, 문서를 인쇄할 수 있다.

ShellExecute Parameter

ShellExecute는 다양한 파라미터를 받을 수 있으며, 이 파라미터들은 함수의 동작 방식을 결정한다.

1. hwnd

• 실행된 프로그램의 부모 윈도우 핸들
• 인자를 사용하면 실행된 프로그램이 모달 대화 상자와 같은 모달 윈도우로 표시될 때 부모 윈도우를 지정할 수 있다.
• 일반적으로 NULL 값을 사용하거나 부모 윈도우의 핸들을 전달한다.
• 윈도우 핸들은 '0' 이다.

  2. lpOperation

• 실행할 작업을 나타내는 문자열
• 주요 작업으로 "open"이나 "print"을 사용한다.
• "open"은 파일을 실행하는 작업을 의미하고, "print"는 파일을 인쇄하는 작업을 의미 한다.
• NULL을 지정하면 파일의 기본 동작(대부분 "open")이 수행된다.

  3. lpFile

• 실행할 파일의 경로 또는 실행할 프로그램의 이름

  4. lpParameters

• 실행될(lpFile에 지정된) 프로그램에 전달할 추가 매개변수

  5. lpDirectory

• 실행될 프로그램의 기본 작업 디렉토리
• 실행될 프로그램의 작업 디렉토리를 지정할 수 있다.

  6. nShowCmd

• 실행될 프로그램의 창을 어떻게 표시할지를 지정하는 정수
• 주요 값으로 SW_SHOWNORMAL, SW_SHOWMAXIMIZED, SW_SHOWMINIMIZED 등이 있다.

ShellExecute 예시

Delphi

uses
  ShellAPI;

procedure TForm1.Button1Click(Sender: TObject);
begin
  ShellExecute(Handle, 'open', 'C:\example.txt', nil, nil, SW_SHOWNORMAL);
end;

C++

#include <windows.h>

int main() {
    ShellExecute(NULL, "open", "http://www.example.com", NULL, NULL, SW_SHOWNORMAL);
    return 0;
}

반환 값

• ShellExecute는 HINSTANCE를 반환한다.
• 값이 32보다 크면 성공, 그렇지 않으면 오류를 나타낸다.
• 오류 코드를 얻으려면 GetLastError 함수를 사용할 수 있습니다.

HINSTANCE

• HINSTANCE는 Windows 프로그래밍에서 사용되는 핸들 타입
• ShellExecute 함수에서 반환되는 HINSTANCE 값은 호출된 작업의 성공 여부 및 관련 정보를 나타내는 데 사용된다.

HINSTANCE의 의미

성공여부

ShellExecute가 성공적으로 수행되었다면, 반환되는 HINSTANCE 값은 32보다 크다. 이 경우, HINSTANCE는 실행된 프로그램이나 문서의 인스턴스 핸들을 의미합니다.

오류코드

• 만약 반환된 값이 32 이하라면, 이는 오류를 나타낸다.

HINSTANCE 사용 예제

Delphi

uses
  ShellAPI;

procedure OpenURL;
var
  H: HINST;
begin
  H := ShellExecute(0, 'open', 'http://www.example.com', nil, nil, SW_SHOWNORMAL);
  if H <= 32 then
    ShowMessage('Error opening URL');
end;

C++

#include <windows.h>
#include <shellapi.h>

int main() {
    HINSTANCE hInst = ShellExecute(NULL, "open", "http://www.example.com", NULL, NULL, SW_SHOWNORMAL);
    if ((int)hInst <= 32) {
        // 오류 처리
    }
    return 0;
}

ShellExecute 사용시 주의할 점

• ShellExecute를 사용할 때는 보안에 특별히 주의해야한다.
• 사용자로부터 입력받은 데이터를 이 함수에 직접 전달하는 경우, 악의적인 입력으로 인해 보안 취약점이 발생할 수 있다.
• 따라서, 사용자 입력을 사용하여 ShellExecute를 호출할 때는 해당 입력을 철저히 검증해야 합니다.

참조

애플리케이션 시작(ShellExecute, ShellExecuteEx, SHELLEXECUTEINFO)