presentLee

그리디, 우선순위 큐 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 시간 범위로 입력이 들어오고 특정 시간이 그 범위에 껴있는 갯수가 최대인 값을 찾는다. 시작시간 순으로 정렬해서 보면서 시작했는데 끝나지 않은 수업의 갯수가 사용중인 강의실의 수. 강의 시간을 시작시간 순으로 정렬하고 이미 시작한 수업은 끝나는 시간을 기준으로 우선순위 큐에 넣는다. 끝날 시간이 되면 큐에서 빼고 시작한후면 뺀다. 큐의 크기가 필요한 강의실의 크기. #include #include #include #incl..

baekjoon 2024. 2. 27. 09:08

https://www.acmicpc.net/problem/6603 처음 푼 방문여부 배열로 체크하며 검사한 풀이 출력 조건만 보고 오름차순 조건과 방문여부 배열을 추가했지만 입력 조건에 원소가 오름차순으로 주어진다는 것을 확인하고 하단에 풀이를 추가 #include #include #include #include #include #include using namespace std; int arrsize; int arr[13]; int prarr[13]; bool check[13]; void back(int prev, int size); int main() { cin >> arrsize; while (arrsize != 0) { memset(check, 0, sizeof(check)); for (int i..

baekjoon 2024. 2. 26. 23:53

https://www.acmicpc.net/problem/1759 목록에서 필요한 갯수만큼 조건에 맞춰 탐색해 뽑아낸다. 백트래킹 사용해야 했던 문제 #include #include #include #include using namespace std; char str[20]; char arr[20]; int l, c; bool check[26]; void dfs(int index, int count); int main() { memset(check, 0, sizeof(check)); check[0] = check[4] = check['i' - 'a'] = check['o' - 'a']= check['u' - 'a'] = 1; cin >> l >> c; for (int i = 0; i < c; i++) {..

baekjoon 2024. 2. 19. 05:19

https://www.acmicpc.net/problem/1697 dp 문제라고 생각하고 풀다가 답이 안나와서 분류를 봤다. bfs로 풀 수 있는 문제였다. 이런느낌으로 연결된 그래프를 연상했다. dfs로 사용하면 모든 경우를 끝까지 가봐서 가장 작은 것을 선택 해야 겠지만 bfs를 사용 시에 같은 횟수로 먼저 도착했을 때 가장 최소 비용을 사용했다고 확인할 수 있으니 bfs를 사용. #include #include #include #include #include #include struct forq { int num; int count; }; using namespace std; bool check[100005]; int linenum, verticenum; int subin, sister; void ..

baekjoon 2024. 2. 18. 03:05

탑다운방식과 바텀업 방식 첨부. 삼각형 형태로 구성된 수를 한칸씩 타고 내려오며 총 합이 가장 큰 경로의 합을 찾는 문제 얼핏 보면 그리디로 풀 수도 있을 것 같지만 좌측처럼 그리디하게 당장 큰 것을 찾아 내려가면 실제로 가장 큰 경로가 되지 않는다. 많은 경우의 수를 비교하기 위해 dp를 사용해서 풀어야 했던 문제. 맨 위칸 값을 기준으로 시작해서 다음행의 같은열과 다음 열 값을 확인 해 더 큰 값을 dp에 저장한다. 마지막 행에 도달하면 해당 위치의 값을 그대로 반환해주면 될 것이다. top-down 방식 풀이 #include #include #include #include using namespace std; int arr[501][501]; int dp[501][501]; int inputnum;..

baekjoon 2024. 2. 17. 20:26

2*n 크기의 직사각형에 1*2 세로로 긴 직사각형과 2*1 가로가 긴 직사각형으로 채울 수 있는 방법을 우선 찾는다. 2*n에서 n이 커질수록 가로로 한칸이 길어진다. 채울 수 있는 것은 1*2나 2*1 사각형이므로 가로가 한칸 길어지면 1*2를 하나 넣을 수 있다. 3에서 4로 넘어갈때 파란색 테두리를 친 사각형들이 그 예시. 가로 길이가 n-2 인 경우에서 2*1을 위아래로 하나씩 배치해서 가로길이 n을 만드는 경우도 존재한다. (초록색테두리) 가로 길이가 n인 직사각형은 n-1길이의 직사각형갯수와 n-2길이의 직사각형 갯수를 합한 값이라는 결과 추론 가능. 피보나치 수열의 형태를 띄고 있으므로 dp 사용. #include #include #include using namespace std; lon..

baekjoon 2024. 2. 17. 00:24

경우의 수가 많다. dp문제로 보이므로 규칙을 찾을때까지 적어본다. 각 숫자를 1,2,3의 합으로 구하는 방법을 쭉 적어보다가 규칙을 발견할 수 있었다. 4부터 보게되면 네모를 친 1+1+1+1, 2+1+1, 1+2+1, 3+1은 4보다 1 작은 3의 네가지 경우의 수의 뒤에 1을 더한 형태 세모를 친 2+2, 1+1+2의 경우에는 4보다 2 작은 2의 2가지 경우의 수의 뒤에 2를 더한 형태 역삼각형의 경우는 4보다 3 작은 1의 1가지 경우의 수의 뒤에 3을 더한 형태다. dp[i]=dp[i-1]+dp[i-2]+dp[i-3] 피보나치수가 생각나는 형태의 점화식을 찾을 수 있었다. #include #include #include using namespace std; long long dp[12]; lo..

baekjoon 2024. 2. 16. 23:02

많은 케이스를 고려해보아야 할 dp 문제였다. ※시작점은 계단이 아니고 시작점에서 한칸 or 두칸 한번에 오를 수 있으므로 처음 닿는 칸이 두번째 칸일 수도 있다. 탑다운 풀이 #include #include #include using namespace std; int dp[302][3]; int arr[302]; int inputnum; int rec(int index, int num, int continually); int main() { cin >> inputnum; arr[0] = 0; for (int i = 1; i > arr[i]; } fill(&dp[0][0], &dp[300][2], -1); cout =3) return -2100000000; if (index == inputnum) ret..

baekjoon 2024. 2. 16. 22:07