https://www.acmicpc.net/problem/5710 5710번: 전기 요금 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 두 정수 A와 B가 주어진다. (1 ≤ A, B ≤ 109) 항상 정답이 유일한 경우만 주어지며, 입력으로 주어지 www.acmicpc.net 구현과 이분탐색을 적절히 섞어놓은 문제였습니다. 아이디어로는 상근이가 아예 전기를 안쓴 경우(0 Wh)부터 전기를 전부 썼을 경우(A Wh) 사이를 이분탐색으로 구하는 것입니다. 이분탐색의 규칙으로는, 중앙값을 상근이가 사용한 전기의 양, 총사용량에서 중앙값을 뺀 값이 이웃이 사용한 전기의 양이고 이웃-상근이의 값이 B이면 이때의 상근이의 전기요금을 반환, 아니면 이분탐색을 하도록 ..
C++
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 아리스토텔레스의 체로 소수 벡터를 구하고, 투포인터로 답을 구하는 문제였습니다. 문제를 처음 접하고, N의 범위가 400만까지 가는 것을 보고 아리스토텔레스의 체로 구하면 시간이 괜찮을까..? 싶어서 소수판별 관련된 이것저것 찾아봤는데, 아리스토텔레스의 체의 시간복잡도는 Nlog(logN)) 으로 생각보다 좀 많이 빨랐습니다. 머쓱 소수 벡터를 구한 이후로는 여타 투포인터 문제풀이를 하듯, 앞에서부터 포인터 2개로 둘 사이의 총합을 구해가며 총합이 n인 경우의 수를 구하면 됩니다. #include #include u..
https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1
https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 크기가 N인 배열이 주어지고, 각 칸에는 1 이상 N 이하인 정수가 들어갔을 때, 만들 수 있는 모든 사이클의 노드 개수와 노드를 정렬하여 출력하는 문제이다. 문제를 처음 접하였을 때, 모든 사이클이 아닌 가장 큰 사이클을 찾는 것이라 착각했는데, 경험의 부족인듯 하다(...) 루프 또한 사이클이므로 입력단계에서 미리 처리해주고 루프가 아닌 사이클을 모두 찾는 순서로 구현하였다. #i..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net dp Table을 그리면 쉽게 점화식을 구할 수 있는 문제였다. dp Table의 각 칸은 모든 경우의 수를 직접 써내려가며 구해도 되지만, 순열공식을 통해 더 빠르게 구할 수 있다. 예를 들어, n=5, k=3 일 때 각 조합의 경우의 순열의 개수는, (3,0,0) -> 3!/2! = 3 (2,1,0) -> 3! = 6 (1,1,1) -> 3!/3! = 1 따라서, 3+6+1 = 10 위와 같이 n=8, k=4 까지 구한 dp Table은, k\n 1 2 3 4 5 6 7 8 1 1 1 1 1 1 1 1 1 2 2 3 4..
이분탐색은 오름차순 정렬된 배열에서 특정 값을 찾아 인덱스를 반환하는 search algorithm입니다. 코드는 다음과 같습니다. int binarySearch(int A[], int x, int low, int high){ int mid; if(low>high) return -1; else{ mid = (low+high)/2; if(A[mid]==x) return mid; else if(A[mid]>x) return binarySearch(A,x,low,mid-1); else return binarySearch(A,x,mid+1,high); } } low와 high의 초기값은 각각 탐색하고자 하는 배열의 처음 인덱스와 마지막 인덱스입니다. 즉 mid는 현재 탐색하고 있는 배열의 가운데 인덱스를 가리키..
https://www.acmicpc.net/problem/2011 >s; int size = s.size(); if(s[0]=='0'){ cout
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번호가 공백으로 구분되어 주어진다. 사이트 주소는 알파벳 소문자, 알파벳 대문자, 대시('-'), 마침표('.')로 이루어져 있고, 중복되지 않는다. 비밀번호는 알파벳 대문자로만 이루어져 있다. 모두 길이는 최대 20자이다. N+2번째 줄부터 www.acmicpc.net 사이트 주소와 비밀번호를 페어로 묶은 벡터를 정렬하여, 이분탐색으로 사이트 주소의 위치번호를 찾아내면 쉽게 풀 수 있는 문제이다...
