JArchive 프로그래밍 일기

목차 

0x00 다이나믹 프로그래밍 설명 

0x01 연습 문제

0x02 경로 추적 

0x00 다이나믹 프로그래밍 설명 

다이나믹 프로그래밍은 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 활용하여 문제를 해결하는 알고리즘이다. 

앞 글자만 따서 DP라고 부르기도 한다. 

재귀를 배울 때 피보나치 문제를 풀어봤다.
재귀적으로 구현하면, fibo(4)를 호출할 때 fibo(3)과 fibo(2)를 호출한다. 

fibo(3)은 또 fibo(2)와 fibo(1)을 호출하고. fibo(2)는 fibo(1)과 fibo(0)을 호출한다. 

-> 중복된 연산 발생! 

int fibo(int n){
  if(n <= 1) return 1;
  return fibo(n-1) + fibo(n-2);
}

피보나치 문제를 DP로 해결하면, 연산의 결과를 배열에 저장하는 메모이제이션을 활용한다. 

그래서 fibo(1)을 재호출하지 않고 f[1]의 값을 재활용한다. 

int fibo(int n){
  int f[20];
  f[0] = f[1] = 1;
  for(int i = 2; i <= n; i++)
    f[i] = f[i-1] + f[i-2];
  return f[n];
}

연산의 중간 결과를 저장하여 재활용 하니까. O(N)에 답을 구할 수 있다. 

DP를 푸는 과정 

1. 테이블 정의하기 

2. 점화식 찾기

3. 초기값 정하기 

DP는 점화식 찾고, 초기값을 채워넣은 후에 반복문을 돌면서 배열을 채우면 구현이 끝나는 단순한 구조다. 

DP에 익숙하지 않으면 DP문제인지도 알아채지 못할 수도 있다. 여러 문제를 풀면서 DP 점화식을 찾는 연습을 하자.

 0x01 연습 문제 : 1로 만들기 BOJ 1463

이 문제는 BFS로도 해결할 수 있다. dist 배열을 두고 초기값을 1로 한 뒤, x2, x3, +1로 뻗어나가면 답이 나온다. 

그런데 DP로 풀면 훨씬 짤막하게 구현할 수 있다.

1. 테이블 정의하기

먼저 테이블은 위와 같이 정의하자. D[i] = i를 1로 만들기 위해 필요한 연산 횟수의 최솟값

배열의 인덱스와 값을 어떻게 구성할지에 관한 건 여러 경험이 쌓이면 감이 온다. 

2. 점화식 찾기

구체적인 예시를 들어서 D[12]를 구하는 연산을 생각해보자. 

D[12] = 12를 1로 만들기 위해 필요한 연산 횟수의 최솟값

3으로 나눈다: D[12]  =  D[4] + 1번의 연산(3으로 나누기)

2로 나눈다: D[12] = D[6] + 1번의 연산(2로 나누기)

1을 뺀다 D[12] = D[11] + 1번의 연산(1 빼기)

세 가지 연산 횟수 중에서 최솟값이 답이 된다. 따라서 D[12] = min( D[4] + 1, D[6] + 1, D[11] + 1)  

3. 초기값 정의하기 

1을 1로 만드는데 연산은 0번 필요하다. D[1] = 0

2를 1로 만드는데 연산은 1번 필요하다.(2로 나누거나 1을 빼기) D[2] = 1

이 문제에서는 D[1] 초기값만 정해주면 된다.

이제 D[] 배열을 전역에 잡고 for문을 돌면서 주어진 정수x 인덱스까지 채우면 답이 나온다. 

1로 만들기 바킹독님 코드, 내 코드

   // http://boj.kr/161694ef04f04d8dbe826e253622c1cb
#include <bits/stdc++.h>
using namespace std;

int d[1000005];
int n;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  d[1] = 0;
  for(int i = 2; i <= n; i++){
    d[i] = d[i-1]+1;
    if(i%2 == 0) d[i] = min(d[i],d[i/2]+1);
    if(i%3 == 0) d[i] = min(d[i],d[i/3]+1);
  }
  cout << d[n];
}

DP는 구현이 이렇게 짤막한 편이다. 점화식을 찾아내는 것이 관건이다. 

0x01 연습 문제 : 1,2,3 더하기 BOJ 9095

1. 테이블 정의하기

정수 4를 1,2,3의 합으로 나타내는 방법의 수는 본문에 나와 있지만 7가지다.

테이블은 D[4] = 7 의 형태로 만들면 된다. D[i] = i를 1,2,3의 합으로 나타내는 방법의 수. 

7가지 방법을 3줄에 나눠서 써놨다. 규칙이 뭘까? 점화식을 생각해보자. 

첫 번째 줄은 +1로 끝난다.

두 번째 줄은 +2로 끝난다.

세 번째 줄은 +3으로 끝난다. 

2. 점화식 찾기 : 노랑으로 표시된 +1, +2, +3만 제외하고 생각해보자. 

3을 1,2,3의 합으로 나타내는 방법에 +1, +2, +3 을 붙이면  4가 된다.

이렇게 D[4]=D[3] + D[2] + D[1] 이 성립하게 된다. 

3. 초기값 정하기 

D[i] 는 직전 값이 3개는 필요하다. D[i] = D[i-1] + D[i-2] + D[i-3] 

D[1] = 1, D[2] =2, D[3] = 4. 

1,2,3 더하기 바킹독님 코드, 내코드

// http://boj.kr/8b763a1df15a4cb3936f7a181f3db97c
#include <bits/stdc++.h>
using namespace std;

// d[i] = i를 1, 2, 3의 합으로 나타내는 방법의 수
int d[20];
int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  d[1] = 1; d[2] = 2; d[3] = 4;
  for(int i = 4; i < 11; i++)
    d[i] = d[i-1] + d[i-2] + d[i-3];

  int t;
  cin >> t;
  while(t--){
    int n;
    cin >> n;
    cout << d[n] << '\n';
  }
}

0x01 연습 문제 : 계단 오르기 BOJ 2579

만약 N이 20 정도로 그다지 크지 않으면 백트래킹 같은 방법으로 O(N^2)으로 해결이 가능하다. 

지금처럼 N이 300이라면 DP로 해결해야 한다. 

2개의 규칙을 유념하자. 

1) 최종 계단은 반드시 밟아야 한다.

2) 계단을 연속 3개 밟을 수 없다.

1. 테이블 정의하기

S[k] = 주어진 계단 점수

D[i] = i 번째 계단까지 최대 점수 

2. 점화식 찾기 

최종 계단은 반드시 밟아야 하니까, 그 이전 계단에 대해서만 생각하자.

계단이 4개 있을 때 가능한 경우 2가지를 그림으로 그렸다. 

경우 2 : 4번째 계단이 2연속 밟은 계단이면, 직전 계단은 반드시 밟는다.

경우 1 : 4번째 계단이 1연속 밟은 계단이면, 직전 계단은 반드시 안밟는다. 

경우 1 : 최종 계단이 2번째 연속으로 밟은 계단이면, 확실한건 3번은 밟았고 2번은 안밟는다는 것이다. 

따라서 1번째 계단까지의 최대점수(D[1]) + 3번 점수(S[3]) + 4번 점수(S[4]) 가 답이 된다.

경우 2 : 최종 계단이 1번째 연속으로 밟은 계단이면, 확실한건 3번은 안밟았다는 것이다.

따라서 2번째 계단까지의 최대점수(D[2]) + 4번 점수(S[4]) 가 답이 된다.

점화식은 아래와 같다. 

D[i] = S[i] + max(S[i-1] + D[i-3] , D[i-2]);

3. 초기값 정하기 

i를 구할 때 i-3 이 필요하니까 1, 2, 3 까지 초기값을 정해줘야 한다.

D[1] = S[1], D[2] = S[2], D[3] = S[3];

계단 오르기 전체 코드 바킹독님 코드, 내 코드 

// http://boj.kr/e93e56bb850a46378cf8f53486233cdc
#include <bits/stdc++.h>
using namespace std;

int s[305];
int n;
int d[305];

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  int tot = 0;
  for(int i = 1; i <= n; i++){
    cin >> s[i];
    tot += s[i];
  }
  if(n <= 2){
    cout << tot;
    return 0;
  }
  d[1] = s[1];
  d[2] = s[2];
  d[3] = s[3];
  for(int i = 4; i <= n-1; i++) d[i] = min(d[i-2],d[i-3])+s[i];
  cout << tot - min(d[n-1],d[n-2]);
}

0x01 연습 문제 : RGB거리 BOJ 1149

0x02 경로 추적 : 1로 만들기 2 BOJ 12852 

DP 문제집 

다음 시간에는 그리디 알고리즘을 공부한다. 

공부 내용 출처 : 바킹독 알고리즘 다이나믹 프로그래밍

목차

0x00 DFS 알고리즘 설명 

0x01 예시 

0x02 BFS vs DFS 

0x00  DFS 알고리즘 

DFS (Depth First Search)

다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 

BFS (Breadth First Search)

다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘

0x01 DFS 예시

BFS에서는 queue를 사용해서 모든 칸을 검사했었다. 

DFS는 큐 대신 stack 을 쓰는 것 뿐이고 나머지는 BFS와 똑같다. 

(0,0)에서 시작하여 상하좌우로 인접한 같은 색의 칸을 방문하는 Flood Fill을 구현해보자. 

아래는 좌표 배열이 있고, DFS를 위한 stack이 있다. 

탐색 흐름을 그림으로 확인하자. 

1. (0,0)시작점에 방문표시를 하고, stack에 push한다. 

스택이 빌 때까지 계속 스택의 top을 확인하여 상하좌우를 살펴보며 미방문한 좌표를 스택에 푸시하는 작업을 반복한다. 

2. 현재 스택의 top은 (0,0)이다.

(0,0)을 pop()해서 (0,0)의 상하좌우를 확인한다. 

파란 칸이면서 방문하지 않은 좌표를 스택에 push한다. -> (1,0)과 (0,1)을 push

3. 현재 스택의 top은 (1,0)이다.

(1,0)을 pop() 해서 (1,0)의 상하좌우를 확인한다. 

(0,0)은 이미 방문했고, (1,1)은 못간다. (2,0)은 방문하지 않은 칸이다. 

(2,0)에 방문표시를 하고 stack에 push한다. 

4. 이제 스택의 top은 (2,0)이 된다. (2,0)을 pop한다. 

전체 과정 그림으로 보기

0x02 BFS vs DFS 

BFS는 queue를 쓰고 DFS는 stack을 쓴다는 차이가 있지만, 원소 하나를 빼내서 주변을 살핀다는 알고리즘의 흐름은 똑같다. 

이 그림에서 관찰할 점은 방문순서다.

BFS

중앙의 1번 칸을 중심으로 주위를 보면, 1방문 후에 상하좌우 2,3,4,5번 방문한다.

마치 냇가에 던진 돌로 인해 동심원이 생기는 것처럼 상하좌우로 퍼져나간다. 

이전 강의에서 배운 '거리 순으로 방문한다'는 성질을 확인할 수 있다. 

DFS

갈 수 있을 때 까지 간다.

가능한 깊게 직진하는 모양이다. depth 우선 탐색이라는 성질을 그림으로 확인할 수 있다. 

거리 잴 때 DFS? BFS?

Flood Fill을 구현할 때 DFS, BFS 무엇을 쓰든 상관은 없다.

하지만 BFS에서 거리 잴 때 유용하게 썼던 "현재 보는 칸으로부터 추가되는 인접한 칸은 거리가 현재보다 1만큼 떨어져있다"는 성질이 DFS에서는 성립하지 않는다. 

결국 다차원 배열에서 굳이 DFS를 쓸 일이 없다. 거리측정은 BFS만 가능하기 때문이다. 

DFS는 그래프와 트리라는 자료구조를 쓸 때 짜게 된다. 

이 수업에서는 DFS는 stack을 써서 다차원배열을 순회하는 알고리즘 이라고만 기억하고 넘어가자. 

다음 시간에는 재귀를 공부한다. 

공부 자료 출처 : 바킹독 알고리즘 DFS

목차

0x00 수식의 괄호 쌍이란?

0x01 문제 해결을 위한 관찰

0x02 문제 해결 방법

0x03 연습문제

0x00 수식의 괄호 쌍이란? 

수식의 괄호 쌍이 짝이 맞는지 확인해보자. 

( 이 있으면 ) 으로 닫아야 짝이 맞다. { 이 있으면 } 이 있어야한다. 

두 번째 식에서 (12+4} 여기가 틀렸다. 이와 같이 수식의 괄호 쌍이란, 주어진 괄호 문자열이 올바른지 판단하는 문제다. 

0x01 문제 해결을 위한 관찰 

아래의 3개 수식 중에 올바른 괄호 쌍은 무엇 무엇이 있을까? 

결론부터 말하면 첫 번째 식만 올바른 괄호 쌍이다. 

판단 방법 중에 가장 보편적인 방법은 바로 안쪽부터 짝 맞추기를 해서 지워나가는 방법이다. 

그리고 관찰력이 뛰어나다면,  ')' 의 개수가 '(' 의 갯수를 넘지 않으면 된다는 사실도 있다. 

괄호의 종류가 () 말고도 {}, [] 이 있다면, 여는 괄호의 갯수와 닫는 괄호의 갯수 비교만으로 해결되지 않는다. 

우리는 머릿속으로 어떤 로직을 거쳐서 판단한 걸까? 생각의 과정을 관찰하여 코드로 구현해보자. 

스택을 이용하여 구현해보자. 

아래의 관찰을 인지해야 한다. 

"닫는 괄호는 남아있는 괄호 중에서
가장 최근에 읽은 여는 괄호와 짝을 지어 없애버리는 명령이다. " 

1. 스택을 하나 두고, 문자열을 읽어 나가다가 여는 괄호를 만나면 모두 스택에 넣는다. 

2. 문자열을 읽어 나가다가 닫는 괄호를 만나면 스택의 top을 확인한다. 

3. 지금 읽은 것이 닫는 괄호이고 스택의 top이 여는괄호라면?  쌍이 올바른 것이다.

4. 따라서 스택의 top인 여는 괄호를 스택에서 지운다. pop() 

올바르지 않은 괄호 쌍 

올바르지 않은 괄호 쌍의 경우, 과정을 살펴보자. 

1. 문자열을 읽다가 만난 여는 괄호 2개는 모두 스택에 넣는다. 

2. 닫는 괄호 ) 를 만나면, 스택의 top을 확인한다. 

현재 스택의 top은 { 이다. 

3. 스택의 top인 {와 닫는괄호 ) 는 짝이 안맞는다. 

올바르지 않은 괄호 쌍의 예시 2가지 

1. 문자열을 끝까지 읽었는데, 스택에 여는 괄호가 남아있다. 

2. 문자열을 끝까지 읽고 스택도 비었는데, 닫는 괄호가 남아있다. 

0x02 문제 해결 방법 

올바른 괄호 쌍 판단을 위해 문제 해결 방법을 정리해본다. 

1. 여는 괄호가 나오면 스택에 추가.

2. 닫는 괄호가 나왔을 경우, 스택의 top이 짝이 맞는 괄호라면 pop 

3. 스택에 괄호가 남아있지 않으면 올바른 괄호 쌍. 

스택이 비었을 때 top을 참조하면 런타임에러!

0x03 연습문제 

수식의 괄호쌍이 코딩테스트에서 무조건 나온다고 할 정도로 중요하진 않지만,

stack을 이용한 문제가 많기 때문에 연습문제를 꼭 풀어보자. 

다음 시간에는 BFS를 배운다. 

공부 자료 출처 : 바킹독 알고리즘 수식의 괄호 쌍

목차

0x00 정의와 성질

0x01 기능과 구현

0x02 STL queue

0x03 연습문제 

0x00 정의와 성질

큐는 뒤에 원소를 넣고, 앞에서 원소를 빼는 자료구조다. 

큐 자료구조 방식은 넣은 순서대로 나오니깐, First In First Out 이라고 한다. FIFO

반대로 스택은 방금 넣은 것이 최상단에 있으니까 Last In First Out 이다. LIFO

스택과 똑같이 원소 추가/제거에 O(1) 시간이 걸린다. 

다른 점
큐는 뒤에서만 추가하고 앞에서만 제거한다.  => back에서 추가 front에서 제거 
스택은 top에서만 추가/제거한다. 

0x01 기능과 구현

배열을 이용해서 큐를 간단히 구현해보자. 

const int MX = 100005;
int dat[MX];
int head = 0, tail = 0;

데이터를 담을 배열을 선언한다.

데이터를 꺼낼 앞쪽 인덱스를 저장하는 head 와, 데이터를 넣을 뒤쪽 인덱스를 저장하는 tail을 선언한다. 

큐라는 자료구조와 STL queue에는 큐의 인덱스를 제공하지 않는다. 지금은 배열을 이용한 구현이기 때문에 인덱스를 이용한다. 

시작할 때는 tail 과 head가 모두 0 을 가리키고 있다. 

데이터를 넣고 빼고 하다보면, 자연스레 데이터가 뒤쪽 인덱스에 몰리게 된다. 

이를 해결하기위해 '원형 큐' 라는 개념을 쓴다. 

head나 tail이 마지막 인덱스(MX가 되면,) 7이 되면, 1이 더해질 때, 0번지를 쓰도록 하는 것이다. 

0x02 STLqueue

큐에서는 빼내는 앞쪽의 원소를 확인하는 front() 와 넣는 뒤쪽의 원소를 확인하는 back()이 있다. 

큐 레퍼런스 

// Authored by : std-freejia
#include <bits/stdc++.h>
using namespace std;

int main(void) {

  queue<int> qu;

  qu.push(10);  // 10
  qu.push(20);  // 10 20
  qu.push(30);  // (앞) 10 20 30 (뒤)

  cout << qu.size() << '\n';

  if(qu.empty()) cout << "Q is empty\n";
  else cout << "Q is not empty\n";

  qu.pop(); // 20 30
  cout << qu.front() << '\n';  // 20
  cout << qu.back() << '\n';   // 30
  qu.push(40); // 20 30 40
  qu.pop();       // 30 40

  return 0;
}

실행 결과 

3
Q is not empty
20
30

0x03 연습문제 

큐 문제집

다음 시간에는 deque 덱을 배운다.

공부 자료 출처 : 바킹독 알고리즘 큐 

목차

0x00 배열의 정의와 성질 

0x01 기능과 구현 

0x02 STL vector 

0x03 연습문제 

0x00 배열의 정의와 성질 

정의

메모리 상에 원소를 연속하게 배치한 자료구조 

성질 

1. O(1)에 k번째 원소를 확인/변경 가능 

2. 추가적으로 소모되는 메모리의 양(overhead)이 거의 없음 

3. Cache hit rate가 높음 

4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림  

참고) Cache hit rate 가 높다는 의미 

캐시 적중률이 높다 == 캐시를 참조했더니 데이터가 존재하는 확률이 높다.

캐시의 지역성에 기반하여 캐시에 존재하는 데이터의 주변 데이터도 곧 사용할 가능성이 높은 데이터다. 

배열은 메모리상에 연속한 구간에 존재하기 때문에 Cache hit rate가 높다. 

0x01 기능과 구현

조회, 수정 O(1)

인덱스로 바로 접근할 수 있으니까 O(1) 시간이 걸린다. 

맨 끝에 추가, 마지막 원소를 제거 O(1)

따로 배열을 변경할 필요 없기 때문에 O(1)이 걸린다. 

임의의 위치에 원소 추가 O(N)

평균적으로 N/2 개를 밀어야 하기 때문이다. 

책꽂이에 꽂힌 책들을 생각해보자. 중간에 책을 하나 꽂으려면, 나머지 책들을 옆으로 밀어야 한다. 

임의의 위치에 원소 제거 O(N)

이 경우도 원소를 하나 제거하고, 평균적으로  N/2 개를 밀어야 하니까 O(N)의 시간이 필요하다. 

insert 함수와 erase 함수를 직접 구현해보자

github 링크에 들어가서 코드를 받고 직접 삽입/삭제를 구현해보자. 

존재하지 않는 인덱스를 참조하지 않도록 주의해야 한다. 

배열 초기화 팁 

1. memset  실수할 여지가 많다. 0이나 -1아닌 다른 값을 넣으면 오동작한다. 

2. for  투박하지만 실수할 여지가 없어서 무난하다. 

3. algorithm헤더의 fill함수 사용을 권한다. 

실수할 여지도 별로 없고, 코드가 짧아서 가장 추천하는 방식이다. 

    int a[21];
    int b[21][21];
    
    // 1. memset
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    
    // 2. for
    for(int i = 0; i < 21; i++)
        a[i] = 0;
    for(int i = 0; i < 21; i++)
        for(int j = 0; j < 21; j++)
            b[i][j] = 0;
        
    // 3. fill
    fill(a, a+21, 0);
    for(int i = 0; i< 21; i++)
        fill(b[i], b[i]+21, 0);

0x02 STL vector 

배열과 거의 동일한 기능의 STL 
배열과 달리 크기를 자유자재로 늘이고 줄일수 있는 장점이 있다. 

공식 레퍼런스 사이트에서 확인하며 메서드 정확하게 익히도록 연습하기.
iterator는 따로 공부하는 것을 추천함

#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> v1(3, 5);  // {5,5,5}
    cout << v1.size() << '\n';   // 3
    v1.push_back(7);   // {5,5,5,7}
    
    vector<int> v2(2);    // {0,0}
    v2.insert(v2.begin()+1, 3);   // {0,3,0}
    
    vector<int> v3 = {1,2,3,4};
    v3.erase(v3.begin() + 2);  // {1,2,4}
    
    vector<int> v4;  // {}
    v4 = v3;   // {1,2,4}
    cout << v4[0] << v4[1] << v4[2] << '\n';  // 1 2 4
    v4.pop_back(); // {1,2}
    v4.clear();    // {}
}

시간 복잡도 유념할 점

앞에서 넣고 빼는 popfront(), pushfront() 는 O(N)의 시간이 걸리는 것을 유의하자. 

insert(), erase()는 시간복잡도가 O(N)

뒤 쪽에 넣고 빼는 popback(), pushback()은 O(1)

벡터에서 = 를 사용하면 deep copy 가 발생한다. 

vector 순회하는 방법

vector<int> v1 = {1,2,3,4,5,6};

// 1. range-based for loop (since C++11)
for(int e: v1)
	cout << e << ' ';
    
// 2. not bad
for(int i = 0; i< v1.size(); i++)
	cout << v1[i] << ' ';
    
// 3. 주의! 
for(int i = 0; i <= v1.size()-1; i++)
	cout << v1[i] << ' ';

1. range-based for loop 범위 기반 반복문 (C++11 부터 지원된 기능임을 유의)

2. v1.size()를 인덱스의 끝으로 보는 것 

3. v1.size()는 기본적으로 unsized int를 반환함! 조심해야 함. 

만약, v1이 빈 벡터일 때, 
v1.size() -1 이 unsigned int 0에서 int1 을 빼는 식이 된다. 
그리고 unsiged int 와 int를 연산하면 unsigned int 로 자동 형변환이 된다.

unsigned int 0 - (int) 1은 -1이 아니라, 4294967295 가 되어버린다!! 
unsigned int  overflow가 발생하여 런타임 에러가 난다. 

0x03 배열 연습문제

 배열 문제집을 풀어보자. 

BOJ 10808번 알파벳 갯수 

다음시간에는 연결리스트를 배우고 연습문제를 풀어본다. 

공부 내용 출처 : 바킹독 알고리즘 0x03 배열 

이번 강의 내용은 실제 코드를 짤 때 주의해야 할 점이다. 

목차 

0x00 STL과 함수 인자 

0x01 표준 입출력 

0x02 코드 작성 팁 

0x00 STL과 함수 인자 

아래 함수의 출력값을 말해보자. 

첫 번째 

func 함수에 t값을 복사해서 보낸다. 

따라서 t값은 변함이 없다. 답은 0이 출력된다. 

두 번째 

배열 이름을 넘긴다는 것은 배열 주소를 넘기는 것이다. 

arr의 값을 넘기고, 0번째 값 주소에 접근해서 10을 할당했다. 

답은 10이 출력된다.  

세 번째 

구조체는 사용자 정의 자료형이다. 첫 번째 문제처럼 값이 다 복사되어 넘어간다.

따라서 답은 0이다. 

STL을 쌩으로 함수 인자에 넣으면, 복사해서 보낸다. deep copy

STL도 구조체랑 비슷하다.

함수 인자로 실어보내면 복사본을 보낸다. 따라서 원본에 영향을 주지 않고, 0이 출력된다. 

벡터 안의 값을 비교하고 싶다면?  주소 값을 보내자. 

cmp1 함수 : vector 값을 전부 복사하기 때문에 O(N) 시간복잡도가 나온다. 

cmp2 함수 : 주소만 넘기기 때문에, O(1) 이 된다. 

0x01 표준 입출력 

1. cin/cout 쓸 때 유의사항 : 입출력으로 인한 시간초과를 막기 위해서 아래 코드를 넣어주자. 

단, 이 명령을 쓰면 cout/cin과 printf/scanf를 섞어쓰면 안된다. 

ios::sync_with_stdio(0)
cin.tie(0)

2. 공백을 포함한 문자열을 받을 때, getline을 쓰자 

3. endl 쓰지 마세요. (궁서체)

줄바꿈이 필요하다면 개행문자를 쓰자. '\n'

0x02 코딩 팁

1. 코딩 테스트와 개발은 다르다. 

코테의 목표는 제한 시간 안에 정답을 받는 것이다. 

코테의 목표는 남이 알아볼 수 있는 클린 코드를 작성하는 것이 아니다. (변수명, 예외처리 를 크게 신경 쓸 필요가 없다.)

내가 헷갈리지 않는 범위 안에서 어떻게든 타이핑을 아끼자. 

2. [중요] 문제를 30분 고민했는데 실마리가 안잡히면?

스트레스 받지 말고 다른 사람의 코드를 보며 배워가면 된다. (스트레스 받으면 코테 준비 오래 못한다)

코테 준비는 원리를 이해하고 패턴을 익히는 것이기 때문이다. 

기초코드 작성요령2 백준 문제집

다음 시간에는 '배열'을 공부한다.  

공부 자료 출처: 바킹독 실전알고리즘 기초코드 작성요령2 

이번 강의는 어려워도 꼭 필요한 기초 내용인 시간 복잡도와 자료형 내용이다.

목차 

0x00 시간, 공간 복잡도 

0x01 정수 자료형 

0x02 실수 자료형 

0x00 시간, 공간 복잡도

[중요]시간복잡도 

입력의 크기와 문제 해결에 걸리는 시간의 상관관계다. 

예를 들어, 반복문을 n번 실행하는 경우, n에 비례한다고 퉁쳐서 표현한다. 

다른 예시를 보자. 

사람들은 '정렬'되어 있음을 유의하자. 

만약 50명 사람이 정렬된 이름순으로 서있다면, 가운데 사람의 이름을 물어봐서 25명을 남기고, 

또 반을 쪼개서 12명, 6명, 3명.. 이런 식이면 '가나다'인 사람을 찾을 수 있다. 

만약 16명이 있다면,

반으로 나눠서 8명, 반으로 나눠서 4명, 또 반으로 나눠서 2명, 반으로 나눠서 마지막 1명을 찾을 수 있다. 

16명이 있을 때, 4번의 연산으로 타겟을 찾을 수 있다.  이 것을 lg N에 비례한다고 한다. 

빅오표기법 

주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법이다. 

O(1) : 상수시간 
O(lgN): 로그시간 
O(N): 선형시간 
O(lg N)부터 O(N²)  : 다항시간
O(2^N): 지수시간 
O(N!) : 팩토리얼 

공간 복잡도 

512MB 일때, 대강 1.2억개의 int를 사용할수 있음을 기억하자.  (int 1개가 4byte 임을 이용해 계산할 수 있다. )

0x01 정수 자료형

char 자료형은 1byte == 8bit 이다. 즉, 8개의 bit로 숫자를 표현한다. 

0000 0001 은 10진수로 1이다. 

0000 0010 은 10진수로 2를 표현한다. 

그런데, 맨 왼쪽은 -2의 7승이다. 맨 왼쪽 비트는 '부호비트'의 역할을 한다. 

왜그럴까?

음수를 표현하기 위함이다.

참고: 2의 보수(2's complement)

보수의 의미? 보충해주는 수를 의미한다. 

1에 대한 2의 보수는 1이다. 1에 1을 보충해줘야 2가 된다. 

1에 대한 10의 보수는 9이다. 1에 9를 보충해주면 10이 된다는 의미다.

비트는 0과 1밖에 없는 2진수임을 유의하자. 1에 대한 2의 보수는 1이다.

어떤 정수를 표현하는 N개 비트가 있다. 

이 비트를 전부 반전시키고, 1을 더하면 1의 보수가 나온다. 

예시는 아래와 같다.  1이 -1이 된다. 

어떤 수를 부호를 바꾸고자 한다면, 비트를 반전시킨 뒤 1을 더하면 된다. 

sign비트로 음수 표현하기 

부호를 표현하는 비트가 있냐 없냐에 따라서 표현할 수 있는 수의 범위가 2배 차이 난다. 

unsiged의 의미는 부호비트(sign)의 여부를 의미한다. 

Integer Overflow 문제 

정수의 표현 범위를 넘어서 sign비트가 바뀌면 overflow가 발생한다. 

맨 왼편이 -2의 7승, 즉 -128값을 가지기 때문이다. 따라서 각 자료형의 범위에 맞게 연산해야 함을 유의하자. 

큰 수를 다룰 때 8byte 정수 자료형 long long을 쓰자. 

만약 unsigned long long 을 넘어선다면 string으로 처리해야 하는데, Python을 쓰는게 C++ string을 쓰는 것 보다 편하다. 

0x02 실수 자료형 

실수 자료형은 float(4byte)와 double(8byte)가 있다. 

float는 1bit 32개다. 

double은 1bit 64개다. 

컴퓨터는 2진수를 기반으로 실수를 표현하기 때문에, 오차가 있음을 기억하자!

1을 3으로 나눠보자. 

10진수로 0.33333.... 무한소수로 길어진다.

2진수로 표현하면 ?  0.010101.. 로 역시 무한소수가 나온다. 

2진수의 과학적 표기법 IEEE 754 format 

실수를 표현하기 위해 32칸 혹은 64칸을 sign field, exponent field, fraction field 로 나눈다. 

sign field : 양수/음수 구분 
exponent field: 지수
fraction field : 유효숫자 

-6.75를 예로 들어보자. 

sign field :  음수니까 1로 표시 

exponent field:  여기서는 2승이니까 2

fraction field : 맨 앞의 1은 뺀, 1011이 적힌다. (맨 왼쪽부터 2의 -1승, 2의 -2승 ... 자리임)

[중요] 실수 자료형의 특징!

1. 실수 자료형은 필연적으로 오차가 있다. 

float는 유효숫자 6자리, double은 유효숫자 15자리 뿐이다.

여기서 유효숫자 15자리라는 의미는 
참 값이 1이라고 할 때, 1 - 10의 -15승에서 1 + 10의 +15승 사이의 값을 가진다는게 보장된다는 의미다. 

2. double에 long long 범위의 정수를 함부로 담지 말자. 

double은 유효숫자가 15자리인데, long long은 최대 19자리 이다. 

따라서 10의 18승과 10의 18승을 구분할 수 없고, 오차 섞인 값이 저장될 수 있다. 

3. 실수를 비교할 때는 등호를 사용하면 안 된다. 

실수 연산 시 오차가 발생할 수 밖에 없기 때문이다. 

아까 배운 것 처럼, 유효숫자가 float는 6자리, double은 15자리 뿐으로 표현에 제한이 있기 때문이다.

두 실수가 같은지 알고 싶을 때 ! 
두 실수의 차가 대략 10의 -12승 이하면 동일하다고 처리하는 것이 안전하다. 
 1e-12 는 10의 -12승을 의미하는 표기다. 

다음 강의에서는 표준 입출력과 코드 작성 팁에 대해 배운다. 

2의 보수 자료 출처: 2진수의 수와 음수 표현법

공부 자료 출처: 바킹독 실전 알고리즘 0x01강