본문 바로가기

CS33

전자서명과 동작 원리 전자서명 전자서명은 프로그램, 드라이버, 서비스 등 여러 매체들이 안전하게 사용할 수 있다는 것을 인증하기 위해 사용되는 서명이다. 안전한 파일이나 드라이버임을 인증하기 위해 Code-Signing과 같은 작업도 전자서명이고… 웹사이트가 안전하다는 것을 인증 받기 위해 SSL을 적용하는 것도 전자서명이고 인증서에 Timestamping하는 것도 전자서명이다. 즉, 안전하다는 것을 인증하기 위한 행위가 전자서명의 포괄적인 의미이다. 위의 이미지는 크롬 브라우저에서 SSL을 적용한 인증서에 대한 확인하는 방법이다. https가 적용되어 자물쇠 아이콘이 있으면 SSL이 적용된 사이트라는 표시이다. 인증서를 확인해보면 인증서 3개가 연결되어 있는것을 확인할 수 있다. 이는 인증서 체인이라고 하는데 가장 상단에 .. 2021. 10. 6.

대칭키 / 비대칭키 양방향 암호화 기법 양방향 암호화 이전 글에서는 봤던 단방향 암호화 기법과 반대로... 대칭키와 비대칭키는 양방향 암호화 방식 이다. Hash를 사용한 단방향 암호화 방식과는 다르게 암호화된 암호문을 복호화할 수 있는 알고리즘이다. 대칭키 : 암호화, 복호화에 사용되는 키가 동일하다. 비대칭키 : 암호화, 복호화에 사용되는 키가 다르다. 암호화와 복호화에 사용되는 키들의 실체는 대체로 파일형태로 되어있고 열어보면 암호화된 값이 있다. 대칭키 암호화 양방향 암호화 방식 중에 널리 사용하는 대칭키는 암호화와 복호화에 같은 암호 키를 쓰는 알고리즘이다. 비교 예시 2차 세계대전 때 독일 스파이들은 모스부호를 이용해서 민감한 군사 정보를 암호화해서 서로 전달을 했다. 여기서 중간에 이 모스 부호로 암호화된 정보를 가로챈다고 하더라.. 2021. 10. 6.

Hash 단방향 암호화 기법 Hash 해시는 데이터를 다루는 기법 중 하나이다. 해시의 가장 큰 특징은 데이터의 크기와 상관없이… 해시 알고리즘을 통해 얻는 해시값은 항상 고정된 길이를 반환한다. 이런 특징을 갖고 보안적인 관점에서는 단방향 암호화으로 사용 할 수 있다. 용어 정리 용어 설명 해시 함수(알고리즘) 임의의 크기의 데이터를 input값으로 고정된 길이의 output(해시값)으로 반환해주는 함수 해시 값 해시 알고리즘에 의해 얻은 데이터. 해시코드, 해시 체크섬 이라고도 한다. 해싱 해시 알고리즘에서 해시값을 매핑하는 과정 해시의 특징 해시 알고리즘은 아래와 같은 몇가지 중요 특징들이 있다. 고정된 길이 hash(10GB Data) = '84960594d762e2534b56c2e8f8b2a3f6770e1ae8e13d255.. 2021. 10. 6.

백준 2839 파이썬 - 설탕 배달 - 동적 계획법 백준 2839 파이썬 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net N킬로그램의 설탕이 주어졌을 때, 설탕을 담기 위해 3키로그램과 5키로그램 봉지로 가장 적은 양의 봉지를 만들어 내는 방법을 구하는 문제이다. 이 문제는 계산 횟수를 줄이기 위해 이전에 계산했던 값을 기억해뒀다가 재사용하는 메모이제이션을 활용하는 것이 적당하다고 판단했습니다. 3 ~ N킬로그램까지 작은 숫자부터... 각각 가장 적은 양의 봉지를 저장해두면... 해당 값보다 3, 5 큰 .. 2021. 10. 5.

[백준 11724 연결 요소의 개수] 파이썬 BFS 너비 우선 탐색 풀이 연결 요소의 개수 문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 뱡향 없은 양방향 그래프가 주어졌을 때 연결 요소를 구하는 문제입니다. 문제 풀이 연결 요소를 구하는 것은 즉 몇개의 구역으로 나누어져 있는지 구하는 문제입니다. 그래프를 위와 같이 표현했을때 2개의 영역으로 이루어져 있습니다. DFS, BFS 모두 사용해서 풀수 있는 문제입니다. 너비 우선 탐색 BFS로 문제를 풀어보겠습니다. 1. 그래프 연결 정보용 행렬 생성 2. BFS.. 2020. 9. 28.

[백준 1012 유기농 배추] 파이썬 BFS 너비 우선 탐색 풀이 유기농 배추 문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 2차원 배열의 유기농 배추밭이 주어지고 0(땅) 과 1(배추 심어져 있는 땅)로 데이터가 구분됩니다. 배추흰 지렁이를 배추에 서식하게 하면 사방면으로 이동이 가능하여 다른 배추를 해충으로부터 보호가 가능하다. 필요한 배추흰 지렁이의 마리수를 구하는 문제입니다. 입력 받는 정보로 아래와 같이 배추 밭을 2차원 배열 형태로 만들어 주어야 합니다. 문제 풀이 4방면으로 이동이 가능하므로 각 영역당 한마리의 배추흰 지렁이를 배치하면 해결할 수 있습니다. 즉, .. 2020. 9. 28.

[백준 10026 적록색약] 파이썬 BFS 너비 우선 탐색 풀이 적록색약 문제 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net RGB 3가지 문자로 이루어진 N * N 보드판이 주어질때 일반사람과 적록색약인 사람이 보는 구역의 수를 각각 구하는 문제입니다. 적록색약은 R과 G를 하나의 색으로 보입니다. 즉, 아래와 같이 구역이 나뉘게 됩니다. 문제 풀이 2차원 배열의 영역을 구하는 문제로 BFS 너비 우선 탐색 알고리즘을 사용해서 풀면 될것으로 판단했습니다. 단, 2가지 경우가 발생하기 때문에 2가지 버전의 배열을 만들어주고 탐색하는 방식을 선택했습니다. N의 최대 .. 2020. 9. 27.

백준 14500번 테트로미노 완전탐색(brute-force) 알고리즘 문제 :: 코드자몽 [백준] 14500번 테트로미노 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 풀이 이런 블록 형태의 문제가 나오면 실제로 도형을 그려보면서 문제를 푸는 것이 가장 좋은 방법인 것 같다. 먼저 N*M 크기의 종이 위에 블록 하나만 놓는다고 했으니.. 2019. 12. 23.

백준 2309번 일곱 난쟁이 완전탐색(brute-force) 알고리즘 문제 :: 코드 자몽 완전 탐색 Brute-Force 완전 탐색은 말 그대로 모든 경우의수를 일일이 탐색하여 정답을 찾아내는 알고리즘이다. 가능한 방법을 모두 확인하여 정확도가 높고 강력한 방식이지만, 시간은 다소 오래 걸리는 단점이 있습니다. 그래서 브루트 포스 알고리즘을 사용하기 전에 문제의 가능한 경우의 수를 먼저 계산을 해봐야한다. 컴퓨터가 1초에 대략 1억 번 정도의 일을 할 수 있다고 한다. 효율성을 고려하여 브루트 포스 알고리즘으로 문제를 접근할 경우 기준은 정해주는 것이 좋다. 예를 들어 "천만(10,000,000) 건 이하의 경우 수가 존재할 때만 브루트 포트 알고리즘을 사용하겠다."라는 기준을 정하고 문제를 접근하는 것이 유리하다. [백준] 2309번 일곱 난쟁이 2309번: 일곱 난쟁이 아홉 개의 줄에 걸.. 2019. 12. 23.

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽 소수(Prime Number) 소수는 자신보다 작은 두개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. ex) 5는 5*1 또는 1*5로 수를 곱합 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 소수 (수론) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 좌측은 소수, 우측은 합성수. 소수란 자신보다 작은 두 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 예를 들어, 5는 1x5 또는 5x1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 .. 2019. 12. 22.

최대공약수(GCD), 최소공배수(LCM) 구하기 유클리드 호제법 알고리즘 :: 코드자몽 최대공약수 GCD(Greatest Common Divisor) 최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다. ex) 72 와 30의 최대공약수는 6이다. 최소공배수 LCM(Least Common Multiple) 최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다. 최소공배수 = 두 자연수의 곱 / 최대공약수 ex) 72 와 30의 최소공배수는 360이다. 유클리드 호제법(Euclidean Algorithm) 2개의 자연수를 받아 최대공약수를 받기 위해 2부터 두 자연수 중 작은 자연수까지 모두 나누어보면서 가장 큰 공약수를 구할 수 있다. 위와 같은 방법으로 문제를 풀면 시간복잡도는 O(N)이 된다. 나쁜 방법은 아니지만 효율을 높이기 위해 유클리드 호제법이란 알고리즘.. 2019. 12. 22.

JAVA 자바로 비트연산 알아보기 :: 코드 자몽 비트연산자 비트연산은 2진수형태의 숫자 0과 1로 할 수 있는 연산이다. 자바에서 기본적으로 사용할 수 있는 연산 6가지를 알아보자.비트연산자를 잘 사용하면 알고리즘을 다양한 방법으로 작성할 수 있을 뿐더러 시간복잡도를 줄여 주는 효과를 볼 수 있다. 왼쪽 시프트( y 형식으로 연산자를 사용하면 되고 x의 비트를 왼쪽으로 y칸 이동시킨다는 것을 의미한다.ex) 1111 >> 2 = 111111(15) 이 11(3)로 변형되는 것을 보면 x / 2^y 으로 나머지를 제외한 몫을 반환한다. 비트의 보수(~)이진수의 모든 비트를 반대로 바꾼다. 0 이면 1, 1이면 0으로 바꾼다. 보수를 사용할 경우 32자리를 기준으로 값을 반환한다.~x 형식으로 연산자를 사용하고 x의 보수를 구하라는 의미이다.ex) ~01.. 2019. 11. 23.

[배열] 부분집합 관련 문제 비트연산으로 풀기 :: 코드자몽 부분집합 구하기 배열이 주어졌을때 부분집합을 구하는 코드를 작성해보자. 아래 기본 문제를 설명 및 코드샘플을 확인하지 않고 먼저 풀어보자. 기본 문제 {1, 2, 3, 4, -1, -5} 위 배열에서 홀수로 구성된 부분 집합을 모두 출력 하시오. 간단해 보이지만 비트연산을 이해하지 못하면 생각보다 어려운 문제이다. 위 문제를 완전탐색 혹은 배열의 위치를 이용해서 풀겠다고 접근했을것이라 생각합니다. 완전탐색 방법으로 풀려고 하다보니 for문을 중첩해서 사용하면 배열이 커질수록 효율도 떨어지고 시간복잡도가 제곱으로 늘어나는 것을 확인했을 것입니다. 그럼 배열의 위치를 이용해서 푸는 방법을 생각하다보니 0과 1을 이용하여 자리를 표시하는 방법이 떠오르게 될것입니다. 위의 문제 처럼 부분집합을 구하는 문제에서는.. 2019. 11. 22.

이전 1 2 다음

티스토리툴바