알고리즘
데이터 타입과 범위
- int
- 크기: 4 Byte (32 bit)
- 표현 범위: ( -2^{31} ) ~ ( 2^{31} - 1 ) (약 -21억 ~ 21억)
- long long
- 크기: 8 Byte (64 bit)
- 표현 범위: ( -2^{63} ) ~ ( 2^{63} - 1 ) (약 -9경 ~ 9경)
- 메모리 계산
- 메모리가 512 MB인 경우:
- 1개의
int배열은 4 Byte를 차지하므로, 약 ( \frac{512 \times 1024 \times 1024}{4} = 134,217,728 )개의int를 저장할 수 있음. (약 1억 3천만 개)
- 1개의
- 메모리가 512 MB인 경우:
char- 크기: 1 Byte (8 bit)
- 표현 범위:
- Signed: ( -128 ) ~ ( 127 ) (기본적으로
char는 signed로 간주)
- Signed: ( -128 ) ~ ( 127 ) (기본적으로
unsigned char- 크기: 1 Byte (8 bit)
- 표현 범위:
- ( 0 ) ~ ( 255 ) (부호 없이 양의 정수만 표현)
실수와 연산 시 주의점
- 실수 연산의 오차
- 실수는 저장 및 연산 과정에서 정확한 값을 표현하지 못해 오차가 발생할 수 있음.
double은 유효 숫자가 최대 15자리까지 표현 가능.
- 정수를 실수에 저장할 때 주의
double에long long범위의 정수를 저장하면 데이터 손실이 발생할 수 있음.long long은 최대 19자리 숫자를 표현할 수 있으나,double은 유효 숫자가 15자리까지이므로 일부 값이 정확히 표현되지 않을 수 있음.
- 실수 비교 시 등호(=) 사용 금지
- 실수는 오차가 존재하므로,
a == b같은 비교는 정확하지 않을 수 있음. - 대신, 두 값의 차이가 일정 오차 범위 이내인지 확인해야 함.
1 2 3
if (abs(a - b) < 1e-12) { // a와 b가 거의 같다고 판단 }
- 실수는 오차가 존재하므로,
c++로 코딩테스트 시 주의점
함수 인자
1
2
3
4
5
6
7
bool cmp1(vector<int> v1, vector<int> v2, int idx){
return v1[idx] > v2[idx];
} //O(n)의 시간복잡도
bool cmp1(vector<int>& v1, vector<int>& v2, int idx){
return v1[idx] > v2[idx];
} //O(1)의 시간복잡도
입출력
- 공백을 포함한 문자열 입력 시 ```c++ string s; getline(cin, s); //입력
cout « s; //출력1 printf(“s is %s\n”, s); //출력2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#### 비트연산자
| 연산자 | 설명 | 예시 (5와 3) | 결과 |
|--------|-----------------------|--------------------------|------|
| `&` | 비트 AND | `5 & 3` (101 & 011) | `1` |
| `|` | 비트 OR | `5 | 3` (101 | 011) | `7` |
| `^` | 비트 XOR | `5 ^ 3` (101 ^ 011) | `6` |
| `~` | 비트 NOT | `~5` | `-6` |
| `<<` | 비트 왼쪽 이동 | `5 << 1` | `10` (5 * 2^1 = 10) |
| `>>` | 비트 오른쪽 이동 | `5 >> 1` | `2` (5 / 2^1 = 2) |
---
### 자료구조
#### 자료구조 특징 요약 표
| **자료구조** | **특징** | **장점** | **단점** | **시간 복잡도** | **메모리 배치** | **추가 메모리 소모** |
|--------------------|-------------------------------------------------------------------------|------------------------------------------------------------------------------------------------|------------------------------------------------------------------------------------------|---------------------------------------------------|----------------|--------------------------|
| **배열 (Array)** | 연속된 메모리 블록을 사용하는 고정 크기 데이터 구조 | k번째 원소 접근 O(1), Cache hit rate 높음 | 임의 위치 추가/제거 O(N), 연속된 메모리 필요 | 접근 O(1), 추가/제거 O(N) | 연속 | 거의 없음 |
| **연결 리스트 (Linked List)** | 노드가 데이터와 포인터를 포함, 동적 메모리 할당 | 임의 위치 추가/제거 O(1), 메모리 활용 유연 | k번째 원소 접근/수정 O(k), 포인터 오버헤드 발생 | 접근 O(k), 추가/제거 O(1) | 불연속 | O(N) (포인터) |
| **스택 (Stack)** | LIFO(Last In First Out) 구조 | 삽입/삭제 O(1), 재귀 문제 해결에 유용 | 맨 위 원소만 접근 가능 | 삽입/삭제/접근 O(1) | 배열/불연속 | 거의 없음 |
| **큐 (Queue)** | FIFO(First In First Out) 구조 | 삽입/삭제 O(1), 순차 데이터 처리에 적합 | 삽입/삭제 외에 임의 접근 불가능 | 삽입/삭제 O(1) | 배열/불연속 | 거의 없음 |
| **해시 테이블 (Hash Table)** | 키-값 쌍으로 데이터 저장, 해시 함수로 키를 매핑 | 평균 O(1)에 삽입/삭제/검색 가능, 큰 데이터 관리 효율적 | 충돌 문제 발생 가능, 최악의 경우 O(N) | 삽입/삭제/검색 O(1) 평균, O(N) 최악 | 불연속 | 충돌 해결 공간 필요 |
| **트리 (Tree)** | 계층적 데이터 구조로 각 노드가 자식 노드를 가짐 | 계층적 데이터 표현 적합, 이진 탐색 트리는 O(log N)에 검색/삽입/삭제 가능 | 균형 깨지면 성능 저하 (최악 O(N)), 구현 복잡 | 탐색/삽입/삭제 O(log N) 평균, O(N) 최악 | 불연속 | 부모/자식 포인터 공간 |
| **그래프 (Graph)** | 정점(Vertex)과 간선(Edge)으로 구성된 데이터 구조 | 복잡한 네트워크 표현 적합 | 데이터 크기 커질 경우 메모리 사용량 증가 | BFS/DFS O(V+E), 최단 경로 O(E+V log V) | 연속/불연속 | 인접 리스트/행렬 추가 공간 |
---
#### 배열과 연결 리스트 비교
| **특성** | **배열(Array)** | **연결 리스트(Linked List)** |
|----------------------|----------------|-------------------------------|
| k번째 원소 접근 | O(1) | O(k) |
| 임의 위치에 추가/제거 | O(N) | O(1) |
| 메모리 배치 | 연속 | 불연속 |
| 추가 메모리 소모 | 거의 없음 | O(N) (포인터) |
---
### 재귀(Recursion)
재귀는 문제를 분석시에는 절차적으로 생각하지 말고 **귀납적**으로 사고하여 단계별로 해결한다. **"1에서 동작한다면, k에서 동작하고, k+1에서도 동작한다"**는 귀납적 논리로 접근하는 것이 사고의 혼란을 줄이는 데 효과적.
#### **재귀의 특성과 고려 사항**
1. **재귀의 비효율성 문제**
- 한 함수가 자기 자신을 여러 번 호출하는 구조는 중복 계산이 발생하여 비효율적.
- 이를 해결하기 위해 **메모이제이션(Memoization)** 기법을 사용.
2. **함수의 인자 설계**
- 재귀 함수에서는 인자로 전달하는 값이 중요하다. 특히, 어떤 값을 기준으로 계산을 진행하고 어떤 데이터를 재귀 호출에 넘겨줄지를 명확히 정의해야 함.
3. **재귀와 반복문 비교**
- **재귀 방식:** 코드가 간결하며 문제의 구조를 직관적으로 표현하기 좋다.
- **반복문 방식:** 메모리 효율이 높고 성능이 우수하지만, 코드가 복잡해질 수 있다.
- 모든 재귀 함수는 반복문을 통해 동일한 기능을 구현할 수 있다. 다만 재귀는 호출 스택을 사용하므로 메모리/시간 측면에서 손해를 볼 수 있다.
---
#### 1. **곱셈에 대한 모듈러 연산**
큰 수의 곱셈 연산이 발생할 때, 오버플로우를 방지하기 위해 사용된다.
공식은 다음과 같다:
\[
(a \times b) \mod m = ((a \mod m) \times (b \mod m)) \mod m
\]
예시:
```java
long a = 1000000000L;
long b = 2000000000L;
long m = 1000000007L;
long result = ((a % m) * (b % m)) % m;
System.out.println(result); // 출력: 999999937
2. 덧셈에 대한 모듈러 연산
큰 수의 덧셈 연산에서도 오버플로우를 방지하기 위해 모듈러 연산을 적용한다.
공식은 다음과 같다: [ (a + b) \mod m = ((a \mod m) + (b \mod m)) \mod m ]
예시:
1
2
3
4
5
long a = 1000000000L;
long b = 500000000L;
long m = 1000000007L;
long result = ((a % m) + (b % m)) % m;
System.out.println(result); // 출력: 1500000000 % 1000000007 = 500000006
3. 제곱에 대한 모듈러 연산 (거듭제곱 분할 정복)
재귀적으로 큰 거듭제곱 값을 계산할 때, 연산을 효율적으로 수행하기 위해 분할 정복(Divide and Conquer) 기법을 사용한다.
거듭제곱에 대한 모듈러 연산 공식은 다음과 같다: [ (a^m \mod n)^c \mod n = (a^{m \cdot c}) \mod n ]
이를 재귀로 구현한 예시는 다음과 같다:
Java 예시 코드:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class ModularExponentiation {
// base^exp % mod를 계산하는 함수
public static long modPow(long base, long exp, long mod) {
if (exp == 0) return 1; // 기본 조건: 지수가 0이면 결과는 1
long half = modPow(base, exp / 2, mod); // 재귀 호출로 절반 계산
half = (half * half) % mod; // 절반 값을 제곱 후 모듈러 연산
if (exp % 2 != 0) {
half = (half * base) % mod; // 지수가 홀수라면 추가로 base를 곱함
}
return half;
}
public static void main(String[] args) {
long base = 3;
long exp = 13;
long mod = 1000000007;
long result = modPow(base, exp, mod);
System.out.println("Result: " + result); // 출력: 1594323
}
}
BFS(Breadth First Search)
자주하는 실수
- 시작점에 방문했다고 표시를 남기지 않는다.
- 큐에 넣을 때 방문했다는 표시를 하는 대신 큐에서 빼낼 때 표시.
- 이웃한 원소가 범위를 벗어났는지 대한 체크를 실수.
- 테스트 케이스가 여러개일 때, 큐를 다 비우지 않고 다음 케이스로 넘어감. 케이스 마다 새로운 큐를 선언하는게 나음.
기본
```cpp #include
#include #include using namespace std;
int map[500][500]; bool vis[500][500]; int n, m; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; queue<tuple<int, int» q;
void bfs(int x, int y) { q.push({ x,y }); vis[x][y] = 1; while (!q.empty()) { tuple<int, int> cur = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int nx = get<0>(cur) + dx[i]; int ny = get<1>(cur) + dy[i]; if (nx<0 || ny<0 || nx>n || ny>m)continue; if (vis[nx][ny] || !map[nx][ny])continue; q.push({ nx,ny }); vis[nx][ny]=1; } } }
int main() {
1
2
3
4
ios::sync_with_stdio(0);
cin.tie(0);
return 0; } ```
DFS(Depth First Search, 백트래킹)
- 백트래킹이 DFS의 최적화된 버전이고, DFS는 완전 탐색의 한 방법이다.
This post is licensed under CC BY 4.0 by the author.