PS/BOJ
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) ..
BOJ 11047 동전 0
boj 11047 동전 0 그리디 알고리즘을 활용하여 풀 수 있는 문제여서 적용하여 풀어보았다. DP를 활용한 풀이도 생각할 수 있는 문제이지만, DP를 활용할 경우 O(NK)의 시간복잡도로 시간초과가 나와 그리디를 활용해야만 하는 문제였다. 그리디 알고리즘 문제의 풀이 흐름에 따라 풀어보았다. 직관적으로 높은 금액의 동전을 최대한 많이 사용할 수록 동전 갯수가 적어질 거라고 생각했다. 위 생각을 증명해보았다. 간단하게 하기 위해 동전의 가치가 10, 50, 100, 500원 뿐이라고 한다. '동전을 최소로 소모하여 값을 지불하기 위해서는 500원은 최대한, 100원은 4개 이하, 50원은 1개 이하, 10원은 4개 이하로 사용해야한다' 를 증명해보자. 증명을 편히 하기 위해 먼저 '..