본문 바로가기
반응형

알고리즘/BAEKJOON87

BOJ 14501, 15486 : 퇴사, 퇴사 2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/14501 www.acmicpc.net/problem/15486 퇴사 1의 경우는 완전 탐색으로 풀 수 있지만, 퇴사 2는 N이 매우 크므로, 다이나믹 프로그래밍, 메모이제이션(memoization)으로 풀어야 한다. DP[i] = i일 전까지의 최대 이익 이라고 정의를 하자. i일에 일을 수행하지 않으면, DP[i + 1] = DP[i]와 기존 memoization의 값 중 큰 값이 된다. i일에 일을 수행한다면, i일 전까지의 최대 이익인 DP[i]와 i일에 받을 보수 P[i]를 더한 값 vs 기존 memoization의 값 중 큰 값. 즉, DP[i + T[i]] = DP[i] + P[i] 와 DP[i + T[i]] 중 큰 값을 선.. 2021. 2. 15.
BOJ 10866 : 덱 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10866 참고 - BOJ 10866 : 덱 with Linked List 큐 + 스택 문제를 조합해서 풀면 해결할 수 있다. 큐에서 push할 때는 wp++, pop은 rp++이고, 스택에서 push할 때는 sp++, pop은 --sp였다. 즉, 배열의 앞에서 pop할 때는 rp++, 뒤에서 pop할 때는 --wp를 하면 된다. 마찬가지로, 앞에서 push할 때는 --rp, 뒤에서 push wp++ 이 된다. 덱의 경우, 앞에서도 push가 가능하므로 rp : read pointer의 의미가 맞지 않다. 따라서, 혼동되지 않도록 rp → front, wp → back 으로 수정하였다. 메모리를 넉넉하게 잡고 메모리의 가운데 부터 시작점.. 2021. 2. 8.
BOJ 10845, 18258 : 큐, 큐2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10845 www.acmicpc.net/problem/18258 큐, 큐2 문제는 같지만 명령의 수가 다르다. 큐는 N이 작아서 적당히 풀어도 통과할 수 있다. 큐2 기준으로 풀려면 모든 명령어를 O(1)이 되도록 풀어야 한다. 큐도 메모리만 넉넉하게 잡으면 스택처럼 배열로만 풀 수 있다. 스택과 다른 점은 pointer가 2개 필요하다. 큐에서 push할 때 write pointer를 증가시키고, pop할 때는 read pointer를 증가시키면 큐가 된다. 그리고 read와 write의 차이가 queue의 사이즈가 된다. 현재 queue의 뒤에 값을 저장해야 하므로 wp에 값을 저장하고 증가시킨다. queue[wp] = input, .. 2021. 2. 7.
BOJ 9012 : 괄호 알고리즘 문제 전체 링크 www.acmicpc.net/problem/9012 올바른 괄호인지 체크하는 문제이다. 실제로 작성하는 cpp 코드를 생각하면 쉽다. 코드를 작성할 때, 열린 괄호 '('를 썼다면 반드시 닫힌 괄호 ')'를 써야한다. 즉, 열린 괄호를 +1, 닫힌 괄호를 -1이라고 생각한다면 마지막에는 반드시 0이 되어야 한다. 열린 괄호 뒤에는 다시 열린 괄호 또는 닫힌 괄호가 와야한다. 그러므로, 괄호가 완전히 닫히기 전에 닫힌 괄호가 열린 괄호보다 많아서는 안된다. #include int main(void) { int T; scanf("%d", &T); for (int tc = 0; tc < T;tc++) { int i, flag, sp; char str[50 + 5]; flag = sp .. 2021. 2. 7.
BOJ 10773 : 제로 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10773 스택 기본 구현 문제 BOJ 10828과 같은 문제이다. BOJ 10828보다 쉬운 점은, push, pop만 구현하면 된다. 정수가 "0"일 경우 지울 수 있는 수를 보장하므로 pop할때 stack pointer를 검사할 필요가 없다. 마지막에 더하는 경우는 stack에 들어있는 모든 값을 더하면 되므로, 0 ~ sp 까지 for문을 돌면 된다. #include int K; int stack[100100]; int sp; int main() { int sum; scanf("%d", &K); for (int i = 0; i < K; i++) { int in; scanf("%d", &in); if (in) stack[sp++] .. 2021. 2. 6.
BOJ 10828 : 스택 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10828 스택 기본 구현 문제이다. push, pop, size, empty, top을 구현해야 한다. 명령의 수가 최대 10000이므로 10000보다 큰 배열을 잡고, index 하나만 추가하면 stack이 완성된다. 즉 push할 때는 index = stack pointer = sp를 증가 시키고, pop할 때는 sp를 감소시킨다. 배열에 값을 넣고, sp를 증가시키면 들어오는 순서대로 값을 저장할 수 있다. stack[sp] = input, sp++; → stack[sp++] = input; 값을 입력하고 sp를 증가시켰기 때문에 바로 이전 값은 sp - 1에 있다. output = stack[sp - 1], sp--; → out.. 2021. 2. 5.
반응형

티스토리툴바