문제:https://www.acmicpc.net/problem/11444난이도: 골드 2단순히 피보나치 수를 구하는 문제. 다만 n이 무지막지하게 큰.아이디어 1처음에는 분할 정복을 어떻게 쓸지 생각이 안 떠올랐다. 그렇게 고민을 하다가 피보나치 수를 직접 나눠서 써보기로 하였다.우선 n이 짝수일 때이다. n=2k일 때 k번째 항까지 분할을 하였다.f(10)을 예시로 들어봤다. 2개로 계속해서 나누었을 때 항의 개수가 피보나치수열을 이루는 것을 알 수 있다. n/2까지 과정을 반복해 보면 다음과 같은 식을 얻을 수 있다.다음은 n이 홀수 일 때다.n=k//2+1이라 할 때 k번째 항까지 분할하였다. 일반항으로 나타내면 다음과 같다.나도 왜 이런 식이 나오는지는 모른다. 2시간 정도 노트에다가 끄적여보며 ..

오늘 공부한 내용 & 푼 주요 문제1629 - 곱셈(실버 1)https://www.acmicpc.net/problem/1629오랫동안 이해하지 못했던 문제. 책을 보고 그제서야 이해하고 풀었다. 분할 정복이라는게 뭔가 쉬우면서도 어려운거같다. 12865 - 평범한 배낭(골드 5)(업로드됨)https://www.acmicpc.net/problem/12865주어진 무게의 최솟값을 맞추며 가치를 최대로 이끌어내는 문제. 이 또한 문제점을 오랫동안 찾지 못했던 문제이다. 내 풀이가 dp인줄 알았으나 완전 탐색이어서 dp의 형태로 변형하여 풀이를 이끌어냈다. dp의 개념을 잘못 알고 있었던거 같기도 하다. 15654 - N과 M (5)(실버 3)https://www.acmicpc.net/problem/15654백..

문제:https://www.acmicpc.net/problem/12851난이도: 골드 4숨바꼭질(실버 1)의 확장판. 숨바꼭질 같은 경우는 visited를 0과 1로 체크해 주면서 이동하면 bfs로 해결할 수 있었지만, 최단 경로의 개수를 구해야 하므로 단순히 0과 1로만 체크를 하면 안 된다는 걸 알 수 있다. 아이디어 1처음에는 단순 bfs를 변형해서 풀 생각을 했다. 최솟값을 찾으면 그걸 저장해 주고 개수를 세주다가 더 작은 최솟값이 나오면 갱신해서 다시 세주는 방식으로 끝까지 세어줬다. 시도 1from collections import dequen,k = map(int,input().split())c=[0]*100001d=deque()d.append(n)c[n]=1s=0check=Truemin_s..

문제:https://www.acmicpc.net/problem/12865정석적인 dp 문제이나... 이해하는데 꽤나 애를 먹었다. 다음 문제를 위해 정리해서 글을 끄적여본다.아이디어1우선 처음에는 이중 for문을 돌면서 리스트에다가 가능한 모든 조합을 넣어서 max 값을 뽑아냈다.(난 이게 완전 탐색인지도 몰랐다) 시도1from collections import dequen,k=map(int,input().split())w=[0]*nv=[0]*nfor i in range(n): w[i],v[i] = map(int,input().split())d=deque()c=0for i in range(n): d.append((w[i],v[i])) for j in range(0,len(d)-1): ..

오늘 공부한 내용 & 푼 주요 문제9657 - 돌 게임 3(실버 3)https://www.acmicpc.net/problem/96579659 - 돌 게임 5(실버 3)https://www.acmicpc.net/problem/96599660 - 돌 게임 6(골드 5)https://www.acmicpc.net/problem/96609661 - 돌 게임 7(골드 2)돌 게임 시리즈를 풀어봤다. 전반적으로 dp에 대한 기본적인 이해를 요구했고, 9660,9661은 이를 토대로 일반항을 세워 O(1)의 시간복잡도를 요구하는 문제였다. 돌 게임 시리즈의 마지막 문제인 돌 게임 8은 이를 더 일반화 하는 내용인데, 이에 대한건 조금 더 공부를 하고 풀어봐야겠다. 1439 - 뒤집기(실버 5)https://www.ac..

다음 달에 우리 학교에서 코딩 대회가 열린다. 여차여차해서 내가 출제자로 뽑히긴 하였으나... 출제자라 부르기엔 너무 실력이 부족하다. 또한 출제자 요건 중 하나가 바로 백준 1000문제 이다. 따라서 오늘부터(7.7) 1000문제 도전기를 시작한다. 목표우선 내 목표는 다음과 같다.1000문제 달성플레 5 달성클래스 6 달성계획하루마다 오늘 푼 문제와 공부한 내용을 정리해서 올릴 것이다. 그 중 실버 이상의 문제는 따로 간단한 주석을 달아둘거고, 그 중 골드 이상의 문제는 따로 문제풀이 글을 남길것이다.우선 목표는 하루에 20~30문제씩 푸는 것이다. 그럼 어림잡아 1000문제 푸는데 25일 정도가 걸릴 것이고, 대회 일자랑 비슷하게 맞출 수 있다. 여기서 5문제 정도는 실버 이상으로 맞춰서 플레5를 ..

문제:https://www.acmicpc.net/problem/9663 n*n 격자판 위에 n개의 퀸을 배치할때, 퀸이 서로를 공격하지 못하게 배치하는 경우의 수를 구하시오.백트래킹을 이용하는 굉장히 유명한 문제이다.아이디어백트래킹을 이용해서 위쪽 줄부터 차례대로 재귀함수를 사용해 탐색하면서 내려가면 된다.이때 겹치는 세로줄,대각선을 체크하여 들어갈 수 있는지 확인하기 위한 리스트를 만든다. 우하향,우상향 대각선을 분리해서 생각해주었다. 퀸이 있는 자리에 배열 값을 바꿔주면서 내려와서 마지막줄에 도달하면, count +=1을 해주어 개수를 세었다.각 x,y에서 col1,diag1,diag2의 어떤 값이 올지 생각해주는게 관건이었던거 같다.정답 코드n=int(input())col1=[0]*n#세로diag1..

문제:https://www.acmicpc.net/problem/1074 1인 경우, 배열을" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/1074" data-og-url="https://www.acmicpc.net/problem/1074" data-og-image="https://scrap.kakaocdn.net/dn/tjWnJ/hyTBHl0I87/73TRFfjERJ85Pv9iBfzzCK/img.png?width=2834&height=1480&face=0_0_2834_1480,https://scrap.kakaocdn.net/dn/buCrT6/hyTBDjCCnG/dr3twovjDIx5zTxPwgXnH1/..