알고리즘/기타

문제 설명보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, B..

문제 설명크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.1 2 32 1 14 5 6배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.A[1][1] A[1][2] → A[1][3] ..

문제 설명한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.다음 예는 22 × 22 크기의 배열을 방문한 순서이다.N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음은 N=3일 때의 예이다.https://www.acmicpc.net/problem/1074      제한 사항      풀이문제를 요약하면, $2^N x 2^N$ 크기의 배열이 주어지면, (r, c)를 몇 번째로 탐색하는지 구하는 것이다.이때, 탐색의 순서는 재귀적으로 z를 ..

문제 설명민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다.어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오.친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다.https://www.acmicpc.net/problem/4195      제한 사항      풀이문제를 요약하면, 2명씩 입력이 주어질 때 두 사람은 친구 관계가 되며 친구가 되었을 때 이전 친구 관계를 포함하여 총 몇 명의 친구가 존재하는지 출력해야 한다. 문제 풀이는 간단하다.유니온-파인드를 이용하여 두 사람씩 친구 관계를 이어주면 된다. ..

문제 설명한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.T(=5) = A[1] + B[1] + B[2] = A[1] + A[2] + B[1] = A[2] + B[3] ..

문제 설명음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.https://www.acmicpc.net/problem/1038      제한 사항      풀이문제를 요약하면, N번째 감소하는 수를 구하는 것이다.감소하는 수란 10, 21, 20처럼 첫자리부터 끝 자리까지 수가 감소하는 수를 말한다.11이나 22는 감소하는 수가 아니다. 문제를 풀기 위해서는 규칙을 찾아내야 한다.규칙을 찾기 위해 감소하는 수를..

문제 설명N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.각각의 벽에 대해서 다음을 구해보려고 한다.벽을 부수고 이동할 수 있는 곳으로 변경한다.그 위치에서 이동할 수 있는 칸의 개수를 세어본다.한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.https://www.acmicpc.net/problem/16946      제한 사항      풀이문제를 요약하면, 모든 벽에 대해 해당 벽을 부수었을 때 이동할 수 있는 칸의 개수를 구해야 한다. 간단하게 생각해보면, 모든 벽에 대해 bfs를 통해 이동할 수 있는 칸을 ..

문제 설명크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.https://www.acmicpc.net/problem/17298      제한 사항      풀이문제를 요약하면, 배열이 주어지면 모든 요소들이 자신의 오른쪽에 ..

문제 설명구사과의 방에는 난로가 하나 있다. 구사과는 절약 정신이 투철하기 때문에, 방에 혼자 있을 때는 난로를 되도록 켜지 않는다. 구사과는 방에 친구가 왔을 때는 항상 난로를 켠다.오늘은 N명의 친구들이 구사과의 집에 방문하는 날이다. 구사과는 친구들을 쉽게 구분하기 위해 1부터 N까지 번호를 매겼다. i번째 친구는 구사과의 방에 시간 Ti에 도착하고, 시간 Ti+1에 나간다. 구사과의 방은 좁기 때문에, 한 번에 한 명만 방문할 수 있다. 즉, 방안에는 항상 구사과를 포함해 2명 이하의 사람만 있게 된다.구사과는 난로를 아무 때나 켤 수 있고, 끌 수 있다. 난로를 켜려면 성냥을 이용해야 한다. 오늘 구사과는 총 K개의 성냥을 가지고 있다. 따라서, 최대 K번 난로를 켤 수 있다. 가장 처음에 난로..

문제 설명서강대학교의 축제 기간에 상근이는 매년 AS관 복도에 화려한 장식을 꾸민다. 장식은 전구 N개로 이루어져 있고, 전구는 왼쪽에서 오른쪽으로 일렬로 배열되어 있다. 각 전구는 불이 켜있을 수 있고, 꺼져있을 수도 있다.상근이는 이 전구를 조작하기 위해서, 집에서 전구를 조작하는 기계를 가지고 왔다. 이 기계는 어떤 구간의 전구를 지정하면, 불이 켜있는 전구의 불을 끄고, 꺼져있는 전구의 불을 켜는 기능이 있다. 하지만, 이 기계는 상당히 오래된 기계로, 한 번 사용하면 다음 해까지 더 이상 사용할 수 없다.서강대학교 학생들은 불이 켜있는 전구와 꺼져있는 전구가 번갈아가면서 나타나는 패턴을 좋아한다. 이러한 패턴을 교대 패턴이라고 한다. 따라서, 상근이는 이 기계를 1번만 사용해서 가장 긴 교대 패..