그리디 알고리즘 3의 배수일 조건 : 각 자릿수의 합이 3의 배수여야 한다. 10의 배수일 조건 : 1의 자릿수가 0이어야 한다. 30의 배수일 조건 : 3의 배수이면서 10의 배수이어야 한다. -문제 풀이 1. 예외 조건을 처리한다. 2. 예외 조건에 걸리지 않는다면 맨 뒷자리에 0을 놓고 나머지를 정렬한다. -예외 조건 1. 주어진 숫자에 0이 포함되지 않을때. 2. 각자리수 합이 3의 배수가 아닐 때. -소스 코드 #include #include using namespace std; int main() { int hap=0; //3의 배수인지 아닌지 판단하기 위한 변수 int arr[1000001]; string a; cin>>a; for(int i=0;i

dfs로 푸는 문제 노드를 하나씩 돌면서, 각각의 노드가 갈 수 있는 최대 횟수를 벡터에 저장한다. 처음에는 배열로 만들었지만, 최대 크기가 10000*10000이나 되서, 연결 여부를 배열로 만들면 시간 초과가 나온다. 또, 방문 여부를 판단하는 배열을 한 번씩 돌 때마다 초기화 시켜주어야 한다. 처음에는 초기화 시켜주지 않았지만, 최대길이가 짧은 노드부터 방문하게 된다면 최대 방문 순위를 재대로 셀 수 없게 된다. 풀이 과정 1. vector 배열을 만들어, from을 index로, to를 vector 배열에 push 한다. 2. 연결된 두 쌍을 찾아, dfs를 돌린다. 그 후 진행하는 횟수를 arr배열에 저장한다. 3. 오름차순 정렬이므로, arr배열에서 max값을 찾아 그와 동일한 값을 갖는 배열..

전형적인 bfs를 이용해서 푸는 문제. 시간 복잡도 : bfs이고, 인접행렬로 구했으므로 o(n^2) 소스코드 #include #include #include #include using namespace std; int connected[101][101]={0,}; bool visited[101]={false,}; int counts[101]={0,}; int p,rel,from,to; void bfs(int start) { visited[start]=1; queue q; q.push(start); while(!q.empty()){ int now=q.front(); q.pop(); for(int i=1;i>p>>from>>to>>rel; for(int i=1;i>a>>b; connected[a][b]=1..

#include using namespace std; int main() { int width,height; cin>>height>>width; if(height ==1){ cout

그리디 알고리즘. 벡터를 두개 만들어서 한 쪽에는 음수만, 한 쪽에는 양수만 저장. 각각 정렬을 각각 해준다. 큰 수끼리 곱하면 그 곱도 최대가 됨을 이용한다. 음수 * 음수 = 양수, 양수* 음수 = 음수 임을 이용한다. 예외 1 ) 1의 경우, 아무와도 짝짓지 않는 것이 유리하다. ex) 2 *1 =2 , 2+1=3 예외 2) 0의 경우, 홀수의 갯수가 홀수일때 곱해주면 음수를 하나 없앨 수 있다. 소스코드 #include #include #include using namespace std; vector pluss; vector minuss; int ans; int main() { int num,a; cin>>num; //벡터 두개에 각각 음수, 양수를 넣어준다. for(int i=1;i>a; if(..

그리디 알고리즘을 사용하는 문제. 간단히 생각해보면, 앞에 부터 채워나간다고 생각하면 편하다. 이미 채워져있다면 넘어가고, 채워지지 않았다면 채우는 과정을 반복한다. // 1. 오름차순 정렬 // 2. 맨 왼쪽꺼 0.5 떨어진 지점에 테이프를 붙임 +1 // 3. 다음 지점 앞뒤로 + 0.5지점에 테이프가 붙어있다면 // 3-1 . 3번이 true라면 다음 지점으로 건너 뛰고 3번으로 // 3-2 . 3번이 false라면 2번으로 간다. #include #include using namespace std; //0.5처리하기 싫으니까 다 두배로 하자. int arr[4000]={0}; bool check[4000]={false}; int main() { int n,l,count=0; cin>>n>>l; l..

dfs를 통해 풀어 볼 수 있는 문제. 처음에는 비정상인을 카운팅할때 로직을 하나 더 짜야하나 고민했지만,, 생각해보니 적록색약은 녹색과 빨간색을 구별하지 못한다. 따라서 모든 빨간색을 녹색으로 바꾸어놓고 풀거나, 모든 녹색을 빨간색으로 바꾸어 놓고 풀어도 정답은 동일하다. 그렇게 바꿔놓은 다음 dfs를 돌리자. #include using namespace std; int num,count=0; char map[101][101]; bool visited[101][101]; //앞,뒤,위,아래로 이동가능 int dx[5]={0,-1,0,0,1}; int dy[5]={0,0,1,-1,0}; //이전에 방문한 것과 색깔이 동일하다면 그곳으로 이동한다. void dfs(int startX,int startY) ..

dfs를 사용해서 사이클을 찾는 문제. 계속 답을 넣어도 예제는 맞는데 답은 틀리게 나오고 반례도 도저히 못 찾겠어서 다른 블로그 보고 푼 문제. 다 맞게 풀고 MAX의 크기를 너무 크게 잡아서 에러가 뜬 것 같다(..) 로직 자체는 동일하니.. 왜 런타임 에러로 안 뜨고 그냥 "틀렸습니다"가 뜨는지... 처음 입력 받은 수를 A라고 하자. 규칙에 따른 수를 생성해 나가면서, 그 수를 인덱스로 가지는 배열의 값을 방문 할 때마다 1씩 늘인다. 사이클이 있다면 그 사이클을 돌텐데, 그럼 그 사이클에 해당하는 배열 값들이 늘어날 것이다. 사이클을 2번 돌리면? 사이클에 있는 수들이 전부 다 2가 되겠지. 그리고 또 사이클에 들어가면 사이클에 있는 첫 번째 값이 3이 되면서 함수를 종료시킨다. 소스 코드 #i..