분류 전체보기

문제 설명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..

문제 설명그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.https://www.acmicpc.net/problem/1197      제한 사항      풀이문제를 요약하면, 최소 스패닝 트리를 만들고 가중치를 출력하는 것이다.최소 스패닝 트리란, 그래프의 모든 노드를 포함하는 최소 가중치 트리를 말한다. 최소 스패닝 트리를 구하는 방법은 크게 두 가지이다.크루스칼 알고리즘프림 알고리즘 해당 문제에서는 크루스칼 알고리즘을 사용하였다.크루스칼 알고리즘은 간선 리스트를 통해 최소 스패닝 트리에 포함되는 노드를 확장하는 방법이다.우선, 간선리스트의 가중치를 ..

문제 설명세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자.첫 번째 단어 : cat두 번째 단어 : tree세 번째 단어 : tcraete보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째 단어를 만들 수 있다. 아래와 같이 두 번째 예를 들어보자.첫 번째 단어 : cat두 번째 단어 : tree세 번째 단어 : catrtee이 경우 역시 가능하다. 그렇다면 "cat"과 "tree"로 "cttaree"를 형성하는건 불가능하다는걸 눈치챘을 것이다.      제한 사항      풀이문제를 요약하면, 두 단..

문제 설명각 노드가 자식을 최대 K개 가질 수 있는 트리를 K진 트리라고 한다. 총 N개의 노드로 이루어져 있는 K진 트리가 주어진다.트리는 "적은 에너지" 방법을 이용해서 만든다. "적은 에너지" 방법이란, 이전 깊이를 모두 채운 경우에만, 새로운 깊이를 만드는 것이고, 이 새로운 깊이의 노드는 가장 왼쪽부터 차례대로 추가 한다.아래 그림은 노드 9개로 이루어져 있는 3진 트리이다.노드의 개수 N과 K가 주어졌을 때, 두 노드 x와 y 사이의 거리를 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/11812      제한 사항      풀이문제를 요약하면, N개의 노드를 K진 트리로 만들어 Q개의 쿼리를 처리하면 된다.Q개의 쿼리는 주어지는 두 노드의 거리를 구하는..