공부하자

https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 처음엔 중복제거를 통해 해결해야하나 고민하던 찰나 구글링으로 vector에서 집합 관련된 연산을 간단히 수행할 수 있게 해주는 라이브러리가 있다 해서 활용해보았다. 입력의 최댓값이 200,000이기에 코드의 시간복잡도가 O(N^2)가 될 수 없기에 라이브러리를 활용해 간단히 해결해보았다. 대칭 차집합 뿐만 아니라 다른 합집합, 교집합 등의 연산들도 같은 라이브러리 안에서 수월하게 적용할 수 ..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net C++에서 기본으로 제공하는 map contaier에 관한 문제이다. 이 문제를 푸는데 있어서 두가지 중요한 관건은, 첫째, 입력받은 변수의 data-type이 int인지 string인지 판별할 수 있는 코드가 삽입되어야 한다. 각각의 케이스를 조건문으로 분기하여 따로따로 처리해주야 한다. 둘째, map에서 find 함수를 활용하여 값들을 찾게되는데, 이때 key와 v..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 10815번 문제와 비슷한 듯 다른 문제다. 다른 점이라 하면, 시간제한이 1초라는 점인데, 처음에 10815번 문제와 같이 set 컨테이너를 이용하여 풀었더니 시간초과가 나왔다. set에서 find나 count를 쓴다 해도 O(logN)의 시간복잡도를 가지는데, 이것이 반복문 안에서 움직이다 보니 시간초과가 뜨는 듯했다. 따라서 map을 사용하여 find나 c..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 저번 글이었던 7785번과 상당히 유사한 문제다. set을 이용하는 문제이며, set 컨테이너를 이용해야겠다고 마음먹고는 거진 10분만에 풀어버렸다. 문제 난이도 또한 상당히 쉽다. 하지만, 최댓값이 500,000이기에 O(N^2)인 경우 시간초과가 나지않을까 잠깐 걱정했으나, set컨테이너에서 특정 값을 찾는 find 메소드의 시간복잡도는 O(logN)에 불과하기 ..

https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 결과적으로 set을 사용하면 아주 쉽게 풀수있었던 문제인데, vector, 그것도 pair형 vector를 선언하고 탐색 및 삭제를 알아보다가 시간초과가 났고, 계속 구글링을 하며 돌파구를 찾아보다가 시간을 많이 버린 문제이다. 반복문 안에서 O(N)짜리 erase와 remove를 때리고 있으니 시간초과가 안나는것이 이상하지. 처음부터 set으로 가닥을 잡고..

https://www.acmicpc.net/problem/2903 2903번: 중앙 이동 알고리즘 상근이는 친구들과 함께 SF영화를 찍으려고 한다. 이 영화는 외계 지형이 필요하다. 실제로 우주선을 타고 외계 행성에 가서 촬영을 할 수 없기 때문에, 컴퓨터 그래픽으로 CG처리를 하려고 한다. www.acmicpc.net 결과값의 규칙성을 찾아 일반항을 구하고 재귀함수를 이용하여 풀면 금방 풀린다. 하지만, math 헤더의 pow를 바로 출력하려다가 지수표기법으로 출력되면 틀렸다고 판정되니, 이 부분만 주의하여 풀면 될 듯 하다. #include #include using namespace std; int arr[16]; long long int f(int a) { if (a==1) return 3; el..

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 백준 단계별 풀어보기 정렬 탭에서 가장 티어가 높았던 문제였다. 높다해도 실버2 정도기에 vector 정렬을 이용한다면 간단히 풀 수 있었다. 하지만 이 문제의 관건은, 주어지는 N의 범위가 최대 1,000,000이므로, 최대한 O(N^2)를 이용하지 않고 풀어내는 것이다. 필자 또한 처음에 기본 반복문 안에 vector를 find하는 함수를 넣..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 실버5로 어려운 문제는 아니지만 아주 오랜만에 백준을 풀면서 기록해둘것이 좀 많아 쓰게 되었다. 풀이 풀이방식은 간단하다. int와 string을 쓰는 pair형 vector에 단어 길이와 단어를 입력받고 정렬한 뒤, 중복제거를 해주고 출력해주면 끝이다. 구현 #include #include #include using namespace std; int main(void) { int N;..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 알고리즘 분류는 이진탐색으로 되어있지만, 그냥 투포인트 방식으로도 풀리는 문제였다. 오히려 그게 시간 효율이 더 좋을수도..? 풀이 알고리즘은 간단하다. int형 벡터에 숫자를 입력받아서 오름차순로 정렬해주고, 왼쪽 끝과 오른쪽 끝 이렇게 두 포인터를 이동시키며 가장 0에 가까운 값이 될때까지 포인터들을 갱신해주면 된다. 구현 #include #include #i..

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 간단한 그리디 알고리즘 문제로, 조금만 다르게 생각해본다면 쉽게 풀 수 있는 문제다. 풀이 가장 단순하게 브루트포스를 이용하여 모든 인덱스를 전수조사하는 방법도 있겠지만, 그렇게 될 경우 반복문 2개를 사용하게 되어 연산 횟수가 10B 가 된다. 따라서, 반복문 하나만으로 해결해야 하는 문제이다. 다음 특성만 생각하면 무척 쉬운 문제이다. 1. 지원자 중, 두 심사의 등수 모..