정의와 성질

연결 리스트의 성질

k번째 원소를 확인/변경하기 위해 O(k)
이미 정한 위치에 추가 및 제거는 O(1)
메모상에 연속된 데이터는 아니라서 cache hit rate는 낮고, 할당은 쉬움

연결리스트 종류

단일 연결 리스트
이중 연결 리스트 : 양방향으로 연결되어 있어서 이전 이후 원소 주소를 둘 다 들고 있다.
원형 연결 리스트 : 사이클 돈다 생각하면 편하다.

기능과 구현

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

손코딩 문제 1

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

효율적으로 구하라 -> 시간복잡도와 공간복잡도를 생각해봐야 한다. 동일한 노드가 나올 때까지 계속 다음 노드로 가면 된다. O(1), O(N)

손코딩 문제 2

각 연결 포인터가 가리키는 주소가 같아지는 순간이 교차점인데 A,B의 길이가 다르니까 더 긴 길이를 차만큼 빼줘서 동시에 도달할 수 있도록 한다. O(A+B)로 전체 노드 길이를 알기위한 순회는 필요하다.

손코딩 문제 3

주어진 연결 리스트 안에 사이클이 있는지 판단하라. O(N)으로 주소 다 기록해놓고 이전에 나왔던 주소가 있는지 체킹하면 될 거 같은데.. 공간 복잡도 O(1) 방법이 있다고 한다. Floyd’s cycle-finding algorithm으로 한 칸씩 이동하는 slow pointer와 두 칸씩 이동하는 fast pointer를 두면 사이클 내에서 꼭 같은 노드에서 만나게 된다.

야매 연결 리스트 예시

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

const int MX = 1000005;
char dat[MX];
int pre[MX]; 
int nxt[MX];
int unused = 1;

void insert(int addr, char num){
  dat[unused] = num;
  pre[unused] = addr;
  nxt[unused] = nxt[addr];
  if(nxt[addr] != -1) pre[nxt[addr]] = unused;
  nxt[addr] = unused;
  unused++;
}

void erase(int addr){
  nxt[pre[addr]] = nxt[addr];
  if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}

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

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  fill(pre,pre+MX,-1);
  fill(nxt,nxt+MX,-1);
  string init;
  cin >> init;
  int cursor = 0;
  for(auto c : init){
    insert(cursor, c);
    cursor++;
  }  
  int q;
  cin >> q;
  while (q--) {
    char op;
    cin >> op;
    if (op == 'P') {
      char add;
      cin >> add;
      insert(cursor, add);
      cursor = nxt[cursor];
    }
    else if (op == 'L') {
      if (pre[cursor] != -1) cursor = pre[cursor];
    }
    else if (op == 'D') {
      if (nxt[cursor] != -1) cursor = nxt[cursor];
    }
    else { // 'B'
      if (pre[cursor] != -1) {
        erase(cursor);
        cursor = pre[cursor];
      }
    }
  }
  traversal();
}

큐

큐 하면 일단 귀신 같이 나와야 하는 것이 선입선출이다. 데이터가 입력되는 순대로 바로 처리하고 싶을 때 효율적인 자료구조이다. 이 큐의 시간복잡도는 O(1)이기 때문이다.

파이썬 : from collections import deque를 사용한다.

from collections import deque

queue = deque()
queue.append(1) # [1]
queue.append(2) # [1, 2]
queue.append(3) # [1, 2, 3]
queue.popleft() # [2, 3]
queue.popleft() # [3]
queue.popleft() # []

java : Queue<String> queue = new LinkedList<>();를 사용한다.

Queue<String> queue = new LinkedList<>();
queue.offer(1); // [1]
queue.offer(2); // [1, 2]
queue.offer(3); // [1, 2, 3]
queue.poll(); // [2, 3]
queue.poll(); // [3]
queue.poll(); // []

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

int main(void){ queue Q; Q.push(9); cout << Q.size() << '\n'; // Q의 사이즈 출력, 지금은 1 Q.push(10); if(Q.empty()) cout<<

}

정의와 성질

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

O(1)에 k번째 원소 확인 가능
오버헤드 거의 없음
hit rate 높음 -> CS 확실히 중요하네..
연속된 자료구조이기 때문에 할당에 제약이 있다 -> 메모리상에도 연속적

기능과 구현

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

void insert(int idx, int num, int arr[], int& len){
  for(int i=len;i>idx;i--) // i가 길이부터 시작이니까 
    arr[i]=arr[i-1]; //i-1이 맞는 위치(?) 맞는 배열의 인덱스, 1번째 원소 인덱스 번호는 0
  arr[idx]=num; //그리고 넣어준다. 
  len++; //len도 하나 늘어난다. 
}

void erase(int idx, int arr[], int& len){
  len--; //길이를 먼저 한 번 지워야 
  for(int i=idx+1;i<len;i++) //여기서 줄인 idx에 맞는 
      arr[i-1]=arr[i];
}

void printArr(int arr[], int& len){
  for(int i = 0; i < len; i++) cout << arr[i] << ' ';
  cout << "\n\n";
}

void insert_test(){
  cout << "***** insert_test *****\n";
  int arr[10] = {10, 20, 30};
  int len = 3;
  insert(3, 40, arr, len); // 10 20 30 40
  printArr(arr, len);
  insert(1, 50, arr, len); // 10 50 20 30 40
  printArr(arr, len);
  insert(0, 15, arr, len); // 15 10 50 20 30 40
  printArr(arr, len);
}

void erase_test(){
  cout << "***** erase_test *****\n";
  int arr[10] = {10, 50, 40, 30, 70, 20};
  int len = 6;
  erase(4, arr, len); // 10 50 40 30 20
  printArr(arr, len);
  erase(1, arr, len); // 10 40 30 20
  printArr(arr, len);
  erase(3, arr, len); // 10 40 30
  printArr(arr, len);
}

int main(void) {
  insert_test();
  erase_test();
}

STL vector

배열과 거의 동일한 기능을 수행하는 자료구조이다. 배열과 마찬가지로 메모리에 연속적으로 원소를 저장하기 때문에 O(1)의 시간복잡도로 접근 가능하다. 배열은 고정 자료구조인 반면, vector는 동적으로 크기를 조절할 수 있다는 장점이 있다.

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

int main(void){
  vector<int> v1(3,5); // {5,5,5} 크기 3으로 초기화값 5인 벡터 생성 
  cout<<v1.size()<<'\n';
  v1.push_back(7); //꼬리에 7 삽입 push 
  
  vector<int> v2(5); //{0,0,0,0,0}
  v2.insert(v2.begin()+1,3); //{0,3,0,0,0,0}

  vector<int> v3 ={1,2,3,4};
  v3.erase(v3.begin()+2); //{1,2,4}

insert, erase는 O(n) push_back, pop_back은 순회가 필요 없으므로 O(1)

vector<int> v1={1,2,3,4,5,6}; //list, map, set 등에서도 모두 사용 가능 
 
for(int e:v1) //int& e:v1이라고 쓰면 for문 내에서 e를 바꿨을 때, 원본 v1도 같이 바뀜
  cout<<e<<' ';

for(int i=0;i<v1.size();i++)
  cout<<v1[i]<<' ';

for(int i=0;i<=v1.size()-1;i++)
  cout<<v1[i]<<' ';

마지막 3번째 예시는 32비트 컴퓨터 기준 런타임에러가 생길 수 있다. vector.size()는 unsigned int 혹은 unsigned long long을 반환한다. 빈 vector일 때 v1.size()-1이 unsigned int 0에서 int 1을 빼는 식이 되고, 이렇게 되면 unsigned int로 자동 형변환이 된다. 때문에 0-1=-1이 아니라 4294967295가 된다(unsigned int의 자료형 범위)

연습 문제

문제 2

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

int func2(int arr[],int N){
  for(int i=0;i<len(arr);i++){
    int occur[101]={};
    for(int i=0;i<N;i++){
      if(occur[100-arr[i]]==1)
        return 1;
      occur[arr[i]]=1;
    }
    return 0;
  }
}

바킹독의 실전 알고리즘 : STL과 함수 인자, 표준 입출력

23 Jan 2026 • Self-study

STL과 함수 인자

void func(int a){
    a=5;
}

int main(void){
    int t=0;
    func(t);
    cout<<t;
}

void func(int arr[]){
    arr[0]=10;
}

int main(void){
    int arr[3]={1,2,3};
    func(arr);
    cout<<arr[0];
}

struct pt{
    int x,y;
};

void func(pt a){
    a.x=10;
}

int main(void){
    pt tmp={0,0};
    func(tmp);
    cout<<tmp.x;
}

3번째 구조체도 변수 넘겨주는 거랑 같게 이해하면 됨 -> 복사

call 방법

call by value -> 안 바뀜, 공간 하나 더 생김
call by address -> 바뀜 (배열)
call by reference -> 바뀜 (구조체)

void swap1(int a, int b);
void swap2(int* a, int* b); //pointer 
void swap3(int& a, int& b); //referencer 

swap1은 그냥 변수 call by value swap2는 주소 전달 swap3는 참조 (넘길 때는 변수 넘기면 됨)

vector<int> v(100);
v[20]=10;
v[60]=-2;

void func1(vector<int> v){
    v[10]=7; //여기에서 값을 바꿨다고
}

int main(void){
    vector<int> v(100);
    func1(v);
    cout << v[10]; //여기서 바뀌진 않음 
}

STL을 함수 인자로 넘길 땐 어떨까.. 는 그냥 call by value call by value는 복사를 하니까 원소마다 다 참조 -> O(n)

bool cmp1 (vector<int> v1, vector<int> v2, int idx){
    return v1[idx] > v2[idx];
}

bool cmp2 (vector<int>& v1, vector<int>& v2, int idx){
    return v1[idx] > v2[idx]; //-> 이건 참조만 하니까 시간복잡도 O(1)
}

유의하자~

표준 입출력

int main(void){
    string s="6kitty";
    printf("s is %s\n",s);
}

int main(void){
    char a[10];
    printf("input: ");
    scanf("%s",a);
    string s(a);
    printf("a is %s\n",a);
    printf("s is %s\n",s.c_str());
}

scanf/printf에서는 C++ string 처리가 안되다. -> 개귀찮으니까 그냥 cin/cout 쓰자

아 그리고 공백 포함은 그냥 받으면 안된다

// 1. scanf 
char a[10];
scanf("%[^\n]", a);

// 2. getline 
string s;
getline(cin,s);
cout<<s;

getline 쓸 때는 string형만 올 수 있다는 걸 유념하자. cin/cout에서 주의해야할 것이 하나 더 있다. 입출력으로 인한 시간초과를 막기 위해 ios::sync_with_stdio(0), cin.ie(0) 명령을 실행해줘야 한다.

int main(void){
    ios::sync_with_stdio(0);
    cout<<"1111\n";
    printf("1111\n")
}

C++ stream과 C stream은 동기화되어 있다. 그런데 내가 cin/cout만 사용할 것이라면 두 동기화하는 시간이 필요 없어지기에 ios::sync_with_stdio(0)로 싱크를 굳이 하지 않는다.

대신 cout, printf를 섞어쓰면 안됨 -> 오류가 나는 건 아니고 순서가 꼬인다.

cin을 위해서는 cin.tie(0)가 필요하다. 문자를 입력하면 입력 버퍼에 모았다가 변수로 넘겨준다. 즉각적으로 메모리에 담기는 것이 아닌 버퍼라는 중간 매개체가 있다. 입출력이 같은 버퍼를 쓰고 있기 때문에 순서가 꼬일 수 있다. 때문에 cin 명령 수행 전에 cout 버퍼를 지워야 한다. 그렇지만 저지 채점할 때는 단순 출력 글자로만 채점하기 때문에 굳이 순서 꼬이지 않게 전처리 하지 않아도 된다. -> 굳이 cout 버퍼를 비우는 수고를 할 필요가 없다.

그리고 endl 쓰지 말아야 한다. -> 시간 소모가 꽤 되나 봄

6kittylog

Life2

바킹독의 실전 알고리즘 : 연결 리스트

정의와 성질

연결리스트 종류

기능과 구현

손코딩 문제 1

손코딩 문제 2

손코딩 문제 3

야매 연결 리스트 예시

알고달레: 큐

큐

바킹독의 실전 알고리즘 : 배열

정의와 성질

기능과 구현

STL vector

연습 문제

문제 2

바킹독의 실전 알고리즘 : STL과 함수 인자, 표준 입출력

STL과 함수 인자

call 방법

표준 입출력