백준

백준 10816 풀이 (숫자 카드 2, 이분 탐색, 해쉬 사용, Counter)

이번 문제는 Counter를 사용해서 해결했다. 기본적인 이분 탐색과 풀이에 차이가 전혀 없다. 단지 Counter를 이용해서 Dict형태로 만들어 주고 중복값을 제거하여 이분 탐색을 진행하게 만들었다. 1. Counter를 이용해서 중복을 제거한 Adict를 얻는다. 2. Adict에서 key값만 뽑아서 중복이 제거된 Alist를 얻는다. 3. Alist를 오름차순으로 정렬한다. 4. 이분탐색을 이용하여 해당되는 값을 구한다. 5. 해당 되는 값을 구할 수 있다면 Adict에서 몇개나 존재하는지 출력한다. 위의 순서로 코딩을 진행하면 쉽게 풀 수 있다. from collections import Counter n = int(input()) AC = Counter(list(map(int, input()...

백준 1920 풀이 (수 찾기, 이분 탐색)

오늘 알고리즘 수업시간에 교수님이 설명해 주셨던 이분 탐색문제다. 문제는 원리는 크게 어렵지 않다. 1. start와 end의 중간인 mid를 정한다. 2. mid의 위치에 찾으려는 i 값과 비교한다. 3. 같으면 리턴한다. mid보다 i의 값이 크면 start=mid+1, mid보다 i가 작으면 end = mid-1을 해준다. 4. 찾을때까지 반복하다가 start < end를 만족하지 않으면 루프를 벗어난다. 이걸 코드로 짜면 아래와 같다. 단, 비교하려고 하는 리스트가 정렬되어 있는 경우에만 사용가능하다. n = int(input()) A = list(map(int, input().split())) A.sort() m = int(input()) B = list(map(int, input().split..

백준 11444 풀이 (피보나치 수 6, 분할 정복, 행렬 제곱)

이 문제 정말 엄청난 삽질을 했다. 심지어 풀지도 못해서 풀이 찾아보니 아주 잘 정리한 식이 있었다. 그걸 사용하는 건가 보다. 이걸 사전지식 없이 어떻게 푼다는건지 정말 똑똑한 사람들...... 처음 접근은 예전에 페르마의 소정리를 이용해서 풀려고 했다. 위키백과에 피보나치를 구하는 일반항이 존재했다. 생긴게 마치 예전에 풀었던 문제랑 비슷해서 비슷한 방식으로 2^n*5**0.5를 p-2승 해서 풀려고 했다. 그런데 문제가 루트때문인지 음수 제곱때문인지 자꾸 수가 망가져서 나누어 떨어지지도 않고 계산이 안되었다. 더구나 n승 만큼 제곱을 해주면 inf값이 나와서 계산이 안됐다. 그래서 삽질을 한참하다가 고수들 풀이를 구경갔더니 피사노 주기라는 키워드도 알게 되었고, 행렬제곱으로 피보나치를 구하는 일반항..

백준 10830 풀이 (행렬 제곱, 분할 정복, 거듭제곱)

이번 문제는 이전문제들을 이용하여 풀면 아주 쉽게 풀 수 있다. 1. 분할 정복을 이용하여 거듭제곱을 구할수 있다. 2. 행렬제곱을 구할수 있다. 이 2가지가 가능하면 상당히 쉬운 문제이다. 그런데 정답률이 낮고 solved.ac에서 골드4인것은 좀 의문이다. 문제를 보면 행렬에 대해서 제곱을 하는 문제이다. 행렬을 제곱한다는것은 같은 놈을 여러번 곱한다는 소리다. 만약 행렬을 A라고 한다면 분할 정복을 이용하여 n을 아주 빠르게 구할 수 있다. $$ A^n = A^{n/2}*A^{n/2}$$ $$ A^{n/2}=A^{n/4}*A^{n/4}$$ 위의 식을 이용하면 분할하여 빠르게 A의 n승 행렬을 구할수 있다. 단, n이 홀수인 경우에는 n이 정확히 나누어 떨어지지 않기 때문에 $$ A^n = A^{n/..

백준 2740 풀이 (행렬 곱셈)

이 문제는 어렵지는 않았지만 살짝 귀찮은 문제였다. 나는 당연히 무식하게 for 돌려서 풀었다. import sys n,m = map(int, sys.stdin.readline().split()) a = [] for _ in range(n): a.append(list(map(int,sys.stdin.readline().split()))) n2,m2 = map(int, sys.stdin.readline().split()) b=[] for _ in range(n2): b.append(list(map(int,sys.stdin.readline().split()))) final = [] for i in range(n): t = a[i] total = [] for j in range(m2): tmp = [] t =..

백준 11401 풀이 (이항 계수 3, 페르마의 소정리, 정수론, 분할알고리즘)

이번 문제는 너무나 어려웠다. 처음에는 어떻게든 풀어보려고 이항계수 강의도 듣고, 페르마의 소정리도 찾아보며 어떻게 풀어야할지 고민하기 시작했다. 물론 이게 하루이틀이지 계속 생각해도 안풀려서 고수의 도움을 받았다ㅋㅋㅋㅋ 여튼 내가 이해한 것을 천천히 정리해보자. 문제를 보면 1초의 시간제한이 존재한다. 또한 N값이 4,000,000으로 상당히 큰 수이다. 마지막으로는 1,000,000,007로 나눈 값을 출력하면 된다. 우선 이항계수를 공부하며 몇가지 규칙을 알게 되었다. 이항 계수를 한방에 이해할 수 있는 파스칼의 삼각형이다. 여기를 보면 규칙을 찾을수 있다. 규칙은 nCk = n-1Ck-1 + n-1Ck 이며 이것을 구하는 식을 나타내면 아래와 같다. 그러나 문제는 이러한 방식으로 엄청나게 큰 수를..

백준 1629 풀이 (곱셈, 분할정복, 파이썬)

이번 문제 상당히 어려웠다. 심지어 풀이로직보고 코드를 짜보았는데 96%까지 올라가고 계속 틀리길래 진짜 머가 문제인지 한참 헤맸다. 문제를 보면 어찌보면 상당히 간단하다. a**b % c를 하면 시간이 상당히 오래걸리니까 이걸 분할정복으로 풀어보라는 소리다. 솔직히 이거 재귀쓰면 더 오래걸릴거 같아서 손을 계속 못댔다. 그래서 고수의 풀이를 살짝 봤더니 b를 분할해서 구하는 것을 알 수 있었다......ㄷㄷ 천재인가 진짜 상상도 못했다. 분할이니까 무언가를 분할해야한다고 생각했다면 접근했을수도 있었지만 재귀면 무조건 오래걸린다는 생각에 갇혔던 것이었다....... 여튼 원리는 아래와 같다. 10**10 = 10**5 x 10**5 로 만들 수 있다. 10**5 = 10**2 x 10**2 x 10 으로..

백준 1780 풀이 (종이의 개수, 재귀, 파이썬)

이번에는 이전보다 더 분할하는 문제를 풀어본다. 문제는 그냥 머랄까 이전에는 반을 나누었다면 이번에는 3등분하는 문제였다. 사실 코드적인 부분이 많이 달라지지 않았다. 저번에는 반으로 나누는 과정을 조금 무식하게 풀었는데, 이번에는 3등분을 해야하다보니 조금더 깔끔하게 처리하려고 노력했다. 막상 비교하려고 놓고 보니 별로 큰 차이가 없어보이네;;ㅎㅎ 여튼 이러한 방식으로 풀면 되는거라 이전 문제와 크게 다른점이 없었다. 처음 제출했을때 틀렸다고 해서 당황했는데 알고보니 0개수를 1개수랑 바꿔놓고 풀었었다. 정신 차리고 풀어야 겠다. import sys n = int(sys.stdin.readline()) nr1 = 0 n0 = 0 n1 = 0 def check(p): global nr1 global n0..