https://www.acmicpc.net/problem/15316 15316번: 현수시티 여러분도 모두 알다시피, 경기과학고는 수원시 장안구 송죽동에 세워져 있다. 하지만, 사실 여러분이 아는 송죽동이 전부가 아니었으니... 여러분이 잠든 사이, 송죽동은 음침하고 위험한 도시 ' www.acmicpc.net 문제 요약 : 정점과 간선이 주어지고 쿼리가 주어지는데 i번째 간선을 연결했다가 끊었다가할 때 어떤 정점 u, v가 연결되어있는지 확인하는 문제이다. 먼저 u,v 가 연결되어있는지를 확인하는 작업은 union find 를 사용한다. 그런데 끊어야 하기 때문에 path compression 은 사용할 수 없고 rank compression만 사용해야한다. 그리고 특정 작업을 롤백하기 위해서 합쳐질 때..
https://leetcode.com/problems/set-matrix-zeroes/ Set Matrix Zeroes - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제요약 2차원 배열이 있을 때 어떤 원소가 0이라면 그 원소가 속한 행과 열의 값을 모두 0으로 바꾸되 추가적인 배열을 사용하지 말것(Constant Space) 행의 크기가 n, 열의 크기가 m 일 때 단순히 맨 가장자리부분, 첫 행과 첫 열을 그 행과 열이 바뀌어야하는지 아니면 안 바뀌어도..
동적 계획법 : 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 두 가지 속성을 만족해야 DP로 문제를 해결할 수 있다. 1. Overlapping Subproblem 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다. 문제를 작은 문제로 쪼갤 수 있다. 2. Optimal Substructure 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 피보나치 수를 기준으로 보면 메모이제이션 : 실행된 결과를 저장해두었다가 재사용하는 최적화 기법 Top - Down : 큰 문제를 작은 문제로 나눈다. fib(n) = fib(n-1) + fib(n-2) 작은 문제를 푼다. fib(n-1) 과 fib(n-2)를 호출해 문제를 푼다. 작은 문제를 풀었으니 큰 문제를 해결한다. fib(n-1) 과 fib(n-2) 결과..
Strongly Connected : 모든 정점에서 정점으로 이동할 수 있다. SCC : 그래프를 Strongly Connected 되게 나누는 것이다. 하나의 SCC에서 두 정점 u,v를 선택하면 u에서 v로 이동가능하고 v에서 u로 이동할 수 있는 가장 큰 집합을 만드는 것이다. 간단하게 말하면 사이클이 포함된 그래프는 위상정렬이 불가능하다. 하지만 scc를 수행하면 사이클을 묶은 큰 노드들이 되고 scc로 묶인 그룹 간에는 위상정렬이 가능하게 된다. SCC를 구하는 방법으로는 코사라주알고리즘과 타잔 알고리즘이 있다 먼저 코사라주 알고리즘 부터 살펴보자 Kosarju’s algorithm 1. 첫 번째 dfs를 하면서 정점에 후위순회 번호를 매긴다. 그 다음 후위 순회 결과를 뒤집어준다. 2. 두 번..
해시
분류 - 비암호학적 해시함수: 암호학적으로 사용하기에 안전하지 않은 해시함수들 데이터 저장 및 찾기, 저장/ 전송 중에 생긴 데이터 오류 탐지, 고유한 ID 생성 등 모든 데이터에 대해 최고의 결과를 보장하는 해시함수는 존재하지 않는다. 입력값에 따라 다른 해시함수를 사용하는 확률적 알고리즘은 존재(Universal hashing) 용도에 맞는 해시 함수를 사용하는게 중요 - 암호학적 해시함수 응용 - 체크섬(checksum) - CRC(순환 중복 검사, cyclic redundancy check) 속성 - 효율성(efficiency) 공간을 더 쓰더라도 보통 빠른 해시함수를 선호 충돌이 나더라도 더 빠른 함수를 선호 하지만 하드웨어 가속이 어려운 해시를 선호하기도 함(소프트웨어 적으로는 빠름) - 암호..