알고리즘/공부

[바킹독 알고리즘] 0x18강 : 그래프

그래프 정의 정점과 간선으로 이루어진 자료구조 간과하기 쉬운 그래프 : 루프가 존재하는 그래프, 연결 그래프가 아닌 경우 (도 생각해야한다.) 그래프 표현법 1. 인접 행렬 vertex * vertex의 2차원 배열을 만들어서 각 vertex의 간선이 존재하면 양방향일 경우 두 vertex에 각 칸을 전부 1로 세팅, 단방향일 경우 해당 칸에만 1로 set해서 그래프를 표현할 수 있다. 2. 인접 리스트 인접 리스트를 표현할 때 Kotlin에서는 LinkedList를 실제로 사용하면 되지만, C++의 경우 Vector를 사용해도 무관하다. ( 그렇다면 Kotlin에서도 Pair 로 사용하면 되지 않을까? 싶다..) 그래프에서 BFS와 DFS 1. BFS using Queue 만약 위 예시처럼 연결그래프가..

[바킹독 알고리즘] 0x10강:다이나믹 프로그래밍

다이나믹 프로그래밍 (Dynamic Programming, DP) : 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 위 사진과 같이 피보나치 수열을 DP를 이용해서 배열로 문제를 풀 수 있다.\ 배열에 하위 값들에 대한 정보를 저장하고 있으면, 상위 문제를 풀 때 배열에 저장된 값을 이용해서 풀 수 있기 때문에 재귀보다 훨씬 수행시간이 줄어든다. DP를 푸는 과정 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기

[바킹독 알고리즘] 0x0A강:DFS in 다차원 배열

DFS: 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 사진만으로 이해가 어렵다면 바킹독 알고리즘 영상을 직접 보면 이해가 더욱 쉬울 것이다. 정리 1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김 2. 스택에서 원소를 꺼내어 그 칸과 상후좌우로 인접한 칸에 대해 3번을 진행 3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문표시를 남기고 해당 칸을 스택에 삽입 4. 스택이 빌 때 까지 2번을 반복 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개 일 때 O(N) DFS 구현 코드 #include using namespace std; #define X first #define Y second int board[502][502] = {{1..

[알고리즘] 이진탐색 알고리즘 (Binary Search)

이진탐색 알고리즘 (Binary Search) 란? 정렬된 배열에서 검색 범위를 반으로 줄여나가면서 해당 값이 배열안에 있는지를 찾는 알고리즘이다. 이진탐색 알고리즘은 반드시 정렬된 배열에서만 사용할 수 있다. 예시로 A라는 값을 찾으려고 할 때 맨 처음 A와 중간 값을 비교하고, A가 더 크다면 중간에서 오른쪽을 탐색, A가 작다면 중간에서 왼쪽을 범위로 탐색을 한다. 이 과정을 반복하여 해당 값이 있는지를 찾아낸다. 사진과 같이 이진탐색이 이루어진다. 이진탐색 코드 구현 #include #include using namespace std; bool compare(int a, int b) { return a < b; } int main() { ios::sync_with_stdio(0); cin.tie(..

[바킹독 알고리즘] 0x09강:BFS in 다차원 배열

BFS: 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 사진만으로 이해가 어렵다면 바킹독 알고리즘 영상을 직접 보면 이해가 더욱 쉬울 것이다. 정리 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남긴다. 2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행한다. 3. 해당 칸을 이전에 방문했다면 아무 것도 하지않고, 처음으로 방문했다면 방문표시를 남기고 해당 칸을 큐에 삽입한다. 4. 큐가 빌때까지 2번을 반복한다. 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. BFS 구현 코드 ver C++ #include #include using namespace std; #define X first #define Y second int..

[바킹독 알고리즘] 0x08강:스택의 활용(수식의 괄호 쌍)

수식의 괄호쌍이란? 주어진 괄호, 문자열이 올바른지 아닌지 판단하는 문제이다. 첫번째 예시의 괄호쌍만 본다면 {()} 로 올바른 괄호쌍이지만, 두번째는 {(})로 올바르지 않은 괄호쌍이다. 문제 해결을 위한 관찰 괄호쌍들이 잘 짝을 이루었는지를 판단하려면 " 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라 생각해도 된다." (대박 이렇게 생각하면 stack으로 문제를 풀 수 있는거같다.) 문제 해결방법 위 방법을 문제에 활용해 stack에 적용하면 문제를 해결할 수 있다. 결론적으로 stack의 empty() 여부로 올바른 짝인지 아닌지 확인 할 수 있다.!! 문제현황 연습 문제 ✔ 4949 균형잡힌 세상 정답 코드 기본 ..

[바킹독 알고리즘] 0x07강:Deque

덱 Deque : 양쪽 끝에서 삽입과 삭제 모두 가능 성질 1. 원소의 추가,제거 O(1) 2. 제일 앞/뒤 원소 확인 O(1) 3. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 구현 덱의 Head와 Tail의 초기값이 MX인 이유는 헤드와 테일에서 모두 삽입삭제가 가능하기 때문이다. 위 이미지와같이 삽입/삭제가 일어나기 때문에 H가 0 일경우 더이상 왼쪽으로 삽입 할 수 없어서 MX로 잡아둔다. (선형으로 구현) #include using namespace std; const int MX = 100005; int dat[2 * MX + 1]; int head = MX, tail = MX; void push_front(int x) { dat[--head] = x; //앞에다 삽입하는..

[바킹독 알고리즘] 0x06강:Queue

Queue: FIFO (First In First Out) 성질 원소 추가 O(1) , 제거 O(1) 제일 앞/뒤 원소 확인 O(1) 나머지 원소 확인 변경이 원칙적으로 불가 // 큐의 원소가 들어가는 배열을 원형으로 만들어서 불필요한 공간낭비를 줄임. const int MX=10000005; int dat[MX]; int head=0, tail=0; void push(int x){ dat[tail++] = x; } void pop(){ head++; } int front() { return dat[head]; } int back() { return dat[tail]; } void test() { push(10); push(20); push(30); cout

[바킹독 알고리즘] 0x05강:Stack

Stack : Last In First Out 원소의 추가, 제거 O(1) 제일 상단 원소 확인 O(1) 제일 상단이 아닌 나머지 원소 확인/변경 원칙적으로 불가능 배열로 스택 구현 #include using namespace std; const int MX=10000005; int dat[MX]; int pos = 0; //삽입해야할 index void push(int x){ dat[pos++]=x; } void pop() { pos--; } int top(){ return data[pos-1]; } STL 스택 문제 현황 연습 문제 ✔ 10828 스택 정답 코드 기본 문제 ✔ 10773 제로 정답 코드 응용 문제 1874 스택 수열 정답 코드 응용 문제 ✔ 2493 탑 정답 코드 응용 문제 ✔ 619..

[바킹독 알고리즘] 0x04강:Linked List

연결리스트 성질 k 번째 원소 확인/변경 위해 O(k) 필요 임의의 위치에 원소 추가, 제거가 O(1) (추가/제거하는 위치를 알고있는 경우) Cache rate hit은 낮지만 할당이 좋다. → 임의의 위치에 원소 추가하거나 제거하는 연산이 많을경우 연결리스트 사용 좋다. 연결리스트 종류: 단일 연결리스트/이중연결 리스트/환형 연결리스트 배열 vs 연결리스트 연결리스트 구현 #include 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] = ..

[바킹독 알고리즘] 0x03강:Array

연습문제: O(1)에 배열 안 원소 중 2개의 합이 100인게 존재하는지 확인하기 int func2(int arr[], int len) { int occur[101] = {}; for (int i = 0; i < len; i++) { if (occur[100 - arr[i]] == 1) { return 1; } occur[arr[i]] = 1; } return 0; } 0~100까지 인덱스가 있는 배열을 만듬 내가 입력한 배열을 돌면서 원소에 해당하는 값을 occur 배열 인덱스 값으로 1을 추가함. 만약에 100-해당 원소 가 occur 배열에서 1 값을 가지고 있으면 합 100이 가능한 원소가 존재한다는 뜻 따라서 존재여부로 O(1)에 값을 구할 수 있다. 문제 풀이 현황 연습 문제✔ 10808 알파..

[바킹독 알고리즘] 0x02강:STL

STL과 함수 인자 stl 벡터를 함수 인자로 넘길때 이를 복사하는 과정이 필요하기 때문에 O(N) 걸림 하지만 레퍼런스 사용시 그 과정이 생략되어 우리가 생각하는 것처럼 O(1)이 걸린다. 표준 입출력 공백포함된 함수를 입력 받을땐 scanf/ cin 안됨 → 둘다 공백 앞까지만 입력으로 받기 때문 → 따라서 getline을 사용하자! c에 printf나 scanf 안쓸꺼면 ios::sync_with_stdio(0) 사용하기 (sync를 끊는다는 뜻) cin.tie(0) : cin 사용 시 cout 버퍼를 비울 필요가 없기 때문에 이를 사용. endl : 사용하지 말기.. 개행하고 버퍼 비우는 명령어이므로 할 필요가 없다.