Hoon222y

#include #include #include #include #include #include #include #include #include #include #include #include #define INF 1000000000 using namespace std; vector tree;vector a;vector lazy; int n, m, k; long long init(int node,long long x,long long y){ if (x == y) return tree[node] = a[x]; return tree[node] = init(node * 2, x, (x + y) / 2) + init(node * 2 + 1, (x + y) / 2 + 1, y);} void update_lazy(..

이분탐색의 경우에는 - 정렬되어진 리스트에서 어떤값을 빠르게 찾는 알고리즘으로서 - 리스트 혹은 배열의 크기를 N 이라고 했을 때 찾는데 logN 의 시간이 걸린다.이런식으로 작동이 되며 Left가 Right 보다 클 때 까지 계속적으로 반복을한다. 시간복잡도가 logN인 이유가 바로 절반으로 계속 나누어 주기 때문이다.참고 코드는 while (left x) { right = mid-1; } else { left = mid+1; } }을 참고하면 될 것이다.그런데 분명 이렇게 구현을 하다보면 까먹을 경우도 발생 할 것이다. 그렇다면 우리는 어떻게 해야할까 ... 바로 STL을 쓰는게 가장 간편 !!while (m--) { int num; scanf("%d",&num); printf("%d ",binary..

보통 dfs나 bfs를 하면 2차원 배열상에서 이동하는 경우가 생기는데 그때마다 같은 코드를 반복하지 않고 for문으로 해결할 수 있다.12345678910111213141516171819202122232425262728293031#include #include using namespace std;//4방향 탐색int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int arr[100][100];int N,M;queue q; //범위를 벗어나는지 확인해주는 chkbool chk(int a,int b){ return 0

int main(){ for(int i=0;i> str; for(int i=0;i

int n, b; cin >> n >> b; string ans = ""; //이것도 포인트 ! 추가하는 방식으로 할 수 있음을 알게되었다. while (n > 0) { int r = n % b; if (r < 10) { ans += (char)(r + '0'); //숫자인 경우는 그냥 '0'을 더함으로서 숫자로 넣을 수 있고 } else { ans += (char)(r - 10 + 'A'); // 그 진법을 넘어서 알파벳으로 표현하게 되는경우 -10 +'A'를 해주면 된다. } n /= b; } reverse(ans.begin(),ans.end()); cout

다이나믹 프로그래밍이라는 이야기는 많이 들어보았지만 ... 아직도 잘 와닿지 않고 막상 문제를 풀려고 할 때마다 어려운 부분이 바로 DP일 것이다.거창해 보이는 이름과는 달리 간단하게 생각하여 2가지 조건을 만족한다면 DP로 접근을 한다고 생각하면 쉬울것이다.1) overlapping subproblem (겹치는 부분문제)2) Optimal substructure (최적 부분 구조) 이다.겹치는 부분문제의 경우에는 피보나치 수열을 생각하면 쉽다. 피보나치 수열을 구하기 위해서는 예 n번째 수를 구하기 위해서 n-1, n-2의 값을 구해야 하는것처럼 말이다. 다이나믹 프로그래밍에서는 각 문제를 한번만 풀어야한다. 같은 문제는 구할 때마다 정답이 같기때문이다. 따라서 정답을 한번 구했으면 어딘가에 메모해놓게..

그래프의 탐색은 대표적으로 2가지로 나눌수 있다.1) DFS(깊이 우선 탐색)2) BFS(너비 우선 탐색)두 종류 모두 모든 정점을 1번씩 방문한다는 목표가 있기는 하지만 방문하는 방법에 있어서 차이가 존재한다. 먼저 DFS에 대해 알아보도록 하자. DFS의 경우에는 스텍을 이용하여 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정점으로 돌아가는 방식이다.위에 그림을 통해 이해를 하자면 원래 스텍에 12345 이렇게 들어있다가 5에서 더이상 갈 곳이 없어서 5가 제거되고 6이 들어온 모습을 나타낸 것이다. 그렇게 4 3 2 1순으로 다시 계속 돌아오는 것이다.보통 DFS의 경우에는 재귀호출을 통하여 구현한다. 코드를 간단하게 작성하자면 12345678void dfs(int x) { check[..

Graph란 자료구조의 일종으로서 정점(Node,vertex)과 간선(Edge)으로 이루어져 있다. G = (V,E) 이렇게 표현을 한다. 이러한 그래프들은 방향이 있는 그래프(유향 그래프)와 방향이 없는 그래프(무향 그래프)로 나눌 수 있다.때때로 간선에 가중치가 주어질 수 있는데 A에서 B 로 이동하는 거리, 이동하는데 걸리는 시간등을 표현할 수 있다. 그래프를 표현할 수 있는 방법은 두가지 정도로 나누어 볼 수있다.1) 인접 행렬을 이용한 표현2) 인접 리스트를 이용한 표현 인접 행렬을 이용한 표현의 경우에는 위의 사진처럼 2차원 배열에 각각의 연결성을 따지는 것이다. 코드로 표현하자면 for (int i=0; i

Tree란 자료구조의 일종으로서 사이클이 없는 그래프라고 볼 수 있다.이때 정점의 개수를 V 개라고 하면 간선의 개수는 v-1개 가 된다.자식을 최대 2개만 가지고 있는 트리를 이진트리라고 한다. 트리를 표현하는 방법은 1) 그래프의 일종이기 때문에 그래프의 표현과 같은 방식으로 저장.2) 트리의 모든 노드는 부모를 하나 혹은 0개를 가지고 있으므로 각각의 부모를 저장하는 방법이 있다.이진트리의 경우에는 다른 그래프들과 달리 배열로 표현이 가능한데 이러식으로 부모의 노드가 x인 경우 자식으 노드는 2x, 2x+1로 표현이 가능하다. 혹은 A[i][0]에 왼쪽자식을 , A[i][1]에 오른쪽 자식을 저정하는 방법을 사용 할 수도 있다. 트리 순회의 종류에는 3가지가 있는데 이런식이다 ㅎㅎ.... 그림 그리..