www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 전형적인 KMP 알고리즘 문제였습니다. KMP 알고리즘을 이용해 해당 부분 문자열이 나오면 true, 아니면 false만 판별하면 됩니다. 코드는 다음과 같습니다. #include #include #include #include #include using namespace std; string S; string P; vectorpi; void init() { cin >> S; cin >> P; } // 전처리 pi 배열 구하기 void ..
www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net (저도 이 문제를 보기 전까지 녹색 옷 입은 애가 젤다인 줄 알았습니다.) n x n 동굴에 주인공이 0,0 지점에 있다면 n-1, n-1 까지 도달할 때 최소한의 검정 루피를 밟고 가도록 하는 문제입니다. 다익스트라 알고리즘을 이용해 시작지점이 0,0으로 정해져 있으므로 모든 지점을 탐색하면서 최소 경로로 만들어주면 됩니다. 그리고 마지막으로 n-1, n-1 지점의 최소 경로 값을 구해주면 ..
www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 터널 내의 차선 변경이 불가능할 때 추월 차량이 얼마나 되는지 묻는 문제입니다. (하지만 실제로는 큰 터널의 경우 추월가능한 터널도 있다.) 처음에는 dp로 생각하여 들어갈 때 내 차량 앞에 몇 대의 차량이 있는지를 계산하여 풀려했지만, 예제 몇 개를 떠올려보니 2번이 1번을 추월하고 1번이 2번을 다시 추월하고 그러면 계산이 꼬이는 경우가 있어서 다른 방법으로 풀었습니다. C++에서 map 컨..
DES 1라운드 암호화 이미지 판별 모델
지난 16라운드 DES 암호화 이미지 판별 모델을 적용하여 1라운드 암호화 이미지 판별을 실시하였습니다. 사실 16라운드가 암호화가 더 잘 된 상황이지만, CBC와 OFB는 구분 할 수 없었습니다. 1라운드 암호화 이미지의 경우 OFB와 CBC의 구분이 확실하고, ECB와 OFB 또한 어느정도의 구분이 가능하기 때문에 3가지 모드 모두를 판별하는 모델까지 작성하였습니다. 아래는 1라운드 암호화시 이미지입니다. (원본, ECB, CBC, OFB) 우선 기본 모델은 다음과 같습니다. (2가지 모드 비교) model = keras.models.Sequential([ keras.layers.Conv2D(32, 3, activation="relu", strides=(1,3),padding="same", input..
www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 예전에 푼 문제인데 재채점 되면서 틀렸다하여 다시 풀었다. 바이토닉 수열이란 수열이 S1 S_k+1 > ... > Sn 을 만족하는 k가 존재하는 수열을 말한다. 수열이 주어졌을 때, 부분 수열 중 가장 긴 바이토닉 수열의 길이를 구하면 된다. 수열의 길이가 1000개이므로 O(N^2) 정도로 풀어도 충분한 시간이다. 수열의 n번째 원소를 arr[n] 이라 하고, dp[n]을 arr[n]을 부분 수열..