분류 전체보기
-
c언어로 stack, queue 구현잡다한 지식 2020. 9. 8. 23:27
c언어에는 c++처럼 , STL이 없어서 직접 배열이나 리스트를 통해 구현해야한다. 1. stack 구현 1) 배열 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include using namespace std;#define MAX 100 int stack[MAX];int top = -1; //스택이 가득 찼는지 확인하는 함수bool IsFull() { if (top >= MAX - 1) return true; return false;}//스택이 비어있는지 확인하는 함수bool IsEmpty() { if (top top = NULL;}bool IsEmpty(Stack *st) { if (st-..
-
c++ string 변환잡다한 지식 2020. 9. 7. 22:05
자료형 변환 함수 1. string을 int형으로 : stoi(string 변수); 2. int를 string으로 : to_string(int 변수); 3. string을 char*로 : string 변수.c_str();ex) string s = "tomato"; char *ch; ch = s.c_str(); 4. char*을 string으로 : 그냥 바로 넣으면됨ex) char *ch = "Hello"; string s =""; s= ch; 5. char*을 int형으로 : atoi(char*변수)
-
[백준] 4013번 ATM문제 풀이 2020. 9. 5. 19:32
4013 ATM 문제) https://www.acmicpc.net/problem/4013 풀이)SCC, dp를 이용해서 푸는 어려웠던 문제였다. 같은 간선을 여러번 사용할 수 있기 때문에,임의의 정점을 방문한다고 할때 그 정점이 속한 SCC내의 모든 정점을 방문해서 최대 현금을 구한다. 과정1. kosaraju algorithm을 이용해 SCC을 구한다. SCC를 구할때, 각 정점이 어떤 SCC에 속하는지 표시해준다 //int node[i] => i 번 정점이 속하는 SCC번호 각 정점이 속하는 SCC의 총 현금을 저장해준다 //int scc[i] => i 번 SCC의 총 현금, 즉 SCC에 속한 정점들의 현금 합 SCC 끼리 연결될 수 있다면, 그 연결 간선을 저장해준다 //vector adj_scc[..
-
c 라이브러리잡다한 지식 2020. 9. 4. 19:12
주로 사용하는 라이브러리와 관련 함수 1. : 표준 입출력① scanf() : 입력 // %d int, %lld long long, %f float, %lf double, %c char② printf() : 출력③ getchar() :문자하나입력ex) char ch = getchar(); 2. : 문자열 함수① strcpy(대상문자열, 원본문자열) : 문자열을 다른 배열이나 포인터(메모리)로 복사ex) char s1[10] = "Hello"; //마지막에 NULL문자들어감 char s2[10]; strcpy(s2,s1); // s1의 문자열을 s2에 복사 printf("%s\n", s2); ② strlen(문자열포인터 or 문자배열) : 문자열 길이를 반환, NULL부분 포함하지 않고 순수하게 문자열 길..
-
SCC-Kosaraju알고리즘 2020. 9. 3. 17:28
SCC(Strongly Connected Component) - 개념 : 방향그래프의 connected component 내 노드 u에서 v로 향하는 경로, 노드 v에서 u로 향하는 경로가 존재하면 해당 connected component를 SCC라 한다. (Connected component : 그래프는 여러개의 부분 그래프로 구성될 수 있는데 서로 연결되어 있는 여러개의 고립된 부분 그래프 각각을 connected component) - SCC를 찾는 알고리즘 Kosaraju's Algorithm : 2번의 DFS를 통해 SCC를 찾는다. 과정 1. digraph G에서 임의의 정점 i부터 dfs 수행 수행 속에서 먼저 끝나는 즉 다른 곳에 갈 곳이 없는 vertex를 stack에 push 하여 저장..
-
[백준] 13511번 트리와 쿼리 2문제 풀이 2020. 9. 2. 01:15
13511 트리와 쿼리 2 문제N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다.아래의 두 쿼리를 수행하는 프로그램을 작성하시오* 1 u v: u에서 v로 가는 경로의 비용을 출력한다.* 2 u v k: u에서 v로 가는 경로에 존재하는 정점 중에서 k번째 정점을 출력한다. k는 u에서 v로 가는 경로에 포함된 정점의 수보다 작거나 같다. 입력첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.둘째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v와 간선의 비용 w가 주어진다.다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.다음 M개의 줄..
-
[백준] 17435번 합성함수와 쿼리문제 풀이 2020. 9. 1. 18:25
17435 합성함수와 쿼리 문제함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자.* f1(x) = f(x)* fn+1(x) = f(fn(x))예를 들어 f4(1) = f(f(f(f(1))))이다.n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하시오. 입력첫 줄에 정수 m이 주어진다. (1 ≤ m ≤ 200,000)다음 줄에 f(1), f(2), ..., f(m)이 차례대로 주어진다.다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)다음 Q개의 줄에 각각 정수 n과 x가 주어진다. (1 ≤ n ≤ 500,000; 1 ≤ x ≤ m) 출력주어지는 ..