JArchive 프로그래밍 일기

목차

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 deque

0x03 연습문제 

0x00 정의와 성질

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하다. 

deque == double linked queue 

추가, 제거, 앞/뒤 원소 확인 모두 O(1) 이다. 

그리고 덱 자료구조는 원소의 인덱스 확인이 애초에 불가능하다. 

하지만 독특하게도 STL deque에서는 인덱스로 원소 접근이 가능하다. (STL stack, queue에서는 인덱스로 원소 접근 불가.)

0x01 기능과 구현

배열로 간단히 덱을 구현해보자.

필요한 변수는 큐랑 똑같이 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개다.

head는 가장 앞에 있는 원소의 인덱스이고 tail을 가장 뒤에 있는 원소의 인덱스 + 1 이다. 

설령 앞의 스택과 큐는 직접 구현해보지 않았더라도, 덱은 꼭 짜봤으면 좋겠다. 

배열로 덱 구현 템플릿 링크 

0x02 STL deque

STL deque는 vector와 비슷한 느낌이 강하다. 

하지만, vector와 달리 deque는 모든 원소가 메모리 상에 연속적으로 배치되어 있지 않다. 

앞쪽과 뒤쪽의 추가/제거가 모두 필요하다면 deque를 쓰는게 효율적이다. 

그렇지 않다면 vector를 쓰면 된다. 

deque 레퍼런스

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

int main(void) {

    deque<int> deq;
    deq.push_front(10); // 10
    deq.push_back(50);  // 10 50
    deq.push_front(24); // 24 10 50

    for(auto x : deq) cout << x << ' ';
    cout << deq.size() << '\n';

    if(deq.empty()) cout << "deque is empty\n";
    else cout << "deque is not empty\n";
    deq.pop_front();  // 10 50
    deq.pop_back();   // 10

    cout << deq.back() << '\n';  // 10
    deq.push_back(72);        // 10 72
    cout << deq.front() << '\n'; // 10
    deq.push_back(12);        // 10 72 12
    deq[2] = 17;                 // 10 72 17

    deq.insert(deq.begin()+1, 33); // 10 33 72 17
    deq.insert(deq.begin()+4, 60); // 10 33 72 17 60

    for(auto x : deq) cout << x << ' ';
    cout << '\n';

    deq.erase(deq.begin()+3);
    cout << deq[3] << '\n';

    deq.clear(); // 모든 원소 제거
    cout << deq.size();
    return 0;
}

0x03 연습문제 

덱 문제집 

다음 시간에는 스택을 활용한 '수식의 괄호 쌍'을 배운다. 

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

목차

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 stack

0x03 연습문제 

0x00 정의와 성질

원소의 추가가 O(1)
원소의 제거가 O(1)
제일 상단의 원소 확인이 O(1)

stack은 상단에서만 데이터를 push pop 할 수 있는 자료구조다.

제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능하다! 

push() : 상단에 x를 추가 
pop()   : 최상단의 데이터를 제거 
top()   : 최상단의 데이터를 조회(확인)

0x01 기능과 구현

배열을 이용해 직접 스택을 구현해봤다.  기본 코드는 바킹독 github 를 가져왔고, 직접 push, pop, top 함수를 채웠다. 

 내가 작성한 코드 

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

const int MX = 1000005;
int dat[MX];
int pos = 0; // 삽입할 수 있는 인덱스

void push(int x){
    if(pos != MX){
        dat[pos] = x;
    }
    pos++;
}

void pop(){
    if(pos != 0) pos--;
}

int top(){
    return dat[pos-1];
}

void test(){
    push(5); push(4); push(3);
    cout << top() << '\n'; // 3
    pop(); pop();
    cout << top() << '\n'; // 5
    push(10); push(12);
    cout << top() << '\n'; // 12
    pop();
    cout << top() << '\n'; // 10
}

int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);

    test();
    return 0;
}

아래는 바킹독님이 제공한 정답 코드

내코드보다 짧게 처리된 부분이 많았다. 

void push(int x){
  dat[pos++] = x;
}

void pop(){
  pos--;
}

int top(){
  return dat[pos-1];
}

0x02 STL stack

STL에서 stack을 제공하니깐 코테에서는 이것을 이용하자. 

직접 stack을 구현하는 것 보다는, 실수를 줄일 수 있기 때문이다. 

스택이 비어있는데 top()을 호출하면 런타임 에러가 발생하니까 주의하자. 
스택이 비어있는데 pop()을 호출해도 마찬가지로 런타임 에러가 난다. 

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

int main(void) {

    stack<int> s;
    
    s.push(10); // 10
    s.push(20); // 10 20
    s.push(30); // 10 20 30 (최근에 넣은 30이 꼭대기다.)
    cout << s.size() << '\n';  // 3

    if(s.empty()) cout << "S is empty\n";
    else cout << "S is not empty\n";   // S is not empty 출력

    s.pop(); // 10 20
    cout << s.top() << '\n';  // 20
    s.pop(); // 10
    cout << s.top() << '\n';  // 10
    s.pop(); // empty

    cout << s.top() << '\n'; // <--- runtime error 발생 !

    return 0;
}

0x03 연습문제 

스택 문제집 BOJ

다음 시간에는 큐를 공부한다. 

공부 내용 출처  바킹독 알고리즘 스택

목차 

0x00  정의와 성질 

0x01 기능과 구현 

0x02 STL list

0x03 연습문제 

0x00  정의와 성질 

연결리스트의 성질 

• k번째 원소를 조회/변경하기 위해 O(k)가 필요함 
• 임의의 위치에 원소를 추가/ 임의 위치의 원소를 제거 할때 O(1) 필요함
• 배열과 달리 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 다소 쉬움

연결리스트의 종류

• 단일 연결 리스트 : 원소가 ‘다음’원소의 주소를 알고 있다.
• 이중 연결 리스트 :  원소가 ‘이전’원소의 주소와 ‘다음’원소의 주소를 둘 다 알고 있다. 
• 원형 연결 리스트 : 마지막 원소가 가장 처음원소의 주소를 알고 있다. 

배열과 연결리스트 비교

배열은 원소의 값만 저장한다. 반면에 연결리스트는 '다음 원소의 주소'도 저장하므로 메모리를 더 필요로 한다. 

연결리스트를의 시간복잡도를 정리하면, 

임의의 위치에 있는 원소를 확인하거나 변경 = O(N)
임의의 위치에 원소를 추가/ 임의 위치의 원소를 제거 = O(1)
(추가할 주소를 알고 있는 경우, O(1)에 가능하다는 의미다. )

배열에 비해, ‘다음 주소’만큼의 메모리를 소모한다. 

그래서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요하다.
64비트 컴퓨터라면 주소값이 64비트(=8바이트) 단위이니 8N 바이트가 추가로 필요하게 된다. 
즉 N에 비례하는 만큼의 메모리를 추가로 쓰게 된다. 

0x01 기능과 구현 

기능

임의의 위치에 있는 원소를 확인하거나 변경 = O(N)
임의의 위치에 원소를 추가/ 임의 위치의 원소를 제거 = O(1)

어디에 연결리스트가 어디에 활용될까 ?

메모장! 을 예로 들 수 있다.
커서를 옮기고, 글자를 지우고 이러한 변경 연산이 많다. 
이렇게 추가 제거 연산이 자주 발생하는 경우 연결리스트 사용을 고려해보자. 

구현

STL에서 제공하는 list를 쓰자. 
STL에 연결리스트가 있는데, 이 컨테이너의 이름은 list이고  내부적으로 Double Linked List로 구현되어 있다. 
면접에서의 손코딩을 대비할 때 STL list를 이용해서 끄적이며 연습하자. 

정석적인 구현

NODE 구조체나 클래스를 만들어서 원소가 할당될 때마다 동적할당을 하고, 노드를 삭제하면 메모리를 해제하는 식으로 구현한다. 

struct NODE{
  struct NODE *prev, *next;
  int data;
};

야매 연결 리스트

STL의 list가 제공되지 않는 경우에 임시로 쓰는 연결리스트 형태를 배운다 .
메모리 할당 및 해제를 생략하고 배열만을 이용한다. 
메모리 누수 문제 때문에 실무에서는 절대 쓸 수 없다. 
구현 난이도가 일반적인 연결리스트보다 낮고, 시간복잡도도 동일하므로 코테에서만 애용하면 된다. 

야매 연결리스트는 원소를 배열로 관리한다. 

이전/다음 원소 주소를 가리키는 대신, 배열 인덱스를 저장하는 방식으로 구현한 연결리스트다. 

dat 배열 : 데이터 저장 
pre 배열 : 이전 노드의 주소 저장
nxt 배열 : 다음 노드의 주소 저장  
unused: 새로운 원소가 들어갈 수 있는 인덱스. 원소가 추가되면 1씩 증가한다. 
0번지: 시작점을 나타내기 위한 dummy node. 실제로 값을 저장하지 않는다. 

pre 값이나 nxt 값이 -1이면 해당 원소의 이전/다음 원소가 존재하지 않는다는 의미다. 

모든 노드를 순회하여 출력하는 traverse() 함수 

0번지 (dummy node)에서 시작한다. 

더미노드가 가리키는 nxt는 2 인덱스를 가리킨다. 

따라서 더미노드 다음 노드는 2번지 노드다. 

void traverse(){
	int cur = nxt[0];
    while(cur != -1){
    	cout << dat[cur << ' ';
        cur = nxt[cur];
    }
    cout << '\n';
}

insert() 함수 직접 구현해보기 

erase() 함수 직접 구현해보기 

전체 코드 바킹독 github 

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

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1; // 사용가능한 인덱스 

void insert(int addr, int num){ // 삽입하려는 인덱스와 값을 파라미터로 받는다. 
  dat[unused] = num;   // 새로운 원소를 생성 
  pre[unused] = addr;  // 이전 노드의 다음 인덱스에 현재 삽입하려는 인덱스를 대입 
  nxt[unused] = nxt[addr]; // 새 원소의 nxt값에 삽입할 위치 nxt 값을 대입
  if(nxt[addr] != -1) pre[nxt[addr]] = unused; // 맨 마지막 원소에 데이터를 추가할 때를 처리.
  nxt[addr] = unused; // 삽입한 인덱스의 다음은 unused 
  unused++; // 새로 할당할 수 있는 인덱스 증가시키기 
}

void erase(int addr){
  nxt[pre[addr]] = nxt[addr]; // 이전 노드의 nxt에 삭제할 노드의 nxt할당. 
  if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr]; // 삭제할 노드가 마지막이 아닌 경우 처리. 
}

왜 pre[addr]이 -1인지는 체크를 하지 않아도 되는데 nxt[addr]이 -1인지는 체크를 해야 할까?

더미노드가 존재하니까 pre[addr]는 항상 -1이 아니다. 
맨 마지막 원소일 경우 nxt[addr]가   -1일 수 있기 때문이다. 

0x02 STL list

vector와 비슷한 것이 많다. 

push_back, pop_back, push_front, pop_front는 모두 O(1)의 시간복잡도다. 

iterator가 주소 역할을 한다! 매우 유용함.

int main(void) {

    ios_base::sync_with_stdio(0);
    cin.ignore(0);

    list<int> L = {1, 2}; // 1, 2  
    list<int>::iterator t = L.begin(); // t는 1을 가리킨다. 
    
    L.push_front(10); // 10, 1, 2
    cout << *t << '\n'; // t는 1을 가리키니까, 1이 출력된다. 
    
    L.push_back(5); // 10, 1, 2, 5
    L.insert(t, 6); // t가 가리키는 곳 앞에 6을 삽입한다. 10, 6, 1, 2, 5
    t++; // t를 한 칸 뒤쪽으로 보낸다. t는 2를 가리킨다. 
    
    t = L.erase(t); // t가 가리키는 값을 제거하고, 그 다음 원소의 위치를 반환한다. 
    // 2를 제거하고 t는 5를 가리키게 된다. 10, 6, 1, 5
                    
    cout << *t << '\n'; // 5 
    
    // 순회하며 출력 
    for(auto i : L) cout << i << ' ';
    cout << '\n';
    
    for(list<int>::iterator it = L.begin(); it != L.end(); it++)
        cout << *it << ' ';
    
    return 0;

}

list::iterator라는 type을 치기가 귀찮으면 C++11 이상일 때 auto t = L.begin()으로 써도 된다. 

0x03 연습문제

연습문제를 풀어보고, 손코딩 문제는 잠시 생각해보고 답해보자. 

BOJ 1406번 에디터

BOJ 5397번 키로거 

BOJ 1158번 요세푸스 문제 

손코딩 문제 1 
원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때, 해당 리스트의 길이를 효율적으로 구하는 방법? 

정답
동일한 노드가 나올때 까지 계속 다음 노드로 가면 됨. 
공간복잡도 O(1)
시간복잡도 O(N)

손코딩문제 2 
중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법은? 

정답 
일단 각 리스트의 길이를 구한다. 
더 긴 리스트에서 둘의 길이 차이 만큼 앞으로 이동시켜 놓는다. 
두 시작점이 만날 때 까지 두 시작점을 동시에 한 칸씩 전진 시키면 된다. 

손코딩문제 3 
주어진 연결 리스트 안에 사이클이 있는지 판단하라. 

정답 
Floyd’s cycle-finding algorithm, 공간복잡도 O(1), 시간복잡도 O(N)
한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시킨다. 
사이클이 없으면, 두 커서가 만나지 못하고 연결리스트의 끝에 도달한다. 
사이클이 있으면, 두 커서는 반드시 만나게 된다. 
거치는 모든 노드를 저장할 필요가 없다.  

다음 시간에는 스택을 공부한다. 

공부 내용 출처 : 바킹독 알고리즘 연결 리스트  

목차

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