알고리즘/BOJ24 [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] 2345. 풍선 터뜨리기 백준 온라인 저지에 있는 2346번 풍선 터뜨리기 문제 풀이입니다. 🎈🎈🎈 문제 N개의 풍선이 있다. 각 풍선 안에는 -N부터 N까지의 수가 적혀있는 종이가 들어 있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다. 우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 풍선은 원형으로 놓여 있다고 생각한다. 즉, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있는 것이다. 이동할 때에는 이미 터진 풍선은 빼고 생각한다. 예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. .. 2020. 4. 27. [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. 이전 1 2 3 4 ··· 6 다음
