https://www.acmicpc.net/problem/15624 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 피보나치 수 문제인데 범위가 커져서 1,000,000,007로 나누는 문제이다. 나머지 분배법칙에 대해 자세히 알고있지 못하여 살짝 해맸는데 나머지 분배법칙만 잘 알고 있으면 dp를 사용하여 쉽게 풀수 있는 문제이다. 나머지 분배법칙의 증명은 다음 블로그를 참고하였다. https://sexycoder.tistory.com/66 모듈러 연산의 성질과 증명 모듈러 연산의 성질과 증명 위와 같이 모듈러 연산은 나머지를 구하는 연산자이며 다음의 분배법칙이 모두 성립한다. 왜 이런지 궁금해서 계속 ..
분류 전체보기
https://www.acmicpc.net/problem/19946 19946번: 2의 제곱수 계산하기 263 = 9,223,372,036,854,775,808 까지는 계산을 잘 하다가 264를 264-1인 18,446,744,073,709,551,615로 계산을 잘못해버렸다. www.acmicpc.net 문제에서 2의 제곱을 곱하다가 실수로 1을 빼버리는 순간이 단 한 번 존재한다고 하고, 실수할 때가 언제인지 구하라고 합니다. 풀이는 두 가지가 존재합니다. 첫 번째 풀이 첫 번째는 2의 제곱은 계속 짝수만 나오는데, 1을 빼버리면 그때 한 번 홀수인 값이 존재한다는 것을 이용하는 풀이입니다. 이 경우에는 홀수인지 짝수인지 확인하면서 짝수면 2로 계속 나누면 되지만, 홀수가 나오는 순간부터는 1을 더해..
https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net 문제 풀이 첫번째 줄에서 얻은 값들을 n이라는 리스트에 저장하고, 두번째 줄부터 입력되는 탐사 영역의 각 구간들을 source라는 2차원 리스트를 생성하여 값을 저장한다. 동시에 각 구간에서의 최댓값을 저장할 result라는 2차원 배열을 source와 같은 크기로 생성한다. wook는 오른쪽이나 아래쪽으로 한 칸씩만 이동하기 때문에 바로 전에 다녀온 길은 위쪽이나 왼쪽에서의..
https://www.acmicpc.net/problem/11944 11944번: NN 첫 번째 줄에는 N, M이 주어진다. (1 ≤ N, M ≤ 2016) www.acmicpc.net 문제 코드 #include using namespace std; #include #define PI 3.141592653589793 #define ll long long string str; int main() { ios::sync_with_stdio(0); cin.tie(0); string n; int m; cin >> n >> m; int len = n.length(); int num = stoi(n); if (len*num
BOJ 17626번 Four Squares 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net * 한 게시글에 코드 블록 언어를 하나로 통일해야 해서 Python 코드는 하이라이트가 정상적이지 않습니다ㅠ Intro 처음에는 Python으로 DP를 사용하여 풀이하려 하였으나 계속해서 시간 초과가 발생했습니다. 구글링을 통해 DP를 사용한 Python 풀이를 찾아보았으나 거의 동일한 코드를 돌려도 시간 초과가 발생했습니다. (테스트 케이스가 최근 추가됐거나 발견하지 못한 부분에서 효..
문제 풀이 N의 범위가 20만, 집의 위치의 범위가 10억이므로 이분 탐색을 이용하여 풀어야 한다. 집의 개수가 아닌, 두 공유기 사이의 최대 거리에 초점을 맞춰 반복문마다 값을 수정해야 한다. 탐색하고자 하는 거리의 범위를 0부터 arr[N-1]로 설정하여 모든 값을 탐색할 수 있도록 한다. 최솟값과 최댓값의 평균을 탐색값으로 설정하고, 이 거리를 기준으로 몇 개의 공유기를 설치하는 지 검사한다. 이 값과 문제에서 주어진 공유기의 개수를 비교하여 이 값이 크거나 같다면(최대거리를 출력해야 하므로) 거리의 범위를 크게하고, 공유기의 개수가 크다면 거리의 컴위를 작게한다. 반복을 완료한 후 right 값을 출력하면 문제가 해결된다. 코드 import java.io.*; import java.util.*; ..
https://www.acmicpc.net/problem/8958 문제 내 코드 'O'가 연속해서 나올 경우 추가되는 점수가 점점커진다. sum1에 eve를 더해주는 구조로 하고 'O'가 나오다가 끊겼을때 eve를 다시 1로 초기화한다. 입력받은문자열의 길이만큼 반복해준뒤 sum1을 출력한다. 문제풀이
문제 링크 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다. 예제 입력 ACAYKP CAPCAK 예제 출력 4 ACAK Solution 풀이 유투브 시간복잡도 O(N**2), N은 최대1,000 총 1,000,000번의 계산 최대 문자열 길이 구하기는 기존 LCS문제와 동일 for i in range(1,len(a)+1): for j in range(1,len(b..
8자리의 양의 정수가 주어질 때 그 안에서 연속하여 같은 숫자가 나오는 구간 중 가장 긴 것의 길이를 출력하는 문제이다. 일단 우선적으로 생각할 수 있는 것이 0번째부터 7번째 까지(여덟자리 라고 하였으므로) loop를 돌면서 검증을 하는 것인데, 이 때 ★지금 현재 위치에 있는 것과 바로 뒤 꺼를 비교할 때 for문 범위가 벗어나는 것이 가장 큰 문제였다. 따라서 양의정수와 아무 연관이 없는 문자 a를 붙인 다음에 loop를 그냥 0~7를 돌면 된다. 이후 if문을 선행하는 순서대로 나열한다.! 주석에 구체적인 설명이 있다 for i in range(3): s=input() #일단 연속해서 나오는 게 있는지 검증 s+='a' max=1 t=-1 sum=0 #연속하는 게 있다. 이제 연속하는 숫자들의 개..
https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 분석 여는 괄호와 닫는 괄호로 이루어진 문자열이 주어지고, 주어진 괄호들의 쌍이 올바른지 확인하는 문제이다. 입력으로는 표준입력을 사용하며, T개의 테스트 데이터로 주어진다. 입력의 첫번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어지고, 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다..
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 백트래킹으로 푼다. int arr[ ] : 수열을 담을 배열 bool isused[ ] : 특정 수가 쓰였는지를 나타내는 배열 func(k)는 현재 k개 까지의 수를 택한 상황에서 arr[k]를 정하는 함수이다. base condition을 설정한다(m개를 모두 택했을 때) 재귀함수를 이용한다(base condition으로 수렴) => 1부터 n까지의 수에 대해 아직 i가 사용되지 않..
dictionary형태로, key값에 따른 value값을 업데이트함으로써 최대 value를 가지는 key값을 추출하는 코드이다. 일단 주의해야 할 것은 print(dict[3])이런식으로 하면 key값이 아닌 value값이 나온다는 사실! 그래서 애초에 dict의 key값들을 .keys()로 모아둔 다음에 출력하는 편이 낫다. 코드를 자세히 설명하자면 동아리의 key값을 각각의 이름으로 지정하고 모두 0으로 초기화시킨다. 이후 n으로 동아리원을 입력받고 가장 최대로 문제를 푼 사람을 대표로 내세우기 때문에 L보다 큰 값이 나올 때마다 값을 다시 갱신시켜준다. ☆이후 '가장 큰 value값을 가지는 key를 가지고 오는 함수는 max_key = max(딕셔너리 이름, key=딕셔너리이름.get)으로 구현할..
