SM's Development Log

문제어젯밤 겨울 캠프 장소에서 월드 본원까지 이어지는, 흙으로 된 비밀길 위에 폭우가 내려서 N (1 N >> L; for (int i = 0; i > Puddles[i].first >> Puddles[i].second; sort(Puddles, Puddles + N); int s = 0; for (int i = 0; i < N; ++i) { // 시작지점은 이전에 놓은 막대와 겹치지 않은 웅덩이의 부분이다. s = max(Puddles[i].first, s); // 웅덩이를 메우기 위해 얼만큼의 길이가 필요한지 구한다. int diff = Puddles[i].second - s; // 웅덩이를 완전히 메우려면 Ceil(diff / L)이어야 한다. int count = (di..

문제RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로, 초록으로, 파랑으로 칠하는 비용이 주어진다. 비용은 1,000보다 작거나 같은 자연수이다. 출력첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다. 코드C++ 17 #include #inc..

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. 출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 코드C++ 17 (최적화 전) #include #include using namespace std; int N; // 이 문제는 n을 규칙을 사용하여 나누면 또 다른 n에 대한 문제가 된다.// 따라서 메모이제이션할 부분은 각 숫자에 대한 횟수이다.int Memo[1000001]; ..

문제0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오. 행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0) 입력첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. 출력첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다. 코드C++ 17 #include #include using namespace std; int Ans;int N, M;string A[50];string B[50];..

문제N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N이 주어진다. (1 ≤ N 퀸이 (row, cols[row])에 위치해 있다.int cols[15];int N, Ans; // N-Queen 문제는 전형적인 백트래킹 문제이다.// 다음 함수는 유망성을 검사하는 함수이다.bool canPlace(int bound){ // 이전까지 배치된 퀸의 위치를 순회하며 배치 가능..

문제N(1≤N≤100,000)개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M=3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다. 입력첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000을 만족한다. 출력첫째 줄에 M 이상이면서..

문제크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다. 이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다. -3 -2 -1 0 1 2 3 ---------------------3 |37 36 35 34 33 32 31-2 |38 17 16 15 14 13 30-1 |39 18 5 4 3 12 29 0 |40 19 6 1 2 11 28 1 |41 20 7 8 9 10 27 2 |42 21 22 23 24 25 26 3 |43 44 45 46 47 48 49이 문제는 위와 같이 채..

문제2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 입력첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 출력첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 코드C++ 17#include #include using namespace std; bitset Numbers;int N, K; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.t..

문제에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.이 알고리즘은 다음과 같다.2부터 N까지 모든 정수를 적는다.아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(2, K) < N ≤ 1000) 출력첫째 줄에 K번째 지워진 수를 출력한다. 코드C++ 17 #include #include using namespace std; bitset Numbers; int N, K; int ..

새해가 시작하고 무려(!) 하루가 더 지나서야 작성하는 작년에 관한 회고록이다. 짧지만 그 간 살아오면서 작년만큼 힘이 많이 든 해도 없었던 거 같다. 작년을 회고하면서 앞으로는 무엇을 해나갈지 정리해보고자 한다.대학 생활 곧 있으면 대학 생활도 끝이 난다. 마지막 학년 중 가장 큰 이슈라고 한다면 단연 졸업작품 전시회이다. 나는 포트폴리오에 하나 더 추가할 요량으로 게임을 선택했었는데, 어찌저찌 통과하긴 했으나 아쉬움이 많이 남는다. 나의 능력 부족으로 인해서 일거리를 적절하게 분배하지 못했던 거 같고, 이끄는 것도 많이 모자랐다. 하지만 그 경험을 통해서 표현의 중요성을 많이 깨달았고, 게임 서버 쪽을 공부하면서 전체적인 그림은 그릴 수 있게 되었다. 이전에는 너무 사람들한테 높은 잣대를 들이밀곤 해..