boj, 백준) 2252. 줄 세우기 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 2. 문제 개요 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 했다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 3. 문제 힌트 위상 정렬을 사용해보자. 4. 문제 풀이 문제를 푼 사람도 많고, 정답률도 높..
boj, 백준) 14725. 개미굴 ( C++ )
1. 문제 링크 www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 2. 문제 개요 개미 로봇이 개미굴을 탐사하면서 보내온 신호를 토대로 개미굴의 구조를 파악하는 프로그램을 작성하기. (문제가 복잡해서 링크를 타고 들어가서 읽어보는 걸 추천합니다.) 3. 문제 힌트 트라이를 구현해보자.(트라이에 대한 기본 지식이 있어야 함) 그리고, 자식노드를 만들 텐데 정렬을 편하게 하기 위해 map을 사용해보자. 4. 문제 풀이 이 문제는 알고리즘 뿐만아니라 ..
boj, 백준)16946. 벽 부수고 이동하기 4 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 2. 문제 개요 N x M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 하는데, - 벽을 부수고 이동할 수 있는 곳으로 변경 한다. - 그 위치에서 이동할..
boj, 백준) 17387. 선분 교차2 ( C/C++ )
1. 문제 링크 www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2. 문제 개요 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있으면 교차하는 것이다. 3. 문제 힌트 여러 가지 예외 케이스들을 생각해보자. 가장 기본적인, 두 선분이 교차하는 것에서 시작해서.. 이런 다양한 경우가 있을 수 있다. 어떻게 예외를 처리해야 할까 4. 문제 풀이 많은 예외처리를 다룬 선분 교차 알고리즘을 다른 블로그에서도 많이 올려놓아서 자..
boj, 백준) 12781. PIZZA ALVOLOC ( C / C++)
1. 문제 링크 www.acmicpc.net/problem/12781 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 2. 문제 개요 볼록 다각형 모양인 피자에서 정점 네 개를 선택하여, 2개의 선분을 만든다. 이 선분이 서로 교차하여 피자가 4조각으로 잘리게 되면 1, 그렇지 않으면 0을 출력하는 프로그램을 작성하자 3. 문제 힌트 선분 교차 알고리즘이다. CCW(외적)을 이용해서 문제를 해결한다. 더 복잡한 2차원 평면에서의 선분교차가 아니고, 볼록 다각형 모서리에서의 정점을 선택하기 때문에 많은 제약이 삭제된다. 종이 ..
boj, 백준) 16933. 벽 부수고 이동하기 3 ( C/C++ )
1. 문제 링크 www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 2. 문제 개요 NxM의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 나는 (1, 1)에서 (N, M)의 위치까지 이동하려고 하는데, 이때 최단 경로로 이동하려 한다. 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게..