본문 바로가기

전체 글

 (47)
BOJ 11727 2×n 타일링 2 https://www.acmicpc.net/problem/11727 - 11726번을 풀었다면 바로 풀 수 있는 문제 - 풀면서도 스스로 놀람.. 점화식을 잘 세우자! #include int d[1005]; int main(){ int n; scanf("%d", &n); d[0]=1; d[1]=1; for(int i=2; i
BOJ 11726 2×n 타일링 https://www.acmicpc.net/problem/11726 - DP - 문제 자체는 상당히 어렵게 느껴졌는데 막상 풀고나니 그리 어려운 문제는 아니었음 : 이런것이 DP구나 - 최종 출력은 10007로 나눈 나머지를 나타내야 하는데 for문 바깥에서 출력할 때 %계산을 했는데 틀렸다. : overflow - 계산할 때 마다 나눠줘야 함. for문 안에서 d[]에 넣을 때 %계산하니 통과. #include int d[1005]; int main(){ int n; scanf("%d", &n); d[0]=1; d[1]=1; for(int i=2; i
BOJ 1463 1로 만들기 https://www.acmicpc.net/problem/1463 - DP를 이용해서 푼 첫번째 문제. - 점화식을 세우는 것이 중요하다! - DP에서는 [ 재귀 또는 for문 ] 을 이용하여 문제 solve 가능 당연히 for문 이용한 것이 시간복잡도 적게 걸린다. #include int d[1000010]; int main(){ int n; scanf("%d", &n); d[1]=0; for(int i=2; id[i/2]+1){ d[i]=d[i/2]+1; } if(i%3==0 && d[i]>d[i/3]+1){ d[i]=d[i/3]+1; } } printf("%d", d[n]); return 0; }
BOJ 4963 섬의 개수 - DFS(x,y,cnt)로 넘겼을 때 0ms - BFS(x,y,cnt)로 넘겼을 때 4ms - BFS(x,y)로 넘겼을 때 0ms - w, h의 위치를 잘 보고 입력 받아야 한다. https://www.acmicpc.net/problem/4963 * DFS 풀이 #include using namespace std; int map[52][52]; int visited[52][52]; int w,h,cnt; int dx[8]={-1,0,1,-1,1,-1,0,1}; int dy[8]={1,1,1,0,0,-1,-1,-1}; void dfs(int x, int y, int cnt){ visited[x][y]=cnt; for(int i=0; i=0 && ny>=0 && nx
BOJ 2667 단지번호붙이기 - 큐를 이용하여 BFS 탐색하는 기본 문제 - 두번째 풀 때는 단지 내부에 있는 집의 개수를 세기 위해 vector를 이용하려고 했는데 잘 안됐다. 다음 번에는 벡터로 풀어봐야겠다. - DFS 로도 풀어봐야겠다! https://www.acmicpc.net/problem/2667 #include #include #include #include using namespace std; int n, cnt; int map[26][26]; int visited[26][26]; int ans[26*26]; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; void bfs(int x, int y, int cnt){ queue q; q.push(make_pair(x,y)); visited[..
BOJ 2468 안전 영역 DFS https://www.acmicpc.net/problem/2468 - BOJ 2667 단지 번호 붙이기와 유사 문제 - DFS로 풀었음 - 사실 처음엔 문제 이해가 되지 않았음. 높이가 주어지는 것이 아니었고, 모든 높이를 고려했을때 섬(?)이 많은 것을 print 하면 된다. - 주어진 입력에서 가장 큰 숫자를 저장하여 그 숫자부터 내림차순으로 탐색하였음. - 높이가 새로 정의 될 때마다 visited 배열 초기화해야한다. #include #include #include using namespace std; int map[110][110]; int visited[110][110]; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; int n, cnt; int ans[110*..
BOJ 10026 적록색약 - BFS 함수를 두 번 호출 하여 해결. - 첫번째 호출 시 적록색약 아닌 사람 계산 후 두번째 호출 위해 초기화 할때 R을 G로 변경하고 두번째 호출 때 G와 B만 남으므로 그대로 BFS 계산 https://www.acmicpc.net/problem/10026
BOJ 2583 영역 구하기 DFS - Y 좌표가 뒤집어져 있어서 input 할 때 헷갈렸다. - DFS, recursion으로 해결 - 영역 갯수, 영역 크기 모두 구해야 한다. https://www.acmicpc.net/problem/2583 #include #include using namespace std; int board[110][110]; int visited[110][110]; int ans[110*110]; int dx[4]={-1,0,0,1}; int dy[4]={0,-1,1,0}; int m, n, k; void dfs(int x, int y, int cnt){ visited[x][y]=cnt; //영역번호. for(int i=0; i=0 && nx=0 && ny

티스토리툴바