쌓고 쌓다

XOR 연산은 두 비트가 다르면 1, 같으면 0을 반환한다. 비트 두개를 더한다고 생각할때 올림수를 제외하여 생각하면 XOR 연산 결과와 동일하다. 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0

에라토스테네스의 체 설명은 아래의 링크에 잘 되어있다. 에라토스네에스의 체 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 ko.wikipedia.org 아래의 코드로 구현 해보았다. #include using namespace std; bool visit[1000001]; // 소수라면 false이다.(방문하지 않았으므로) true fill(visit,visit+1000001,false); // false로 초기화 for(int i=2;i

이진트리로 메시지의 내용을 압축한다. 각 글자의 비트수를 최소로 해서 문자를 압축하는 것이다. 예로 e, t, n, i, s 5개의 문자로 이루어진 문자열이 있다고 가정해보자. 그럼 각 글자의 빈도수와 표현에 필요한 비트수를 구해본다. ( 한 글자를 표현할때 필요한 비트는 3비트라고 가정) 글자 빈도수 비트수 e 15 3x15=45 t 12 3x12=36 n 8 3x12=24 i 6 3x6=18 s 4 3x4=12 즉 e t s i s 로 각각 해당 문자의 빈도수만큼 표현한 문자열은 총 비트수가 135이다. 즉, 135 비트를 차지함 하지만 아래와 같이 허프만 코드를 이용해 압축을 한다면 글자 빈도수 비트코드 비트수 e 15 00 30 t 12 01 24 n 8 11 16 i 6 100 18 s 4 10..

(1) 정점 A, B의 LCA는 A, B를 자식으로 하는 가장 깊은 노드 (2) A가 B의 자식이라면 A와 B의 LCA는 B가 될 수 있다. 각각 해당하는 트리의 그림을 보자. (1)의 경우 위로 푸른색의 노드들은 모두 A와 B의 공통된 부모이지만 진한 파란색의 노드가 가장 깊은 부모이자 LCA이다. (2)의 경우 A와 B의 LCA는 B이다. 위의 그림을 보니 필요한 변수가 보인다. Tree를 저장할 인접 리스트 노드의 부모를 저장한 parent 배열 노드의 깊이를 저장할 depth 배열 단순히 한칸씩 올라가며 LCA를 찾는다면 아래와 같은 케이스에 엄청난 시간이 든다. 그래서 우리는 1, 2, 4, 8 ,16 ... 이런 방식으로 올라가자. 2의 승수로 올라가니 각 정점에 대해 1, 2, 4, 8.....

문자열을 탐색하는데 피연산자(숫자)라면 스택에 그냥 저장해줍니다. 연산자라면 피연산자가 2개 필요하겠죠? 스택에서 피연산자 2개를 꺼냅니다. 먼저 꺼낸 것은 op2 ( 연산자 뒤에 쓸 피연산자) 2번째로 꺼낸것은 op1 ( 연산자 앞에 쓸 피연산자)입니다. op1, op2를 연산자로 계산하여 스택에 넣어줍니다. 연산자가 / 라면 op1/op2를 스택에 넣어줍니다. 이 과정을 문자열 끝까지 실행 시 스택에는 결괏값만 남아 있을 것입니다. 전체 코드 #include #include using namespace std; int solve(string str) { stack s; int idx = 0; while (idx < str.length()) { char ch = str[idx]; if (ch != '+..

피연산자(숫자)를 만난다면 그냥 바로 피연산자를 출력해준다. 연산자를 만난다면 스택에 넣을 것이다. 그런데, 우선순위가 항상 높은 것이 스택의 맨 위에 있도록 스택을 유지하게 넣을 것이다. ( 우선순위가 같다면 먼저 스택에 있던 연산자가 먼저 출력해주는게 맞다 그러므로 같아도 출력해주며 pop해줄것이다.) 왼쪽 괄호 '(' 는 스택에 바로 넣어줄 것이다. ( 우선순위를 제일 낮게 설정 ) 오른쪽 괄호 ')' 는 '(' 가 스택에 맨 위에 있을 때까지 스택 안의 연산자들을 출력하면서 pop을 해줄 것이다. 모든 과정을 문자열 끝까지 한 후 스택에 남아있는 연사자들을 모두 출력해준다. 중위 표기법 후위 표기법 1+3*8 138*+ 전체 코드 #include #include using namespace std..

[(()){}{}] 와 같은 괄호가 있다. 이 괄호가 올바른지 확인하는 방법으로 스택을 사용한다. 여는 괄호는 스택에 그냥 넣어주면 된다. 닫는 괄호에서는 스택을 열어봐서 비교해봐야 한다. 현재 닫는 괄호가 ')'일 경우 스택의 맨 위 요소는 '(' 여야만 한다. 아니라면, 괄호 짝이 안 맞아 괄호를 닫을 수가 없다... 그래서 닫는 괄호가 나올 때마다 스택의 맨 위 요소가 짝이 맞는지 확인을 해주어야 한다. 짝이 맞다면 닫는 괄호를 push 하지 말고 스택의 맨 위(확인한 여는 괄호)를 pop 해준다. 이 과정을 문자 하나하나 돌면서 문자열 끝까지 한다. 괄호가 올바르다면 스택에는 아무것도 없어야 한다. 왜냐하면, 다들 짝을 맞춰 pop을 했을 테니 소스 코드 #include #include using..

모든 노드에서 모든 노드의 최단 경로를 구할 때 사용 양의 가중치와 음의 가중치 모두 사용 가능 하지만 음의 가중치 일 경우 사이클이 없어야함. 기본 초기화 방법 V : 정점의 개수 E : 간선의 개수 arr[i][j] : i에서 j로 가는 비용 int V, E; int arr[101][101]; int a, b, c; cin >> V >> E; for (int i = 0; i > a >> b >> c; // a에서 b로 다닐수 있는 비용 c인 길 arr[a][b] = c; arr[b][a] = c; } 이렇게 처음에 정점의 개수와 간선의 개수를 입력받고 간서의 개수만큼 a b c 를 입력 받는다( a에서 b로 다닐 수 있는 비용 c인 길 ) 위의 코드는 양방향으로 길을 놓..