본문 바로가기

알고리즘119

[백준] 1780 종이의 개수 예전에 풀어봤던 문제인데 해맸다. 0,1,-1의 개수를 세어 주고 n*n개 인지 비교하고 아니면 분할하는 방식으로 했는데 왜인지 계속 정답이 안나왔다. 재귀가 잘못된건지 뭐가 잘못된건지 못찾아서 다른 방식으로 했다. 하나라도 다른 것이 있으면 분할하고 아니면 카운트 해주었다. #include #include using namespace std; int nn,temp; int num[2200][2200]; int ans[3]; int check; void division(int x, int y, int n) { check = num[x][y]; for (int i = x; i < x + n; i++) for (int j = y; j < y + n; j++) { if (num[i][j] != num[x][y.. 2022. 6. 4.
[백준] 2839설탕배달 c++ dp문제이다. 2중 for문을 통해서 풀어줬다. 3키로 봉지와 5키로 봉지와 조합을 해서 만들 수 있는 무게여야하고 최소의 개수의 봉지를 사용해야한다. sugar[3]과 sugar[5]를 1로 초기화 해줬다. 해당 무게를 만들 수 있는 조합을 안에 있는 for문으로 다 검사해주어서 최소의 개수를 sugar[i]에 넣어주었다. #include #include using namespace std; int sugar[5001]; int main() { int n; cin >> n; for (int i = 0; i < 5001; i++) sugar[i] = 5000; sugar[3] = 1; sugar[5] = 1; for (int i = 3; i 2022. 5. 28.
[백준 ] 2042 구간합 구하기 C++ 두번째 풀었던 것임에도 놓쳤던 부분 1.배열 크기를 int 로 했다.-> long long으로 해야한다. 2. 세그먼트 트리 크기를 num 배열이랑 똑같이 해줬다. -> 4배 해야한다. 3.(start+end)/2 로 해야하는데 start+end/2로 했다. ->코드 꼼꼼히 작성하기 4. 함수를 호출할때 num배열은 0에서 N-1까지이기 때문에 start=0,end=N-1로 해줘야하는데 1과 N으로 했다. 다음에는 num배열을 1부터 입력을 받아야겠다. +(b인덱스의 값을 c로 바꾸는 부분도 틀렸다.) 5. 배열의 값을 갱신 시켜줄때 원래 값과 차이를 이용하면 되는데 까먹었다. 다시 한번 풀어봐야겠다. #include #define MAX_TREE (1 right || end < left) return .. 2022. 5. 22.
[알고리즘 문제 해결 전략] 02 알고리즘 분석 - 알고리즘의 정당성 증명review 도입 단위 테스트는 알고리즘에 문제가 있음을 증명할 수 있지만 없음을 증명할 수 없다. 알고리즘의 정확한 증명을 위해서는 각종 수학적인 기법이 동원되어야 한다. 알고리즘 증명을 공부해야 하는 이유 : 증명이 알고리즘을 유도하는 데 결정적인 통찰을 담고 있기 때문. 수학적 귀납법과 반복문 불변식 수학적 귀납법 : 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법 단계 나누기 -> 첫 단계 증명 -> 귀납 증명 반복문 불변식 (loop in - variant ) : 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지 명시하는 조건 이진 탐색에서 int binsearch (const vector&A,int x){ int n =A.size(); .. 2022. 5. 22.

티스토리툴바