본문 바로가기

C34

스택 응용(수식 계산) 1. 수식표기법 (1) 중위표기법(infix notation) : 연산자를 피연산자의 가운데 표기하는 방법 => 우리가 사용하는 방식 ex) A+B (2) 후위표기법(postfix notation) : 연산자를 피연산자 뒤에 표기하는 방법 => 컴퓨터 처리 방식 : 응용하여 중위표기법->후위표기법->수식 계산 : 스택 이용 ex) AB+ 1.1 괄호 검사 : 이때 수식을 계산하기 위해서는 올바른 수식인지 확인하기 위해 괄호 검사가 필요하다 : 수식에 포함된 괄호는 가장 마지막에 열린 괄호가 가장 먼저 닫아주어야 하는 구조를 스택을 통해 구현가능 : 수식검사가 완료된 경우, 공백 스택 상태여야함 왼쪽 괄호를 만나면 스택에 push 오른쪽 괄호를 만나면 스택에서 pop하여 같은 종류의 쌍의 괄호인지 확인 #.. 2023. 9. 15.
Transposition Cipher[C] 1. 전치암호 : 평문 문자의 순서를 어떤 특별한 절차에 따라 문자 위치를 재배치하여 평문을 암호화하는 방식 => 가장 단순한 전치 암호 : 정상적인 평문 배열을 특정한 키의 순서에 따라 재배치하여 암호화 cf> 대치암호(substitution) : 문자를 다른 문자로 전치암호(transposition) : 문자의 위치를 변경 1.1 단순 전치 암호 (1) 동작방식 평문 문장을 키의 길이에 따라 일정 간격으로 나눈다 일정 간격으로 나눈 문자를 키의 재배열 순서에 따라 재배치 (이때, 마지막 간격의 문자가 부족하면 임의의 문자 덧붙임) 1) 구현 : 필자는 키의 크기가 문장의 길이의 약수라고 전제로 하여 코드를 작성 : 랜덤 key table을 생성하기 위해 check 배열을 따로 생성하여 서로 다른 난수.. 2023. 9. 4.
Vigenere Cipher[C] 1. Vigenere Cipher(비제네르 암호) : 다중 대치 암호의 대표적인 암호 1-1. 단일문자대치암호 vs 다중대치암호 단일문자대치암호(ex. 카이사르암호) : 하나의 평문 문자 -> 동일한 하나의 암호 문자 다중대치암호(ex. 비제네르암호) : 하나의 평문 문자 -> 여러 개의 암호 문자 1-2. 다중대치암호 방식 : 대치표를 2회 이상 적용 : 대치 표 개수가 d라면 주기 d를 갖는다 => d=8, 비밀키 수열= "security" : 평문을 길이 8씩 분할하여 비밀키의 문자와 mod26 연산을 통해 암호문을 생성 1-2-1. 비밀키의 차이 카이사르 암호 : key = 1(숫자) -> abcd의 암호화 결과 : bcde 비제네르 암호 : key = ab(문자열) -> abcd의 암호화 결과 .. 2023. 9. 1.
Caesar Cipher[C] 1. 카이사르 암호 : 고전 암호 알고리즘으로 평문 문자를 다른 문자로 일대일 대응시켜 암호문을 만들어내는 방식 : 모듈 이용 : Brute-Froce 알고리즘에는 취약함 1.1 카이사르 암호 알고리즘 구현 1) 고려해야하는 점 (암호화) 키를 적용했을 때 범위를 벗어나는 것(모듈러 값을 초과)을 방지하기위해 순환시킨다 (복호화) 키를 적용했을 때 범위를 벗어나는 경우(음수가 되는 경우) 26을 더해준다 -> 이때 mod26을 하는 건 어떤 숫자를 0~25의 범위의 숫자로 만드는 과정이기에 (26이상의 자연수)-26을 하는 것이라 생각할 수 있다(물론, 26보다 한참 큰 숫자는 -26한 결과와 %26한 결과는 다르다) -> 그렇다면 음수가 되어 범위를 벗어나는 경우엔 (0미만의 정수)+26을 하여 0~2.. 2023. 9. 1.
EED(Extend Euclid Algorithm)[c] 1. 확장 유클리드 알고리즘 ∀a,b ∈Z, If gcd(a,b)=d, then ∃x,y ∈Z s.t ax+by=d : 유클리드 알고리즘을 이용해 두 수의 최대공약수를 구하는 거라면 확장 유클리드 알고리즘은 거꾸로 수행하며 x,y를 찾는 과정이라고 할 수 있다 : 이 점을 이용하여 두 개의 정수가 서로소, 즉 gcd의 값이 1일 땐 하나의 수에 대한 다른 수의 곱셈에 대한 역원을 계산할 수 있다 : gcd(a,n)=1 (a 단항식의 해를 구하는 과정은 n을 법으로 하는 a의 곱셈의 역원을 구하는 것과 동일해진다 (1) EED 동작 : ∀a,b ∈Z(a≥b), sxa + txb = gcd(a,b) 만족하는 gcd와 s,t 값 도출 이때 a= b*q+r (division algorithm) 1) Divisi.. 2023. 9. 1.
강한 결합 요소(Strongly Connected Components) 강한 결합 요소 : 그래프 안에서 강하게 결합된 정점 집합 cf> scc 활용 : scc마다 묶으면 cyclic 존재하지 않는 방향 그래프이기에 위상정렬 수행 가능하다 1. 알고리즘 코사라주 알고리즘(Kosaraju's Algorithm) 타잔 알고리즘(Tarjan's Algorithm) (1) 타잔 알고리즘 : 모든 정점에 대해 DFS(Depth-First Search, 깊이 우선탐색)을 수행하여 scc 찾는 알고리즘 : 부모로 돌아올 수 있어야 scc 성립 : 각 정점마다의 부모 노드가 무엇인지 기록(초기값은 자기자신) => union-find algorithm 개념과 비슷 (2) 작동 방식 1) 정점번호가 낮은 순으로 DFS 탐색 (이때, 연결리스트 통해 오름차순으로 정렬하였음) 2) 현재 정점의 .. 2023. 8. 15.

티스토리툴바