gcc -o app app.c

• gcc : GNU C 컴파일러
• o app : 컴파일 결과 파일 이름을 app으로 지정
• app.c : 소스 파일 이름

Step 2. 컴파일된 실행 파일 실행

./app

컴파일된 파일 목록 보기

ls -l

컴파일 후 app이라는 실행 파일이 생긴 걸 확인할 수 있어야 합니다.

gcc 컴파일러 코드(여러 파일로 나눠서 작업한 경우)

gcc -c rbtree.c -o rbtree.o

gcc 컴파일러 코드(단일 파일인 경우)

gcc -o app app.c

전체 과정의 흐름 요약

make clean make test vi cd ls

vi ~/.vimrc (초반 세팅 파일)

aws 가상컴퓨터 접속하기.

```bash % ssh -i 키파일 ubuntu@퍼블릭 주소

void RecursiveReverse(ListNode **ptrHead) //ll.head를 가르키는 이중포인터변수를 받음
{
    /* add your code here */
    if ((*ptrHead)==NULL || (*ptrHead)->next==NULL) return; //헤드값이 없거나 연결리스트가 값이 없을 때 함수를 종료한다.
    ListNode *first=*ptrHead,*rest=first->next;//두가지 포인터변수 생성. ll.head값이 저장된 first, head 다음값인 rest.
    RecursiveReverse(&rest); // 재귀함수를 선언한다.위의 함수가 주소를 받는 이중포인터변수라 주소값을 넣음.
    first->next->next=first; //밀린 재귀들을 내려받으면서 노드의 순서를 바꿔준다. rest(5)->next=first(4) ,rest(4)->next=first(3)
    first->next=NULL;//first 이후의 노드의 연결을 끊어준다. 5->4->NULL 이렇게 만들어짐
    *ptrHead=rest; //rest는 마지막으로 4의 값이 재귀함수위에서 저장되었을때가 마지막이라 값은 5로 고정됨.
}

인자 전달 (최대 6개까지 레지스터로)

함수에 인자를 넘길 때는 아래 순서대로 레지스터를 사용해:

함수 리턴값은?

• 리턴값은 기본적으로 %rax에 저장
  • 예: return 42; → %rax = 42
• 리턴값이 128비트 이상이면 다른 레지스터 추가 사용 or 메모리 통한 복잡한 처리 필요

레지스터는 크게 두 종류

레지스터 버전별 비교 표

%rdi, %edi, %di, %dil을 쓰는 상황

전달할 값의 크기(자료형)에 따라 자동으로 결정됨.

확장(extension) 계열

• 작은 크기 → 큰 크기로 바꿀 때 사용
• 부호(sign)를 유지하느냐에 따라 구분됨

igned vs unsigned: 정수의 부호(+, -) 유무

x86-64 아키텍처 규칙

자료형 변환 방향에 따른 동작 요약

트라이란?

- 문자열을 효율적으로 처리하기 위한 트리 자료구조.

단어의 끝에 도달했는지를 확인하는것이 중요

단어 제거

해당위치까지 찾아간다음 단어의 끝을 의미하는 것을 제거
**정점 자체를 제거하면 안됨
- 이전에 삽입한 정점들은 계속 메모리에 남아있어 메모리 측면에서 비효율적임
- 그래서 삭제가 계속 발생하는 환경에서 트라이는 적합하지 않음

a=[1,2,3,4,5]
#a 리스트에서 4의 위치(인덱스 값)을 찾는 코드
a.index(4) # 3

리스트 slicer가 [값1, 값2, 값3] 형태일 때, 각 값을 순서대로 변수 a, b, c에 할당합니다.

slicer = [2, 5, 10]
a, b, c = slicer
print(a)  # 2
print(b)  # 5
print(c)  # 10

주의할 점

slicer의 길이가 반드시 3이어야 해요. 만약 [1, 2]처럼 2개만 있으면 에러 발생:

a, b, c = [1, 2]
# ValueError: not enough values to unpack (expected 3, got 2)

반대로 4개 이상이면?

a, b, c = [1, 2, 3, 4]
# ValueError: too many values to unpack (expected 3)

안전하게 언패킹하려면?

• 갯수가 다를 수 있다면 슬라이싱이나 별표(*) 연산자를 써서 처리 가능:

a, b, *rest = [1, 2, 3, 4, 5]
# a = 1, b = 2, rest = [3, 4, 5]

풀이 방법

자기 자신과의 거리는 0이므로 1번 인덱스의 값은 0이다.
인접한 정점 중 가장 가까운, 가중치가 작은 정점을 최단 거리 테이블에 넣어 확정시킨다.

우선순위 큐를 이용한 다익스트라 알고리즘!

1. 우선순위 큐에 (0, 시작점)을 추가.
2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우 넘어감.
3. 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가.
4. 우선순위 큐가 빌 때 까지 2, 3번 과정을 반복.

- 방향, 무방향 둘다 가능
- 간선값이 음수여도 동작. but 음수인 사이클이 있으면 문제 발생.
- 자기 자신으로 가는거리 = 0 , 간선 1개로 바로 건너갈 수 있는 곳 = 간선의 값

접근법
- 현재 테이블에서 1번을 거쳐가는 최단 거리만을 먼저 갱신
- 다른 모든 경우도 모두 계산. 최종적인 최단 거리까지 구현

시간복잡도
- O(V^3)

위상정렬 이란

올바른 위상정렬
- ABCDEF
- ACEDBF
- BADCEF
- BADFCE

올바르지 않은 위상정렬
- BFACED는 F가 D보다 먼저 나오기 때문에 잘못된 위상정렬이다.

자신보다 앞에 위치하는 정점이 없어야한다.
자신에게 들어오는 간선이 없어야한다.
indegree - 자신에게 들어오는 간선의 수

위상정렬 알고리즘

1.맨 처음 모든 간선을 읽으며 indegree 테이블을 채움
2.indegree가 0인 정점들을 모두 큐에 넣음
3.큐에서 정점을 꺼내어 위상 정렬 결과에 추가
4.해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킴 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가
5.큐가 빌 때 까지 3,4번 과정을 반복

위상정렬은 사이클이 존재하면 모순이 발생

A, B, C 중 어느것이 먼저 나오더라도(순서와 상관없이)
간선으로 주어진 정점 간 선후관계에 모순이 발생한다.
위상정렬은 사이클이 존재하지 않는 방향 그래프에서만 잘 정의된다.
DAG(Directed Acyclic Fraph) - 사이클이 존재하지 않는 방향그래프

1. 처음에 1을 큐에 넣고 방문했다는 표시 남김
2. 큐가 비어있지 않으니 큐의 front인 1번 정점을 꺼낸다
3. 1번 정점과 이웃한 2, 3, 4번 정점은 방문하지 않은 정점이라 큐에 순서대로 넣고 방문처리.
4. 큐가 비어있지 않으니 순서대로 큐의 front정점을 꺼냄
5. 2번은 주변에 방문하지 않은 정점이 없지만 3번은 방문하지 않은 정점 5번을 이웃하고 있어 5번을 큐에 넣고 방문했다는 표시 남김
6. 큐가 비어있을 때 까지 반복

if 연결그래프가 아닐때 BFS순회를 하려면?

for문을 돌면서 아직 방문하지 않은 정점을 찾아 그 정점을 시작정점으로 잡게 코드를 구현하면 된다.

가중치

모든 간선의 길이가 동일한 상황에서 두 지점 사이의 거리를 찾는 문제는 BFS로 처리 가능. BUT. 모든 간선의 길이가 다르다면 플로이드나 다익스트라와 같은 알고리즘 사용.

DFS(깊이 우선 탐색), (스택)

간단하다. BFS과정에서 큐를 스택으로만 변경하면 끝
재귀가 가능하다. 재귀적으로 함수를 호출하는 상황 = 가장 늦게 호출된 함수를 차례대로 처리. LIFO (스택) but, 재귀로 구현할 때 깊이가 깊어지면 문제가 생길 수 있다. 재귀로 처리하면 실제 방문을 할 때 방문표시를 남긴다. 비재귀적인 방식은 방문하기 전에 방문하지 않은 곳을 발견하면 그 때 방문 표시를 남긴다. 강조 비재귀 DFS는 순회를 잘 수행하지만 엄밀히 말해 우리가 관념적으로 생각하는 DFS와는 방문순서가 다르다.

try:
    실행할 코드
except 예외타입:
    예외 발생 시 실행할 코드

beakjoon 5639 코드에서의 역할

pre = []
while True:
    try:
        pre.append(int(sys.stdin.readline()))
    except:
        break

이 코드의 의미

• sys.stdin.readline()은 줄 단위로 입력을 받습니다.
• 입력이 끝나면(EOF: End Of File) int(...)에서 오류(Exception)가 발생합니다.
• 그때 except 블록으로 빠져서 while 루프를 멈추게 됩니다.

쓰이는 이유

입력 개수가 정해져 있지 않은 경우 (EOF 입력 방식)에는 try ~ except를 사용해서 입력이 끝나는 시점을 처리.

문자열.append()는 쓸 수 없음. 리스트.append()는 가능

문자열은

문자열 += 추가할 str

문자열뒤집기(슬라이싱)

a[i:j+1][::-1]

• start < end일 때: step은 양수여야 함 (왼쪽 → 오른쪽)
• start > end일 때: step은 음수여야 함 (오른쪽 → 왼쪽)
• 슬라이싱은 항상 start부터 end 전까지입니다

그런데 이걸 a[i:j+1:-1]로 쓰면?

a = ['a', 'b', 'c', 'd', 'e']
a[1:4][::-1]    # ✅ ['d', 'c', 'b']
a[1:4:-1]       # ❌ []  (결과 없음)

왜냐면 start=1, end=4, step=-1은 왼쪽부터 오른쪽 방향인데 역순(-1) 이라 조건 충돌이 생깁니다.

파이썬은 이런 경우 "읽을 수 있는 방향이 아예 없음"으로 보고 빈 리스트를 반환.

join()

''.join(리스트)

리스트를 하나의 문자열로 만들어준다. join은 문자열 리스트에만 사용

각 문자열 슬라이스로 이어붙이기

def solution(my_strings, parts):
    answer = ''
    for i in range(len(my_strings)):
        s, e = parts[i]
        answer += my_strings[i][s:e+1]
    return answer

• my_strings[i][s:e+1] → 끝 인덱스를 포함하기 위해 e+1
• answer에 차례대로 잘라붙임

리스트안에 값 확인하는 방법

if is_suffix in a:

a 리스트안에 is_suffix가 있으면 True

startswith 란?

str.startswith(prefix)

반환값

• 시작하면 True
• 아니면 False

  ex)
  s = "hello"
  s.startswith("he")     # True
  s.startswith("x")      # False

  (시작 위치 지정)
  "abcdef".startswith("c", 2)  # True

1. ord() 와 chr()

```python for i in range(26): chr(ord('A') + i) # A~Z 생성

• 객체(Object)를 생성하기 위한 틀(Template)
• 변수(속성)와 함수(메서드)를 묶어서 하나의 구조로 정의

class ClassName:
    def method(self):
        pass

생성자 __init__()

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

• init 함수는 클래스를 선언하는순간 실행이 된다.
• 객체가 생성될 때 실행됨
• __init__() 안의 self.name은 객체의 속성, name은 전달된 값

self

def set_name(self, name):
    self.name = name

• 메서드는 항상 self를 첫 번째 인자로 가짐
• self.name: 인스턴스 변수에 접근

상속과 super()

class Animal:
    def __init__(self, name):
        self.name = name

class Dog(Animal):
    def __init__(self, name, breed):
        super().__init__(name)  # 부모 생성자 호출
        self.breed = breed

• super()는 부모 클래스에 접근할 때 사용
• 중복 제거 및 유지보수 용이

클래스 예시 전체

class Animal:
    def __init__(self, name):
        self.name = name

    def speak(self):
        print(f"{self.name}가 소리를 냅니다")

class Dog(Animal):
    def __init__(self, name, breed):
        super().__init__(name)
        self.breed = breed

    def speak(self):
        print(f"{self.name}는 멍멍 짖어요 ({self.breed})")

dog1 = Dog("초코", "푸들")
dog1.speak()

출력 결과

초코는 멍멍 짖어요 (푸들)

핵심 요약

자주 나오는 문법 요약

사용법

count() – 특정 값만 세기

s = "banana"
s.count('a')     # 3

collections.Counter – 전체 빈도수 분석

from collections import Counter

s = "banana"
Counter(s)
# 출력: Counter({'a': 3, 'n': 2, 'b': 1})

리스트 예시

lst = [1, 2, 2, 3, 1, 1, 2]

# count()
lst.count(2)     # 3

# Counter
from collections import Counter
Counter(lst)
# 출력: Counter({1: 3, 2: 3, 3: 1})

주요 차이 요약

Counter 응용 팁

# 가장 많이 등장한 요소 n개 구하기
Counter("banana").most_common(1)
# 결과: [('a', 3)]

# 딕셔너리처럼 사용
c = Counter("banana")
c['a']     # 3
c['z']     # 0 (없는 값도 기본 0 반환)

핵심 요약

• count(): 특정 원소의 개수만 셀 때 간편하게 사용
• Counter: 모든 원소의 빈도수를 한 번에 분석할 때 유리
• 문자열, 리스트, 튜플 등 반복 가능한 자료형 모두 사용 가능

• 그래프에서 사이클이 생기는지 판단하는 방법
• 특히 MST 문제(최소 신장 트리) 에서 필수 개념
• 간선을 하나씩 추가할 때, 사이클을 유발하는지 실시간 판별해야 함

유니온 파인드 (Disjoint Set Union - DSU)

핵심 원리

• 두 정점이 같은 집합에 속해 있다면 → 사이클 발생
• 새로운 간선을 추가할 때마다 find()로 대표 노드 비교

구현 방식

# 기본적인 유니온 파인드 구조
parent = [i for i in range(n + 1)]

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]

def union(a, b):
    a_root = find(a)
    b_root = find(b)
    if a_root < b_root:
        parent[b_root] = a_root
    else:
        parent[a_root] = b_root

사이클 판별 코드

if find(a) == find(b):
    # 사이클 발생
    pass
else:
    union(a, b)

DFS/BFS로 사이클 판별

설명

• 현재 간선 (a, b) 를 추가하기 전에

  a에서 b로 이미 경로가 있는지 탐색 → 있다면 사이클

• 이론적으로 가능하지만, 실전에서는 비효율

방법 비교 요약

결론

• MST 문제에서는 무조건 유니온 파인드 사용
• DFS/BFS는 이론적으로만 가능하며 실전에서는 사용하지 않음
• 크루스칼 알고리즘 = 간선 정렬 + 유니온 파인드

참고: 프림 알고리즘의 사이클 처리

• Prim 알고리즘은 사이클을 체크하지 않음
• 대신, 방문 여부만으로 새로운 정점을 선택
• 구조적으로 사이클이 생기지 않도록 설계되어 있음

• DFS는 그래프의 가장 깊은 정점까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아오는(Backtracking) 방식
• 스택(Stack) 또는 재귀(Recursive Function) 로 구현
• 보통 경로 기반의 완전탐색, 백트래킹, 사이클 탐지 등에 사용

언제 사용되는가?

동작 방식

1. 시작 노드를 방문하고 처리
2. 방문한 노드에서 인접한 노드로 이동
3. 더 이상 방문할 곳이 없을 때까지 반복
4. 더 이상 진행 불가하면 되돌아가서 다른 분기로 이동

구현 예시 (Python)

재귀 함수 방식

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for neighbor in graph[v]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

graph = [
    [],         # 0번 노드 미사용
    [2, 3],     # 1번 → 2, 3
    [4],
    [4],
    [],
]
visited = [False] * 5
dfs(graph, 1, visited)  # 출력: 1 2 4 3

스택 기반 반복문 방식 (재귀 없이)

def dfs_stack(graph, start):
    visited = [False] * len(graph)
    stack = [start]

    while stack:
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            print(v, end=' ')
            stack.extend(reversed(graph[v]))  # 순서 보장

시간 복잡도

실전 문제 유형

Python vs C 구현 차이

연관 개념

핵심 요약

• DFS는 깊이 우선 탐색으로, 한 갈래 끝까지 내려간 후 되돌아옴
• BFS와는 반대로 경로 탐색, 완전탐색, 백트래킹 문제에 적합
• 재귀 방식이 가장 간단하지만, 깊이가 깊으면 스택 방식 필요
• 방문 여부 체크는 필수
• 실전에서는 섬의 개수, 미로 찾기, 백트래킹 유형에서 빈출

• 너비 우선 탐색: 가까운 정점부터 넓게 탐색
• Queue(큐) 자료구조를 사용해 구현
• 시작점에서 인접한 정점을 먼저 탐색 후, 더 깊은 곳으로 진행

사용 목적

동작 순서

1. 시작 노드를 큐에 넣고 방문 처리
2. 큐에서 노드를 꺼냄
3. 인접 노드를 모두 큐에 추가
4. 큐가 빌 때까지 반복

구현 예시 (Python)

from collections import deque

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for neighbor in graph[v]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True

# 호출 예시
graph = [
    [],         # 0번 노드 미사용
    [2, 3],     # 1 → 2, 3
    [1, 4],
    [1, 4],
    [2, 3]
]
visited = [False] * 5
bfs(graph, 1, visited)  # 출력: 1 2 3 4

시간 복잡도

• O(N + M) (N: 노드 수, M: 간선 수)

실전 예시 문제

핵심 요약

• BFS는 가까운 노드부터 탐색
• Queue 사용 + 방문 체크 필수
• 가중치 없는 최단 거리 문제에서 가장 많이 사용됨
• Python은 deque, C는 배열 기반 큐 직접 구현

• 정점(Vertex)*과 간선(Edge)으로 구성된 자료구조
• 정점 간의 연결 관계(네트워크)를 표현
• 방향, 가중치, 연결성에 따라 다양한 그래프 형태 존재

핵심 용어

그래프의 종류

그래프 구현 방법 (Python 기준)

인접 행렬 (Adjacency Matrix)

n = 4
graph = [[0]*n for _ in range(n)]
graph[0][1] = 1  # 0 → 1 간선 추가

• 메모리: O(N²)
• 모든 간선 확인 빠름
• 간선이 적을 땐 비효율적

인접 리스트 (Adjacency List)

graph = [[] for _ in range(4)]
graph[0].append(1)  # 0 → 1 간선 추가

• 메모리: O(N + M)
• 연결된 노드만 탐색 가능
• 일반적으로 선호되는 방식

딕셔너리 기반

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': [],
    'D': []
}

• 문자열 정점 등 다양한 데이터 처리 시 유용

시간 복잡도 비교

실전 알고리즘 예시

Python vs C 구현 차이

자주 나오는 개념 정리

핵심 요약

• 그래프는 정점(Vertex) + 간선(Edge)로 구성
• 구현은 대부분 인접 리스트 사용
• 문제 조건에 따라 방향성/가중치/연결성 확인 필수
• 실전 문제는 그래프 탐색 + 자료구조 구현 능력이 핵심
• DFS, BFS, 다익스트라, 위상정렬 등 그래프 알고리즘과 연결됨

• 정렬된 배열에서 탐색 구간을 절반씩 줄이며 값을 찾는 알고리즘
• O(log N)*의 빠른 탐색 성능
• 조건을 만족하는 최소/최댓값을 찾는 문제에도 자주 사용됨

전제 조건

• 입력 배열은 반드시 오름차순 정렬되어 있어야 함

주요 활용

• 값 존재 여부 확인
• 파라메트릭 서치
• lower_bound, upper_bound 구현

구현 방식

• 반복문, 재귀 함수
• 파이썬 내장: bisect (단 실전에서는 직접 구현 연습 필수)

분할 정복 (Divide and Conquer)

• 큰 문제를 작게 나누고(분할) → 해결(정복) → 결과를 합침
• 재귀 기반 알고리즘 설계의 핵심 패턴

대표 알고리즘

• 병합 정렬 (Merge Sort)
• 거듭제곱 계산 (aⁿ)
• 최대 구간합 문제

시간 복잡도

• O(log N) 또는 O(N log N)

특징

• 문제를 나눌 수 있어야 하며, 나눈 결과를 다시 합쳐서 정답을 만들어야 함

스택 (Stack)

• LIFO 구조: 나중에 들어온 데이터가 먼저 나감
• 시간 복잡도: O(1) (삽입, 삭제)

기본 연산

• push(), pop(), peek(), is_empty()

주요 활용

• 괄호 유효성 검사
• 수식 후위 표기법 계산
• 오큰수, 탑 문제 등

파이썬 구현

• 리스트 append(), pop()

큐 (Queue)

• FIFO 구조: 먼저 들어온 데이터가 먼저 나감
• 시간 복잡도: O(1) (deque 기준)

기본 연산

• enqueue(), dequeue(), peek(), is_empty()

주요 활용

• BFS 탐색
• 프린터 대기열
• 생산자-소비자 구조, 캐시 시스템

파이썬 구현

• collections.deque 사용
• append(), popleft()

우선순위 큐 (Priority Queue)

• 값의 크기(우선순위)에 따라 먼저 꺼내는 큐
• 일반 큐와 달리 최소값 또는 최대값을 빠르게 꺼낼 수 있음
• Heap 자료구조로 구현됨

시간 복잡도

• 삽입 / 삭제: O(log N)

파이썬 구현

• heapq 모듈 사용 (heappush(), heappop())

주요 활용

• 다익스트라 알고리즘
• K번째 큰 수
• 스케줄링, 대기열 처리 문제

연결 리스트 (Linked List)

• 각 노드가 다음 노드를 가리키는 포인터 기반의 선형 자료구조
• 중간 삽입/삭제가 O(1) 로 매우 빠름 (단 탐색은 O(N))

종류

• 단일 연결 리스트 (singly)
• 이중 연결 리스트 (doubly)

주요 활용

• LRU 캐시
• 내부적으로 큐, 스택 구현 시 활용
• 노드 삭제/삽입, 역순 연결 등

파이썬 구현

• Node 클래스 + LinkedList 클래스 구성

해시 테이블 (Hash Table)

• Key → Hash Function → Index → Value 저장
• 탐색/삽입/삭제 평균 O(1)

주요 특징

• Key는 immutable 타입이어야 함
• 충돌이 발생할 수 있으므로 충돌 처리 필요 (chaining, open addressing 등)

파이썬 구현

• dict, defaultdict, get(), in

주요 활용

• 등장 횟수 세기
• 중복 체크
• 빠른 조회, 맵핑

Week2 실전 대비 핵심 요약

복습 가이드

• 각 구조/알고리즘의 시간복잡도, 활용 사례, 구현 방식을 중심으로 다시 정리
• 파이썬 기본 모듈(collections, heapq, bisect) 활용법 연습
• C로 전환할 경우 직접 구현 방식도 병행 학습

• Key를 해시 함수에 넣어 고유한 인덱스를 생성하고, 그 인덱스에 데이터를 저장하는 구조
• Key-Value 쌍으로 데이터를 저장
• 빠른 탐색, 삽입, 삭제 가능
• 파이썬에서는 dict, C에서는 배열 + 해시 함수 직접 구현

주요 특징

• 평균 시간 복잡도는 O(1)
• Key 값은 변경 불가능한 자료형만 사용 가능 (str, int, tuple 등)
• 해시 충돌이 발생할 수 있으며 이를 처리하는 로직이 필요함

언제 사용되는가?

자료구조 동작 방식

1. Key에 해시 함수를 적용하여 index 계산
2. 해당 index에 Value 저장
3. 같은 index가 겹치면 충돌 발생 → 별도 충돌 처리 필요

해시 테이블 구현 예제

기본 사용

my_dict = {}
my_dict['apple'] = 3
print(my_dict['apple'])   # 3
my_dict['apple'] = 5       # 값 수정
del my_dict['apple']       # 값 삭제

존재 여부 확인

if 'banana' in my_dict:
    print("존재함")

문자 빈도수 세기

s = "banana"
count = {}
for c in s:
    count[c] = count.get(c, 0) + 1

# 결과: {'b': 1, 'a': 3, 'n': 2}

시간 복잡도

※ 일반적으로 충돌은 잘 발생하지 않도록 구현

실전 문제 유형 예시

C언어 구현 시 고려사항

관련 파이썬 함수

핵심 요약

• 해시 테이블은 O(1) 성능의 탐색/저장 구조로, 알고리즘에서 거의 필수
• 파이썬은 dict로 매우 간단하게 사용 가능
• 실전에서는 빈도수 세기, 중복 확인, 매핑 등에서 자주 등장
• C에서는 해시 함수, 충돌 처리, 메모리 관리까지 전부 직접 구현해야 함