분류 전체보기

문제 설명여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.     ..

문제 설명오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.https://www.acmicpc.net/problem/11057      제한 사항      풀이문제를 요약하면, i번째 숫자가 i-1번째보다 크거나 같은 수를 오르막 수라고 한다.N이 주어지면 N자리 수의 오르막 수의 개수를 구하면 된다. 만약, i자리 수의 오르막 수의 개수를 안다면 i+1자리 수의 오르막 수의 개수를 구할 수 있다.i자리의 수가 특정한 수로 끝난다..

문제 설명수열 S가 어떤 수 Sk를 기준으로 S1   Sk-1  > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/11054      제한 사항      풀이문제를 요약하면, 증가하였다 감소하는 수열을 바이토닉 부분 수열이라 한..

문제 설명n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.      제한 사항      풀이문제를 요약하면, N개의 동전으로 K를 만드는 경우의 수를 구하는 것이다.이때, N개의 동전은 각각 다른 가치를 갖고 있다. 해당 문제는 DP를 통해 간단하게 풀 수 있다.우선, {1, 2, 5}의 동전으로 10을 만드는 경우를 생각해 보자.0을 만드는 방법은 동전을 모두 사용하지 않는 단 하나의 경우밖에 없다.1을 만드는 방법 역시 1을 사용한 경우밖에 없다.2를 만드는 방법은 [1, 1], [..

문제 설명N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/11660      제한 사항      풀이문제를 요약하면, N x N 표가 주어지고 구간을 나타내는 좌표 (x1, y1), (x2, y2)가 주어질 때, 구간의 합을 구하는 문..

문제 설명45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.https://www.acmicpc.net/problem/10844      제한 사항      풀이문제를 요약하면, 특정한 수의 각 자릿수가 1씩 차이나는 수를 계단수라 하고, N자리의 계단수를 구하는 것이다. 해당 문제는 DP를 통해 간단하게 풀 수 있다.DP에서는 i자리 수 중 j로 끝나는 계단수의 개수를 메모이제이션한다.예를 들어, dp[3][2]는 세 자릿수 중 2로 끝나는 계단수의 개수가 된다.계단수를 DP로 구할 수 있는 이유는 i-1자리 계단수에 하나의 수를 추가하여 i자리 계단..

문제 설명페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다. 친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로운 아이디어를 먼저 받아들인 사람을 얼리 아답터(early adaptor)라고 하는..

문제 설명N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오https://www.acmicpc.net/problem/2252      제한 사항      풀이문제를 요약하면, N명의 학생을 M개의 관계로 줄을 세우는 문제이다.하지만, M개의 관계가 N명의 모든 학생을 나타내기엔 부족할 수 있다. 해당 문제는 위상 정렬을 이용하면 풀 수 있다. 위상 정렬이란 방향 그래프의 노드에 대해 순서를 매기며 정렬하는 것을 말한다..

문제 설명2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/11758      제한 사항      풀이문제를 요약하면, 주어진 세 개의 점이 일지선에 위치하는지, 시계방향으로 존재하는지 반시계방향으로 존재하는지 여부를 판정하는 것이다.이를 판정하는 것을 CCW라고 한다.이는 벡터의 외적과 관련되어 있다.벡터의 외적의 결과는 두 벡터의 직교하는 벡터인데, 이는 좌표계에 따라 다를 수 있지만 벡터가 존재하는 방향에 따라 결과가 달라진다는 것은 같다.즉, 세개의 점으로 두 개의 벡터를 만들고 두 벡터의 외적의 결과가 정답이 된다는 뜻이다..

문제 설명최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다.최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한 컴퓨터까지 포함하여 총 몇 대의 컴퓨터가 감염되며 그에 걸리는 시간이 얼마인지 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/10282      제한 사항      풀이문제를 요약하면, 여러 컴퓨터로 이루어진 그래프가 존재하고 특정 컴퓨터를 시작으로 바이러스가 감염된다.이때,..