어흥

문제 링크: www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 1. 주의할 점 - TC가 여러개 + 언제 끝나는지 알려주지 않음 -> EOF가 입력될 때까지 받는다 - 서로 다른 2 조각 사용 - TC마다 V 벡터 초기화 2. 구현 - if(cin>>len)을 통해 EOF를 입력 받았다면 false를, 아니라면 true를 입력 받기 때문에 EOF를 입력 받는다면 Break로 While문을 빠져 나간다 - 입력 받는 조각들을 오름차순으로..

문제 링크: www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. 주의할 점 - 세 포인터가 아닌 1개 고정 + 두 포인터를 이용해 해결한다 - 포인터가 겹칠 수 없다 - 정답을 오름차순으로 출력한다 2. 구현 - 모든 수를 Arr[] 배열에 받은 후, 오름차순으로 정렬한다 - Result를 3000000001로 설정하여 이보다 0에 가까운 값을 가질 경우, Ans[] 배열과 Result값을 갱신하도록 한다 - 가장 왼쪽의 포인터 K를 ..

문제 링크: www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 1. 주의할 점 - 모두 비교할 경우, 최악의 경우 O(N*M)으로 TLE가 발생한다 - 둘중 하나는 lgN이나 lgM으로 바꿔야 TLE가 발생하지 않는다 - 사대의 X값이 정렬되어 있지 않다. 왜? 2. 구현 - 입력 받은 사대 Arr[]를 오름차순으로 정렬한다 - 동물들의 위치를 X[], Y[]에 할당 받는다 - 각 동물을 기점으로 사대까지의 거리가 Len보다 작거나 같다면, Result++하고..

문제 링크: www.hackerrank.com/challenges/sherlock-and-anagrams/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps Sherlock and Anagrams | HackerRank Find the number of unordered anagramic pairs of substrings of a string. www.hackerrank.com 1. 주의할 점 - substring 길이에 따라 다른 Map에 저장한다 - 정렬을 이용한다 2. 구현 - 최대 길이 100까지 담을 수 있는 Map[]을 생성한다. Map은 형태로..

문제 링크: 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/minimum-swaps-2/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=arrays Minimum Swaps 2 | HackerRank Return the minimum number of swaps to sort the given array. www.hackerrank.com 1. 주의할 점 - O(N^2)이 발생하지 않도록 한다 2. 구현 - 현재 위치에 맞는 값이 들어있는 경우 다음 값을 확인한다 - 맞는 값이 들어 있지 않은 경우, 현재 위치에 있는 값 Num과 Arr[Num-1]의 값을 스왑한다(배열의 번호는 0부터..

문제 링크: www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 1. 주의할 점 - 4개의 수를 어떤 방식으로 뽑을 것인지 잘 생각한다 - 정렬 이후, 인접합 4개를 조작하여 답을 구할 경우, 반례가 존재한다. 반례) 6 1 2 1000 2000 10001 10002 답: 0 2. 구현 - 조합을 통해 2개 공의 합이 나타낼 수 있는 높이를 벡터에 저장한다. 이때, 벡터는 사용한 번호 2개, 2개의 합 총 변수가 3개인 구조체 형태..