빅오 표기법은 알고리즘의 시간복잡도나 공간복잡도를 표현할 때 사용되는 수학적 표기법입력 크기 n에 대해 가장 지배적인 연산 횟수(성장률)를 수학적으로 표현한 것으로 최악의 경우 기준으로 표현함a = arr[0] 의 경우 입력 크기와 관계없이 항상 일정한 시간으로 O(1)이진 탐색의 경우 입력을 절반씩 줄이기 때문에 O(log n)선형 탐색의 경우 한 번씩 다 훑기 때문에 O(n)머지 정렬의 경우 거의 모든 효율적인 정렬로 O(n log n)중첩 반복문의 경우 O(n^2)재귀 조합의 경우 O(2^n)완전탐색(순열)의 경우 모든 경우의 수를 탐색하기 때문에 O(n!)O(n+n^2)의 경우 n^2가 n보다 훨씬 빨리 커짐으로 빅오 표기법으로는 O(n^2)로 표기함void example1(int n){ for(..

1. Garbage Collection(GC)이란?GC는 더 이상 사용되지 않는 메모리를 자동으로 회수해주는 기능C#, Java 같은 관리형 언어 에서 제공됨기본 개념- 힙(Heap) 영역에 할당된 객체 중 더 이상 참조되지 않는 객체를 찾아서 메모리를 회수함- 수동 해제가 필요 없는 대신, GC 타이밍에 따라 성능 저하 발생 가능2. GC 동작 방식 (C# 기준)Mark and Sweep 방식1. Mark : 루트(Root) 객체에서 시작해 참조 가능한 객체를 모두 “살아있다”고 표시2. Sweep : 표시되지 않은 객체는 메모리에서 제거세대별 관리(Generational GC)- Generation 0 : 새로 생성된 객체 (빠르게 수거)- Generation 1 : 조금 오래된 객체- Generat..

1. 캐시란?CPU는 매우 빠르지만, RAM은 상대적으로 느림그래서 CPU와 RAM 사이에 작은 고속 메모리인 “캐시(Cache)"가 존재함- L1,L2,L3 캐시 : 점점 느리지만 크기는 커짐- CPU가 데이터를 요청할 때: - 캐시에 있으면 -> Cache Hit (빠름) - 없으면 -> Cache Miss (느림, RAM까지 내려감)2. Cache Hit vs Cache Miss- Cache Hit : CPU가 찾는 데이터가 캐시에 이미 존재 : 빠름 (수 ns)- Cache Miss : CPU가 찾는 데이터가 캐시에 없음 -> RAM에서 가져옴 (수십~수백 ns)3. Spatial & Temporal Locality (지역성)CPU 캐시는 지역성(Locality)을 기반으로 작동함- Tempo..

1. 메모리 모델이란?멀티쓰레드 환경에서 메모리에 접근할 때의 규칙과 보장 범위를 정의한 것- 우리가 x = 10 같은 코드를 쓴다고 해도, 실제 실행 순서나 읽는 값은 CPU, 컴파일러, 메모리 최적화에 의해 달라질 수 있음-> 언제 어떤 값이 보장되는지? -> 메모리 모델이 이걸 정의해서 줌2. 왜 중요한가?멀티코어 CPU에서는 각 코어마다 캐시가 있음-> 변수 값을 바로 RAM에서 읽지 않고, 자기 캐시에서 읽고 쓸 수 있음-> 그러면 문제가 생김:A 코어가 x=10 했는데, B 코어는 x가 0인줄 알고 잘못된 계산을 할 수 있음3. Cache Coherency (캐시 일관성)멀티코어 CPU는 코어들 간 캐시의 값을 동기화해야 함-> 이걸 캐시 일관성(coherency)라고 함대표적인 프로토콜 : ..

1. 경쟁조건이란?두 개 이상의 쓰레드가 공유 자원(예: 변수, 리스트 등)에 동시에 접근하려 할 때, 실행 순서에 따라 결과가 달라지는 문제예시 int counter = 0;Thread t1 = new Thread(()=> { for(int i=0; i { for(int i=0; i기대값은 2000이지만, 실제로는 1500 ~ 2000 사이의 값이 나올 수도 있음원자적(atomic) 연산이 아니기 때문원자적(atomic) 연산이란?하나의 연산이 “더 이상 쪼갤 수 없는 단위”로 수행되는 것- 실행 중 다른 쓰레드가 끼어들 수 없고,- 반드시 전부 성공하거나, 전부 실패함. 중간 상태가 없음즉, “한 번에 딱 처리된다” 라고 생각하면 됨왜 counter++는 원자적이지 않은가?counter++는 3단계로..

CPU와 메모리 사이의 속도 차이를 줄이기 위해 도입된 것이 캐시(Cache)게임처럼 연산이 많은 환경에서는 캐시의 활용이 성능에 엄청난 영향을 줌1. 왜 캐시가 필요할까?- CPU는 엄청 빠름- RAM(메인 메모리)은 상대적으로 느림- 매번 RAM에 접근하면 성능 저하 발생-> 그래서 CPU 근처에 더 빠르고 작은 기억장치인 캐시를 둬서 성능을 높임2. 캐시 메모리 계층 구조보통 캐시는 L1 -> L2 -> L3 순서로 구성됨계층 / 위치 / 크기 / 속도 / 역할L1 / CPU 내부 / 적음(수십 KB) / 가장 빠름 / 현재 실행 중인 명령과 데이터를 저장L2 / CPU 내부 or 외부 / 수백 KB~MB / L1보다 느림 / L1에서 못 찾을 때 사용L3 / CPU 외부 (공유) / 수 MB / ..