어흥

문제 링크: www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 1. 주의할 점 - 한 학생이 자신의 순서를 정확히 아는 경우: 앞에서 몇번째인지 + 뒤에서 몇번째인지 2. 구현 - 모든 순서에 대한 정보를 V[] 벡터에 담는다. 이때, 앞에 나온 수 V[A]에 뒤에 나온 수 B를 추가한다 - 모든 학생들에 대해서 단방향 BFS를 수행하며 해당 학생이 몇명의 다른 학생에게 도달이 가능한지(자기보다 큰 사람)를 canReach[]++를 통해 저장하며, 도달당한 학생..

문제 링크: www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 1. 주의할 점 - 모든 섬에 양이 최대치로 존재 -> 합해지는 과정에서 Int의 범위를 벗어날 수 있다 2. 구현 - 위상정렬의 풀이법으로 접근했다 - Info 구조체를 통해 해당 지점을 도착지점으로 설정한 섬의 수(Conn), 다음 섬으로 연결된 곳(To), 생물의 수(Val)를 나타낸다 - 섬에 늑대가 존재하면, 생물의 개수를 음수로 저장한다. - Info의 성격에 맞게 Ar..

문제 링크: www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 1. 주의할 점 - DFS를 통해 수행하므로, 갱신 + 원복을 잘 처리해야 한다 - 처리해야 하는 변수가 많아 헷갈릴 수 있으니 잘 정리하고 시작한다 2. 구현 - 8방향 탐색을 원활하게 처리하기 위해, 입력받을 때 각 물고기의 방향-1값을 저장한다 - 물고기의 정보를 Fish[]구조체에 담는다. 구조체는 행, 열, 진행방향으로 구성되어있다 - 현재 물고기의 위치는 Arr[][] ..

문제 링크: www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 1. 주의할 점 - DFS, BFS, MST, 한줄 모두 가능 - 허무주의 2. 구현 [BFS] - 시작점을 1로 잡고(아무점이나 상관없다) Queue에 넣고 BFS를 수행한다. 방문하지 않은 Node가 있으면 Result++하고 Queue에 넣는다 #include #include #include using namespace std; vector v[1001];..

문제 링크: www.acmicpc.net/problem/20419 20419번: 화살표 미로 (Easy) 첫번째 줄에는 미로의 행 R, 열 C, 준서가 가진 주문서 세트의 개수 K가 주어진다. 두번째 줄부터 R줄에 걸쳐 화살표 미로의 지도가 입력된다. 각 줄마다 "UDLR"로만 이루어진 길이 C의 문자열이 입 www.acmicpc.net 1. 주의할 점 - 주문서는 최대 1개 가질 수 있다 - 주문서는 왼쪽, 오른쪽 회전 1개가 세트다 2. 구현 - 미로를 입력받으면서 Check[][] 배열을 3으로 초기화시킨다. Check[][] 배열은 해당 지점에 몇개의 주문서를 사용해서 도착했는가?에 대한 정보를 담고있다 -> 시간절약위해 사용 - DFS()를 수행하며, 변수로는 Y, X, 사용한 오른쪽회전 주문서..

문제 링크: www.acmicpc.net/problem/9944 9944번: NxM 보드 완주하기 N×M 보드 위에서 할 수 있는 게임이 있다. 보드는 크기가 1×1인 정사각형 칸으로 나누어져 있다. 보드의 각 칸은 빈 칸 또는 장애물이다. 장애물은 아래 그림에선 어두운 사각형으로 표시되어져 www.acmicpc.net 1. 주의할 점 - EOF를 입력 받을때까지 수행한다 - 매 TC마다 초기화를 진행한다 - 백트레킹으로 진행하므로 사용을 다 했다면, True->False로 꼭 바꿔준다 2. 구현 - Cin>>row>>col을 통해 EOF를 입력 받을때까지 수행한다 - Arr[][]배열을 입력받으면서 Check[][] 배열을 초기화한다 - 만약 공을 놓을 수 있는 자리라면, 해당 자리의 Check[][]..

문제 링크: www.hackerrank.com/challenges/torque-and-development/problem Roads and Libraries | HackerRank Help the ruler of HackerLand determine the cheapest way to give his citizens access to libraries. www.hackerrank.com 1. 주의할 점 - 범위를 잘 확인한다 - 각 쿼리마다 초기화를 잘 수행한다 - 입력받은 길 중에서, 도서관을 1개 세우는 경우: (Cnt-1)*C_road + C_lib만큼의 비용이 발생하고 각각 도서관을 세우는 경우: Cnt*C_lib만큼의 비용이 발생한다. 즉 C_road>=C_lib일때, 각각 도서관을 세우면 된다..

문제 링크: www.hackerrank.com/challenges/magic-square-forming/problem Forming a Magic Square | HackerRank Find the minimum cost of converting a 3 by 3 matrix into a magic square. www.hackerrank.com 1. 주의할 점 - 매직 스퀘어를 이루는 경우가 몇개 없어서 전부 작성하고 풀 수 있지만, DFS로 풀 경우 가로 세로 대각선의 합이 항상 15가 되야 한다 - 중앙의 값은 무조건 5여야 한다 2. 구현 - 입력받은 S벡터의 중앙값이 5가 아니라면, 5로 바꾼 이후 차이만큼 Cnt값을 추가하며 DFS()를 시작한다 - 중앙이 5이므로, 중앙을 기준으로 정의될 수 ..