전체 글
BOJ 11726 2xN 타일링
boj 11726 2xN 타일링 간단한 DP 문제이다. DP가 무엇인지를 다시 생각해보면, 하위 문제들을 먼저 푼 후 그것들을 쌓아올려 주어진 문제를 해결하는 알고리즘이다. DP 문제를 풀 때 중점은 테이블을 정의해주고, 그 테이블의 제일 하위 값들이 무엇일까를 생각하며 점화식을 찾는 것이다. 먼저 테이블 설정을 해보면, D[i] = 1x2, 2x1 타일로 채우는 경우의 수 라고 정의하자. 전체 경우의 수 D[i]는 아래 그림과 같이 맨 끝의 한 칸을 1x2 타일이 채우는 경우와 맨 끝의 두 칸을 2x1 타일 2개가 채우는 경우 2가지로 나뉜다. 맨 끝이 3칸이 남는 경우는 더 채우면 결국 앞의 2가지와 겹치기 때문에 생각할 필요가 없다. 그러므로 점화식을 D[i] = D[i-1] + D[i-2]로 설정..
BOJ 1920 수 찾기
boj 1920 수 찾기 예시로 A 배열에 '3 5 6 9 10 12 14 26 35 41' 이 주어졌다고 하고, 14가 있는지 알아본다고 하자. 입력 받은 후에 sort 함수를 이용해서 정렬하면 앞과 같이 정렬된 상태일 것이다. 원래 문제는 A 안에 14가 있는지만 확인하면 되지만, 14가 A 안에서 위치하는 인덱스를 반환하는 함수를 구현해보려고 한다. st와 en은 14가 있을 수 있는 범위의 처음과 끝 인덱스를 의미한다. mid는 (st+en)/2 이다. A[mid]와 14의 값을 비교하며 st와 en의 값을 계속 바꿔나갈 것이다. 만약 A[mid] > 14 이면, 14는 mid와 en 사이에 있음이 자명하고, 그러므로 st = mid+1 이라고 할 수 있다. 만약 A[mid] < 1..
BOJ 6603 로또
boj 6603 로또 숫자를 입력 받아 지정하고 그 갯수의 숫자 중 가능한 6개 조합을 모두 출력해야하는 문제이다. 백트레킹 기법을 이용하여 문제를 해결했다. #include #include using namespace std; int k; vector s; vector l; void func(int num) { if (s.size() == 6) { for (int i = 0; i l[i]; func(0); cout
BOJ 2667 단지번호붙이기
boj 2667 단지번호붙이기 간단한 bfs 구현 문제였다. 단지의 수는 지도를 돌면서 bfs를 도는 횟수를 구해주면 되고, 단지의 면적은 큐에 들어갈 때마다 1씩 증가시키면 된다. 코드에서 num은 단지의 수, area는 단지의 면적, v는 각 단지의 면적을 넣어줄 벡터이다. #include #include #include #include #include using namespace std; string board[27]; bool vis[27][27]; int N; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,-1,0,1 }; int num; vector v(num); int main(void) { ios_base::sync_with_stdio(0); cin.tie(0)..
BOJ 11652 카드
boj 11652 카드 간단하게 모든 카드의 수를 세보는 O(N^2) 풀이법이 가장 먼저 떠오르지만, 시간 초과이다. 일단 먼저 정렬을 하여 같은 값들을 다 붙였다. 그리고 mxval는 현재까지 가장 많이 등장한 수의 값, mxcnt는 현재까지 가장 많이 등장한 수의 등장한 횟수, cnt는 현재 보는 수가 등장한 횟수를 의미하고, mxval = -2^62-1, mxcnt = 0, cnt = 0으로 초기화하였다. 현재 보는 수가 제일 앞의 수이거나 직전의 수와 같은 값이면 cnt를 1 증가시킨다. 그리고 직전의 수와 다른 값을 가지면 cnt를 다시 1로 초기화시켜준다. cnt가 mxcnt보다 커지면 mxval과 mxcnt를 바꿔준다. 시간복잡도는 정렬하는데 O(NlogN)이고 카드들의 수를 보는데 O(N)..