쌓고 쌓다

스택의 특징 LIFO ( Last-In First-Out ) : 후입선출로 가장 늦게(최근에) 들어온 데이터가 가장 먼저 나감 프링글스 통을 스택이라고 생각하자 스택 ADT is_empty(s) : 스택이 비어있는지 검사 is_full(s) : 스택이 가득 찼는지 검사 push(s, e) : 스택의 맨 위에 요소 e를 추가 pop(s) : 스택 맨 위의 요소 삭제 스택 생성 #define MAX_SIZE 10 typedef int element; // 추후 int형 스택을 다른 자료형으로 바꿀때 이부분만 수정하면 편리함 typedef struct { element stack[MAX_SIZE]; int top; }StackType; init 함수 void init(StackType* s) { s->top ..

희소행렬을 2차원 배열을 통해 전체를(0도 포함해서) 저장해버리는 방법 장점: 행렬의 연산이 간단해진다. 단점: 대부분의 항이 0인데 메모리 낭비이다. 0이 아닌 요소들만 구조체를 이용해서 저장하자 장점: 메모리 공간 절약 단점: 행렬의 연산들의 구현이 복잡 아래의 코드는 구조체를 이용해 0이 아닌 요소들만 있는 행렬의 덧셈을 하는 코드이다. #include using namespace std; #define ROWS 3 #define COLS 3 #define MAX_TERMS 10 typedef struct Element { int row; int col; int value; }Element; typedef struct sparse_matrix { Element data[MAX_TERMS]; int ..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net #include #include using namespace std; int T[1500001]; int P[1500001]; int dp[1500051]; int N,res=0; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i > T[i..

https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net #include #include #include using namespace std; long long dp[101][101]; int N, M, K; string res = ""; long long Count(int a, int z) { if (a == 0 || z == 0) return 1; if (dp[a][z] != 0) return dp[a][z]; return dp[a][z] = min(Count..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net #include #include #include #include using namespace std; int parent[100001]; int N,res; vector v[3]; // 좌표,i번째 행성 vector planet; // dis,A번째 행성,B번째 행성 int Find(int x) { if (parent[x] == x) return x; return ..

https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net #include #include using namespace std; queue q; int arr[50][50]; int visit[50][50]; int side[4][2] = { {-1,0},{1,0},{0,-1},{0,1} }; int res = 987654321; int N; void BFS() { q.push(make_pair(0, make_pair(0, 0))); visit[0][0]..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net #include #include #include #include using namespace std; vector v; int N; int arr[101]; bool visit[101]; void DFS(int start, int cur) { if (visit[cur]) { if (start == cur) v.push_back(arr[start]); return; } visit[cur..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net #include #include using namespace std; bool visit[2001]; int res = 0; int N,M; vector v[2001]; void DFS(int cur, int cnt) { if (cnt == 5) // A,B,C,D,E 5명이 연결이 되었으므로 가능함 { res = 1; return; } for (int i = 0; i < v[cur].size(); i++) { if (visit[v[cur][i]] == false) { visit[v[cur][i]] =..