전체 글

문제 설명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      제한 사항      풀이문제를 요약하면, 여러 컴퓨터로 이루어진 그래프가 존재하고 특정 컴퓨터를 시작으로 바이러스가 감염된다.이때,..