안 쓰던 블로그

[정렬과 이분탐색] 1920 수 찾기 #include #include #include #include using namespace std; vector v; int n; int find(int num) { int s = 0, e = n - 1; while (s > n; for (int i = 0; i > a; v.push_back(a); } //int m; cin >> m; //for (int i = 0; i > a; //auto it = find(v.begin(), v.end(), a); //if (it == v.end()) cout a; cout n; for(int i=0;i> x; a[x]++; //인덱스 증가..

10610 30 #include #include #include #include using namespace std; /* "길거리에서 찾은 수에 포함된 숫자들을 섞어, 30의 배수가 되는 가장 큰 수를 만든다" 처음에 문제를 봤을 때는 주어진 N값을 소인수분해해서 나온 여러 숫자들을 어케 잘 연산해서 30의 배수를 만드는 줄 알았다. 그런데 무한히 더해버리면 무한히 큰 30의 배수를 만들 수 있기 때문에 이건 아니었다 예제를 다시 보니까 "포함된 숫자"라는 의미가 주어진 N의 각각 자리수를 의미하는 것이었다 그리고 각 자리수를 어케 잘 재배치해서 가장 큰 30의 배수를 만들면 된다 30의 배수가 될 조건을 만족하는지 확인하고 각 자리수를 큰 수부터 재배치한다 30의 배수가 될 조건 1. 끝자리가 0 2..

1676 팩토리얼 0의 개수 #include #include #include #include using namespace std; int n, m; /* 2와 5를 곱할 때만 0이 생긴다 5보다 2가 많으니까 5만 세면 된다 근데 5의 배수가 예외 5*2=10 5*5*2*2=100 5*5*5*2^3=1000 2는 충분히 많다고 칠 수 있으므로(소인수분해 하면 2가 잔뜩나온다) 5의 배수는 1개씩 늘 때마다 0의 개수가 1개씩 증가되며 추가된다고 볼 수 있다 5^4=625는 문제 범위인 500을 넘으므로 패스 */ int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; while (n >= 2) { if (n % ..

약수 1: https://www.acmicpc.net/problem/4375 약수: https://www.acmicpc.net/problem/1037 C가 A의 약수라면, A/C도 A의 약수가 되어야 한다 C=3, A=24라면, 24/3=8도 24의 약수가 되어야 한다 그러면 중간을 기준으로 대칭을 이루게 된다 이 아이디어로 전체 약수를 구할 때 더 빠르게 구할 수 있다 전체 약수 구하기 1. 1~A로 모두 나눠보기: O(A)걸림. N개 수에 대해서 연산하므로 N*O(N) = O(N^2) 2. 1~루트(A)로 모두 나눠보기: O(루트(A))걸림. N개 수에 대해서 연산하면 N*O(루트(N))=O(N*루트(N)) 이런 아이디어는 범위가 클 때 사용 가능하다 N

문제 설명 입력으로 a, b가 들어오는데, b와 b+1을 잇는 사다리가 a에 있다는 의미 위에 그림으로 보면 2, 3이면 3과 4사이를 잇는 2 위치에 사다리가 있다는 의미임 가로선을 최소로 추가해서 i번 세로선의 결과를 i로 만드는 문제 세로선의 개수는 2> y >> x; map[y - 1][x] = true; //y-1번째 col에서 x~x+1을 잇는 사다리 } go(0, 0); if (res == 1e9) cout

그래프에서 사이클 구간 찾는 문제 문제 이해 자체는 쉬운데 구현이 어려웠다 사이클을 찾아야 하는데, 다른 사람들 글을 보니까 finish배열을 써서 finish가 체크가 아닌데 visit는 체크이면 사이클이고 그런다던데 뭔소린지 직관적으로 이해되지 않아서 이해하는 데 좀 걸렸다 1. 사이클 확인 그래서 내 나름대로 이해해 보았는데, finish배열말고 아래처럼 생각하면 좋더라 void dfs(int now) { int next = v[now]; //가리키는 거 if (visit[next]) { //방문을 했던 노드인데 또 탐색하러 오게 되면 사이클이다 //구현 } visit[now] = 1; dfs(next); //다음 경로 } dfs를 돌면서 보통 이렇게 방문을 체크하고, 방문하지 않았으면 dfs를 또..

이분 그래프란? 정점에 색깔을 부여한다고 할 때, 절반씩 그룹으로 나눌 수 있는 그래프. 인접한 정점끼리 색깔이 같으면 안 된다 골4 문제이지만 이제까지 풀어왔던 dfs, bfs처럼 탐색으로 풀 수 있다 1. 탐색하면서 그래프에 색깔(1, 2)을 부여한다. visit를 체크할 때 방문/미방문이 아닌, 미방문/색1/색2 이렇게 세 가지로 주면 된다 위에 그림에서는 문제의 예시로 있는 두 케이스를 그림으로 그린 것이다 O가 색1, X가 색2라고 했을 때, 탐색이 끝나면 각 정점에 대해 O또는 X가 전부 부여된다(미방문이 없을 때까지 탐색) 2. 각 정점에 연결된 정점들을 확인하며 색1의 연속, 색2의 연속인 경우가 있는지 체크한다 각 정점에 연결된 정점들을 이중for문으로 확인하며 OO또는 XX가 나오면 이..