분류 전체보기
-
2178 미로탐색알고리즘/백준 문제 2020. 5. 14. 20:11
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - 미로의 시작 [0,0] 에서 [n-1, m-1]로 빠져나가는 최단거리를 구하는 문제 - 정점간의 거리가 모두 1 이므로 BFS를 사용하여 최단거리를 구할 수 있다. 탐색중인 위치(x,y) 를 표시할 클래스 Pos를 만들었다. 반복문을 이용해 이동가능한 상하좌우 좌표를 확인하기 위해 상하좌우로 이동시켜줄 _x, _y 배열을 생성했다. 즉 각각의 배열 인덱스 0은 '상' 으로 이동하기 위한 x좌표, y좌표를 담고 있다. 위와 같..
-
충격받아 다시 블로그 시작한 후기휴먼띵킹 2020. 5. 14. 18:57
얼마 전에 카카오 인턴채용 코딩테스트가 있었다. 원래 공부를 잘하지도 않았고, 알고리즘은 더더욱 공부를 안했었기 때문에 기대를 하고 보진않았다. 가벼운 마음으로 문제를 확인하는데 5문제 모두 나에게 너무 어려워서 두 문제만 풀자는 생각으로 시험을 봤다. 결론부터 얘기하자면 한 문제만 쳐다보다가, 한 문제도 못풀었다. 문제를 적으면 안될 것 같아서 간단히 요약하면 가장 적은 가중치의 길을 찾는 문제였다. 직선으로 움직일 때와 방향이 바뀔 때 가중치가 달랐다. 단순히 최단거리? BFS지. 라고 생각하고 접근을 하려는데 BFS가 뭐였는지 잘 기억이 안났다. 이때부터 내가 정말 심각한 상태구나 라고 느꼈던 것 같다. 과거에 풀었던 문제를 보며 한참을 걸려 완성시킨 것 같았는데 계속 오답이었다. BFS를 이용해서..
-
1260 DFS와 BFS알고리즘/백준 문제 2020. 5. 14. 18:40
입력값 : 4 5 1 1 2 1 3 1 4 2 4 3 4 - DFS (Depth First Search 깊이우선탐색) 한 방향으로 갈 수 있는 끝까지 탐색을 마치고, 그 다음 방향으로 탐색한다. 길이 여러개일 경우 숫자가 작은 정점부터 탐색하므로 1 -> 2 로 이동. 한 방향으로 탐색을 이어가야 하므로 1 -> 2 -> 4 -> 3 으로 이어진다. 마지막 3 에 도착했을 때, 1 과 4는 이미 방문 한 상태이므로 재귀로 호출된 스레드가 하나하나 모두 종료된다. 모든 정점을 방문 했으므로 프로그램은 종료된다. - BFS (Breath First Search 너비우선탐색) 한 정점에 도착했을 때, 그 정점에서 방문 가능한 정점은 모두 방문한다. 동시에 여러 정점을 방문하는 형태이다. 각 정점의 거리가 1일..
-
Modular Arithmetic보안/컴퓨터보안 2019. 10. 13. 18:44
비유적으로 Clock arithmetic - 나누기한 값의 나머지를 말함 ( mod = 나머지. //// 'x mod n' = 나머지. ) - 시계 7시 + 6시해도 13시아니고 1시이듯 0~5까지 6가지 경우 -> Clock Arithmetic #Notation · 7 mod 6 = 1 · 7 = 13 = 1 · ((a mod n) + (b mod n)) mod n = (a+b) mod n · ((a mod n)(b mod n)) mod n = ab mod n · (7 + 12) mod 6 = 19 mod 6 = 1 mod 6 · (7 + 12) mod 6 = (1 + 0) mod 6 = 1 mod 6 Modular Multiplication · 3*4 = 0 ( mod 6 ) · 4*2 = 2 ( m..
-
Integrity보안/컴퓨터보안 2019. 10. 13. 18:00
Integrity에 문제가 생긴 경우 - 데이터를 중간에 가로채서 수정 - 공격자가 Alice인 척 메세지를 보내는 일 Data Integrity - 허용되지 않은 writing을 탐지하는 것이 목표 - Encryption은 Confidenciality를 보장하지만 단독으로는 Integrity를 보장하지 못함 MAC ( Message Authentication Code ) - Integrity를 보장하기 위해 사용된다. - CBC residue(CBC의 마지막 ciphertext block)을 사용한다. - MAC은 IV와 plaintext와 같이 보내진다.0 - Receiver도 반드시 key를 알아야 하고 계산을 해야한다. MAC 사용 예 Plaintext를 보내야하는데 alice가 bob에게 그냥보..
-
AES (Advanced Encryption Standard)보안/컴퓨터보안 2019. 10. 6. 19:29
DES가 수명을 다하고 3DES로 연명하다가 AES 를 사용하게 됌 key sizes: 128-10(rounds) / 192-12(rounds) / 256-14(rounds) bits block size: 128bits Substitution permutation network (not Feistel) 선 하나당 1byte. 4byte -> sub-box #AES-128 sub,permutation - 1.subBtyes~ 2. 3. AES s-box 예를 들어 first 4bit- 1101 -> 10진수로 13 ->16진수로 d last 4bit- 1101-> 10진수로 13 -> 16진수로 d ==> 테이블을 참고시 dd는 c1
-
Block cipher modes보안/컴퓨터보안 2019. 10. 6. 19:10
Block cipher에 대해 공부해서 각 블락들을 암호화하는 방법은 공부했다. 이제 이 블락들을 전체적으로 어떻게 암호화해서 전송하는지에 대해 알아본다. 블락을 전송하면 상대방이 받아서 복호화 해야하는데 그 과정에서 공격자가 블락의 순서를 바꿀수 있다. (Permutation공격, Integrity문제) ECB (Electronic CodeBook) - 각각의 블락을 독립적으로 암호화하는 모드 - 각각의 블락들은 암호화되어 (AES,DES등) 안전하다. - 하지만 블락의 순서들은 확인할 수 없기때문에 (보안 취약점) 사용되지 않는다. (Cut and Paste 공격) 공격자가 C0 C1 C2 C3의 순서를 -> C0, C3, C2, C1으로 바꾸고 decryption한 결과. - C = E(P,K) -..