알고리즘문제풀이 (38) 썸네일형 리스트형 [백준 10845]큐-연결리스트로 구현하기 www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net #include #include #include using namespace std; typedef struct node { int value; node *next; }node; typedef struct Que { node *front = 0; node *end=0; int cnt; }Que; void init(Que *que) { que->front=que->end=NULL; //front:.. [백준 2042] 구간 합 구하기 (1).인덱스 트리 #include using namespace std; int N, M, K; long long int arr[4000001]; void update(long long int a,long long int b) { int diff = b - arr[a]; arr[a] = b; a >>= 1; while (a) { arr[a] += diff; a >>= 1; } } long long int hap(long long int a, long long int b) { //cout [백준11438 ]LCA2 #include #include #include using namespace std; vectorg[100001]; int depth[100001]; int dp[100001][30]; int visit[100001]; int n; void dfs(int v,int d) //깊이 구하기 { visit[v] = 1; depth[v] = d; for (int i = 0; i = 1;.. [백준1158]조세퍼스문제 -연결리스트로 구현해보기 https://www.acmicpc.net/problem/1158 1158번: 조세퍼스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net STL Que를 써서 구현할수도 있지만, que를 직접 구현해보면서 풀기에 좋은문제라고 생각한다 #include using namespace std; #define INF 987654321 struct Node { int data; struct Node *next; }; struct LinkedQueue { Node *front, *rear; int len=0; LinkedQueue() //구조체의 초기값 정하기 { front == rear == NULL; //처음에 가리키는 노드 없으니.. KMP알고리즘-문자열 찾기 #include using namespace std; //해당 문자열 인덱스 찾기 char arr[20]; char Find[10]; int ans[20]; //같은 문자열의 최초 인덱스 넣을 곳 int cnt = 0; int pi[20]; void FalseFunction(int len) // 패턴 찾기 { pi[0] = -1; pi[1] = 0; //초기화 테이블 int i= 0; int j = 1; while (j next_permutation STL 구현 int next_permutation(int n) //stl구현 { int i = n - 1; while (i > 0 && arr[i] [백준 2252]줄세우기 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의.. 위상정렬 출처:https://www.youtube.com/watch?v=qzfeVeajuyc //위상정렬-순서가 정해져있는 작업, 차례로 수행해야하는 작업을 수행해야할떼 그 순서를 결정해주기위해 사용하는 알고리즘 //사이클이 발생하지 않는 방향그래프에서 작업 //사이클이 발생하면 위상정렬을 수행하지 못한다. //위상정렬이 가능한지 //위상정렬이 가능하다면 그 결과는 무엇인지 //수행방식->스택 및 큐가 있는데 큐를 더 선호 //진입차수- 현재 노드에 들어오는 간선 개수 //1.진입차수가 0인 정점을 큐에 삽입 //2.큐에서 원소를 꺼내 연결된 모든 간선을 제거 //3.간선 제거 이후에 진입차수가 0이 된 정점을 큐에 다시 삽입 //4.큐가빌때까지 2번~3번과정을 반복 //단, 모든 원소를 방문하기전에 큐가 빈다면.. 이전 1 2 3 4 5 다음
