어흥

문제 링크: www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 주의할 점 - 다익스트라나 플로이드 와샬 알고리즘에 대해 알고 있어야 한다 2. 구현 - 플로이드 와샬 알고리즘(시간복잡도: O(N^3)로 50^3 < 10^9)을 사용하여 구한다 - 간선들의 정보를 입력 받기 전, Dist[][] 배열을 1000으로 초기화한다 - 간선들의 정보를 입력받은 후, 플로이드 와샬을 통해 IJ 까지의 최소 간선 수를 구한다 - 1~N번까지의 사람들 중에서 가장 먼 ..

문제 링크: 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.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/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 1. 주의할 점 - 투 포인터를 이용하여 푼다. 매번 K개의 종류를 센다 -> TLE 2. 구현 - Arr[] 배열을 통해 연속된 K개의 초밥 중에 해당 종류의 초밥이 몇개 속해 있는지 나타낸다. Cnt를 통해 서로 다른 종류의 수를 나타낸다 - 벨트에 놓인 초밥의 종류를 Dish벡터에 담는다. 쿠폰을 사용하여 먹을 수 있는 초밥은 미리 표시한다. 동시에..

문제 링크: www.hackerrank.com/challenges/max-array-sum/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dynamic-programming Max Array Sum | HackerRank Find the maximum sum of elements in an array. www.hackerrank.com 1. 주의할 점 - DP로 풀지 않고 일반 DFS로 풀 경우, TLE발생 - DFS + DP 즉, 메모이제이션으로 풀 수 있다 2. 구현 - DP[][]배열을 통해 [현재 Index][현재 Arr[]값 사용 여부] 형태로 최대값을 저장한다. 단, Arr[] 벡..

문제 링크: www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 1. 주의할 점 - 음수/0/양수로 나눈다 - 음수의 경우, 0과 관련지어서 생각한다 - 양수의 경우, 1일 때 조건을 추가한다 2. 구현 (이해가 안되는 부분은 코드에 주석을 달았으니 확인 바람) - 수를 입력 받을 때, 음수인 경우 M에 양수인 경우 P에 추가한다. 0인 경우, Zero++를 수행한다 - 음수의 경우 오름차순으로, 양수는 내림차순으로 정렬한 이후, 음수->0->양수 순서대로 A..

문제 링크: www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. 주의할 점 - 원하는 숫자가 idx번째에 있다면, 서로 다른 두 수는 idx를 사용하여 만들어지면 안된다. 문제 설명이 모호하게 되어있다 3 0 0 3 -> 답: 0 2. 구현 - 투 포인터를 이용하여 풀이한다 - 입력 받은 수들을 오름차순으로 정렬하여 투포인터의 필요조건을 만족시킨다 - 0~N-1까지 모든 수에 대해 이분탐색을 수행한다 - Left는 0, Right는 N-1부터 수행한다 - 두 수가 같으면 안되므로 Le..

문제 링크: www.hackerrank.com/challenges/crush/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays Array Manipulation | HackerRank Perform m operations on an array and print the maximum of the values. www.hackerrank.com 1. 주의할 점 - 각 쿼리를 입력 받을 때 마다 모든 배열에 값을 추가하지 않는다 -> TLE 발생 2. 구현 - 아이디어가 떠오르지 않아서 Discussion에 적혀 있는 다른 사람의 풀이를 참조하여 해결했다. - 방법은 현재 배열의 값: 현..