Jaegu's Algorithm Blog

여러 테스트케이스가 주어질때, vector의 resize함수를 호출한다고 vector안의 내용들이 초기화 되지는 않음에 유의하자! 항상 하나의 테스트케이스가 끝나면 vector clear함수를 호출하자!

1.  C++로 아래처럼 구현 2.  python으로 구현

아래 문제에서 error를 출력할때 continue를 입력했을경우, break 대신에 error가 무기한 출력이되는 문제가 발생한다. BAPC 2012 문제의 테스트 케이스를 분석해보고 나서야 깨달았다............. 주의해야 겠다

수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. 출처 : wikipedia

bool comp(const pair<int, int> &p1, const pair<int, int> &p2) { if (p1.second == p2.second) {     //second 가 같으면 return p1.first < p2.first; //first 작은게 앞으로 } return p1.second > p2.second;    //second 다르면 second가 큰게 앞으로 }

strcmp를 사용하기 위해서 <cstring> 추가

path1,2를 구할때 뿐만아니라, d배열또한 int범위를 넓혀야 한다.

cin.ignore();

주요 개념은 해를 얻을 때까지 모든 가능성을 시도한다는 점이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 깊이 우선 탐색을 사용한다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아간다. 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우, 이 문제의 해결책은 없는 것이다. 퇴각검색은 보통 재귀 함수로 구현된다. 재귀로 파생된 해결 방법은 하나 이상의 변수가 필요한데 , 이것은 현재 시점에서 적용할 수 있는 변수값들을 알고 있다. 퇴각검색은 깊이 우선 탐색과 대략 같으나 기억 공간은 덜 차지한다. 현재의 상태를 보관하고 바꾸는 동안만 차지한다. 탐색 속도를 높이기 위해, 재귀 호출을 하기 전에 시도할 값을 정하고 조건(전진 탐색의 경우)을 벗어난 값을 지우는 알고리즘을 적용할 수 있다. 아니면 그 값을 제외한 다른 값들을 탐색할 수도 있다.

1번째 행부터 시작해서 column을 순차적으로 돌면서 dp값을 갱신한다.

채점한 학생의 점수가 모두 같다는 말에는, 책상이 연속적으로 위치해있어야한다는 조건이 숨어있다.

#include <cstdio> #include <iostream> #include <vector> using namespace std; int main(void) {     int N,K;     int result[10001] ={0,};     scanf("%d %d",&N,&K);     vector<int> vec;     for (int i=0; i<N; i++){         int input;         scanf("%d",&input);         vec.push_back(input);     }          //중복을 제외하는 법은 아래와 같이 한번만 계산해야될 부분을 바깥 loop에 감싼다.     for (int i=0;i<vec.size();i++)     {         for (int j=1;j<=K;j++){             if ((j-vec[i]) < 0)                 continue;             if ((j-vec[i]) == 0)                 result[j]+=1;             else          ...