www.acmicpc.net/problem/1188 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 자기 전에 간단한 문제를 풀고 자려고 골라보았다. 처음에는 n,m 이 각각 홀, 짝 개인 거 또는 gcd와 관련해 식이 달라질 거라 생각하고 몇 개 그려보니, 정답의 식이 다음과 같음을 알 수 있다. 커트 횟수 = m - gcd(n, m) 커트를 최소한으로 해야되는데, 1/gcd(n,m)만큼 자른 것 + a(남은 것) 한 만큼 나눠준다고 생각하면 쉽다. 코드는 다음과 같다. import math n, m = map(int,input().split()) print(m - math.gcd(n,m))
www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 판다가 주어진 대나무 맵에서 전날 먹은 대나무 양보다 많이 먹는 쪽으로만 이동할 때 며칠동안 살아남을 수 있는지 구하는 문제입니다. 처음에는 dfs만 가지고 구했는데 시간초과도 아니고 그냥 틀렸다 그래서 당황스러웠습니다. (아무리 생각해도 반례는 떠오르지 않았다....) 그렇기에 dp를 조금 첨가하여 풀었습니다. dp[y][x]를 (y,x)에서 최대로 이동할 수 있는 칸의 수라고 합시다. 처음에 dp[..
www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 이용한 문제였습니다. 단방향 그래프가 주어져 있을 때, 파티 지점까지 갈 때와 올 때 최소 경로로 올 때, 그 합이 최대인 것을 구하는 문제입니다. 다익스트라 알고리즘은 하나의 지점에서 모든 지점으로 가는 최단 경로를 찾을 때 유용하게 사용됩니다. 그래서 각 출발 지점에서 파티가 열리는 지점까지 모두 다익스트라로 돌리면 도착 지점은 항상 X로 정해져 있지만, ..
백준 / 1517 버블 소트 C++
www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 처음 생각했던 것은 O(nlogn) 정렬을 활용해 정렬 후 기존 배열의 인덱스를 비교해가며 더하는 것이었는데 배열에 중복된 값이 존재하면 안 된다는 것을 깨달았습니다. 아이디어가 떠오르지 않아 다른 분들의 풀이를 참고했습니다. 아이디어 : merge sort 과정에서 교차점의 개수와 버블 소트의 swap 횟수는 같다. 예를 들어 1 3 5 7 / 2 4 6 8 을 정렬한다고 하면 swap 횟수는 6번이..
이미지 암호화 / DES (single) 활용한 이미지 암호화
지난 번에는 AES128을 활용한 이미지 암호화를 진행하였습니다. 이번에는 추가적으로 DES (single) 을 활용한 이미지 암호화를 진행해보겠습니다. (라운드 별로 나오는 결과를 추후에 이용하고 싶어 라운드를 조작하는 부분을 추가하였습니다.) 우선 Single DES의 기본 구조를 살펴 보면 다음과 같습니다. 이처럼 평문 블럭은 64bit, 마스터키는 56bit, 라운드키는 48bit를 사용합니다. Initial Permutation과 16라운드, Final Permutation을 거쳐 최종 암호문 블럭을 얻게 됩니다. Initial Permutation과 Final Permutation은 64bit 평문을 섞어주는 역할을 합니다. 하지만 테이블이 주어져 있기 때문에 안전성에는 영향이 없습니다. 테이..