c++34 [BOJ] 15829. Hashing 백준 온라인 저지에 있는 15829번 Hashing 문제 풀이입니다. 문제: https://www.acmicpc.net/problem/15829 처음에는 31^i를 구하는 부분에서 pow(31, i)를 썼더니 부분 점수를 받았습니다. L이 커졌을 때 pow(31, i) 부분 때문에 시간복잡도가 엄청나게 커졌나봐요. 31^i는 1, 31, 31*31, 31*31*31 ... 이라서 이전 31^i에 31을 한번 더 곱하기만 하면 되는데 괜히 필요없는 함수를 호출하면서 시간복잡도를 크게 만들어버렸어요... 그래서 아래와 같이 바꿨더니 전체 정답이 되었습니다! 중복되는 부분, 생략할 수 있는 부분을 고민하면서 짜야하는데 나름 신경쓰다가도 생각없이 짤 때가 있네요... 반성해야겠습니다. 🤧 ❗️중복되는 부분, 생.. 2020. 5. 1. [BOJ] 11050. 이항 계수 1 백준 온라인 저지에 있는 11050번 이항 계수 1 문제 풀이입니다. 주어지는 자연수 N과 K에 대한 이항 계수를 구하는 문제입니다. 이항 계수란 N개의 수 중에서 K개를 고르는 경우의 수로 아래와 같이 구하면 되는데요. 딱 보고 떠오르는 생각은 각각의 팩토리얼을 구해서 계산하면 되겠네~ 였습니다. 여기서❗️ 줄일 수 있는 중복되는 부분이 있는데요. 팩토리얼이 1부터 N까지를 차례대로 곱한 수이잖아요. 그리고 n-k와 k는 둘다 N보다 작을 것이구요. 그럼 둘중에 하나는 계산을 생략하고 n!에 바로 나눠줬다고 생각하면 중복되는 부분이 줄어들겠더라구요. 글로 이해가 잘 안가실수도 있어서 예제에 있는 숫자로 예를 들어보면 N=5, K=2의 이항계수는 5*4*3*2*1 / (3*2*1)*(2*1) 이런식이 됩.. 2020. 5. 1. [BOJ] 1920. 수 찾기 key 값으로 수를 쉽게 찾기 위해 set 자료구조를 사용하였습니다. https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. www.acmicpc.net #include #include using namespace std; int N, M; set numbers; int main() { cin.tie(0); cout.tie(0); ios::sync.. 2020. 3. 25. [BOJ] 11650. 좌표 정렬하기 좌표를 저장할 클래스를 만들고 vector로 좌표들을 관리하였습니다. 그리고 이를 요구사항에 맞는 비교 함수를 정의하여 정렬하였습니다. https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net #include #include #include using namespace std; class Location { public: int x; int y; Location(int _x, int _y) { x =.. 2020. 3. 25. 이전 1 2 3 4 ··· 9 다음
