전체 글

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

문제 설명2차원 평면상에 N(3 ≤ N ≤ 10,000)개의 점으로 이루어진 다각형이 있다. 이 다각형의 면적을 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2166      제한 사항      풀이문제를 요약하면, 주어진 점이 이루는 도형의 면적을 구하는 것이다. 도형은 삼각형이나 사각형과 같이 면적을 구하기 쉬운 도형일 수도 있고 절대 공식으로 구할 수 없는 일그러진 도형일 수도 있다.해당 문제를 풀기위해 고민하다 그래픽스의 내용이 떠올랐다.그래픽스에서 도형을 그릴 때 도형을 삼각형으로 나눠 그린다.즉, 해당 문제도 도형을 삼각형으로 나눠 삼각형의 면적의 합을 구하면 된다고 생각했다. 하지만, 실제로 삼각형의 면적을 구하는 법이나 진행방법을 알지는 못했다.풀이..

문제 설명수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/13913      제한 사항      풀이문제를 요약하면, +1, -1, *2를 이용하여 N부터 K까지 도착하는 최소 이동 횟수와 경로를 출력하는 것이다.BFS 혹은..

문제 설명간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.https://www.acmicpc.net/problem/15681        제한 사항      풀이문제를 요약하면, 주어진 정보로 트리를 만들고 쿼리로 주어진 노드의 서브트리의 개수를 구하는 것이다. 해당 문제에서는 트리를 만들 때, DFS를 통해 만들어주면 쉽게 문제를 풀 수 있다.DFS를 통해 트리를 만들다 리프 노드에 도착하면 순회를 종료하고 부모로 올라간다. 예를 들어, 1번 노드는 리프 노드이기 때문에 해당 노드의 서브트리는 존재하지 않는..

문제 설명효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.연속으로 놓여 있는 3잔을 모두 마실 수는 없다.효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 예를 들어 6..