https://www.acmicpc.net/problem/7578 7578번: 공장 어떤 공장에는 2N개의 기계가 2열에 걸쳐 N개씩 배치되어 있다. 이 2개의 열을 각각 A열과 B 열이라고 부른다. A열에 있는 N개의 기계는 각각이 B열에 있는 N개의 기계와 하나씩 짝을 이루어 케이블 www.acmicpc.net 주어진 A, B에 대해 같은 수끼리 이었을 때 교차점이 몇 개인지를 구하는 문제입니다. 예전에 풀었던 문제와 비슷하여 동일한 방식으로 풀었습니다. https://ghqls0210.tistory.com/152 백준 / 1517 버블 소트 C++ www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 ..
https://www.acmicpc.net/problem/2957 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 오랜만에 조금 높은 티어 문제를 풀었습니다. (사실 예전에 틀린 것... 뭔가 최악의 케이스에 걸려 시간초과가 떴었을 듯하다....) 문제에서 구하고자 하는 C 값은 사실 이진트리에서 루트부터 몇 개의 노드를 카운트하는 지를 구하는 문제입니다. 단 카운트 수가 누적됨에 주의합니다. 문제를 다 풀고 좀 찾아보니 단순 이진 탐색을 이용한 방법 외에 유니온 파인드를 이용해서도 풀 수 있음을 알게 ..
https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 개인적으로 아이디어를 떠올리기가 조금 까다로운 문제였습니다. dp를 어떻게 효율적으로 할 지 까다로웠지만 제가 사용한 방법은 다음과 같습니다. dp[ i ][ j ][ k ] = i번째에 j라는 수가 들어갔고 이 때 k만큼 체크된 상황 이라고 할 때 (1번째는 왼쪽을 기준입니다.) (체크는 비트스트링을 이용합니다.) dp[ i ][ j ][ k | (1
https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net map 자료구조를 이용해 풀었습니다. 피자를 n^2으로 start 번호부터 piece개 (정확히는 piece + 1개)를 돌면서 합을 구해줍니다. 그리고 map에 해당 합의 값을 찾아 +1 을 해줍니다. 최종적으로 맵 중 하나를 골라 iterator를 돌리면서 나머지 피자의 양을 다른 맵에서 찾아줍니다. 벡터에 넣고 바이너리 서치를 해도 될 거 같지만 map을 이용해도 풀릴 것..
https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 주어진 수열의 오른쪽에 있는 수 중 수열에 나온 횟수가 더 큰 가장 왼쪽의 수를 구하는 문제입니다. 예를 들어, 1,2,1,1,3,3,1 로 주어졌다면, 가장 오른쪽의 1보다 더 오른쪽의 수는 없으므로 -1, 그 다음 3은 2번 나왔지만, 오른쪽의 1은 4번 나왔으므로 1, 2의 경우 오른쪽의 1은 4번, 3은 2번 나왔지만, 2를 기준으로 1이 더 왼쪽에 있으므로 1이 정답입니다. 스택 2개를 이용해 스택에..