PS
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)..
BOJ 1931 회의실 배정
boj 1931 회의실 배정 그리디 알고리즘 문제의 풀이 흐름에 따라 풀었다. 현재 시간을 t라고 할 때, t이상의 회의들 중에 가장 먼저 끝나는 회의를 선택하는 것이 최선이라고 생각했다. 증명까지는 하지 못했고, 그림을 그려보고 당장 손해이지만 나중에는 이득인 경우가 있나 확인해보았다. 입력 받은 회의의 시간들을 끝나는 시간이 빠른 순으로, 끝나는 시간이 같을 때는 시작하는 시간이 빠른 순으로 정렬한 후에 가장 먼저 끝나는 회의를 찾는 방식으로 구현했다. #include #include #include using namespace std; int N; int ans = 0; int t = 0; pair p[100005]; bool compare(const pair& p1, const pair& p2) ..