어흥

문제 링크: www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 1. 주의할 점 - 출력에 있어 3가지의 경우가 있다 - 정답이 여러개인 경우, 사전순으로 앞선 경우를 출력한다 2. 구현 - BFS를 통해 정답을 도출한다 - 최대 범위가 10^9이므로 곱셈 혹은 덧셈의 결과가 10^9를 넘기지 않도록 한다 - 사전순으로 빠른 순서대로 BFS 탐색을 시작하며, 연산 결과의 숫자가 존재하지 않는 경우, Set과 큐에 추가한다 - 큐에서 꺼낸 원소가 Targe..

문제 링크: www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 1. 주의할 점 - A와 B의 범위가 10만개 + 짝을 이루기 때문에 Set혹은 Map을 사용한다 2. 구현 - sInfo 구조체를 통해 A와 B 물통에 남은 물의 짝을 저장한다 - Info 구조체를 통해 A, B, 수행한 명령 수를 저장하고 우선순위큐는 수행한 명령 수의 오름차순으로 정렬한다 - 현재 시점으로 3가지의 과정을 수행해보고 Set에 없다면..

문제 링크: 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/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 1. 주의할 점 - 변수들을 헷갈리지 않도록 한다 - 초기화를 잘 처리해준다 - 특정 조건에 맞는 우선순위 큐를 사용하여 다음으로 태울 손님을 구한다 2. 구현 - 길에 대한 정보를 Arr[][] 함수에 저장한다 - 손님의 시작위치, 도착지점 위치를 P[][4] 배열에 담는다 - Need_fuel[] 배열에 대한 초기화를 수행한다. 해당 배열은 손님의 탑승위치..

문제 링크: www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 1. 주의할 점 - 한명의 상사에겐 여러명의 직속부하가 있을 수 있다 - 칭찬을 모두 저장했다가 트리의 순서에 따라 부여한다 2. 구현 - 모든 직원들에 대해 상사->직속 부하에 대한 정보를 V[]벡터에 저장한다 - 입력받은 모든 칭찬에 대해 해당 직원의 index번호에 해당하는 Compliment[]에 더한다(한 직원이 여러번 받았을 수도 있으므로 할당이 아닌 더하기) - 사장인 1번부터 시작하..

문제 링크: www.acmicpc.net/problem/1743 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진 www.acmicpc.net 1. 주의할 점 - BFS로 해결하도록 한다 2. 구현 - Check[][] 배열을 통해 음식물이 있는 좌표는 true로 갱신한다. 문제는 좌측 상단의 좌표가 (1,1)이므로 입력받는 좌표들에 대해 -1씩 한 좌표에 음식물을 표시한다 - 전체 Check[][] 배열에 대해 탐색을 시작하며, 음식물인 지점을 주변으로 4방향 탐색을 실시하여 음식물의 크기를 ..

문제 링크: www.hackerrank.com/challenges/find-the-nearest-clone/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=graphs Find the nearest clone | HackerRank Find the shortest path length between any two nodes with the given condition. www.hackerrank.com 1. 주의할 점 - BFS를 통해 해결하여 TLE가 나지 않도록 한다 - 방문여부를 기록해둔다 2. 구현 - 모든 간선에 대한 정보를 V[] 벡터에 담는다 - Idx: 현재 Node번호, Val..

문제 링크: www.hackerrank.com/challenges/castle-on-the-grid/problem Castle on the Grid | HackerRank Determine the number of steps to move a castle to the goal position on a given grid. www.hackerrank.com 1. 주의할 점 - 한쪽으로 기울이면 벽이 닿거나, 장애물에 닿을때까지 계속 움직일 수 있다. - 벽이나 장애물에 닿아야만 공이 멈추는것이 아니다 2. 구현 - Check[][]배열을 통해 해당 지점에 도달하기 위해 최소 몇번 기울였는지 구한다 - 공의 시작점을 Queue에 넣는다 - 4방향 탐색을 하며 공을 진행시킨다. 이때, 공이 벽이나 장애물에 닿..