본문 바로가기
반응형

알고리즘/BAEKJOON88

BOJ 2751 : 수 정렬하기 2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2751 참고 - 머지 소트 Merge Sort 여러 정렬 방법이 있겠지만, 여기에서는 merge sort로 풀어보자. #include int N; int a[1000000 + 50000]; int b[1000000 + 50000]; void merge(int start, int end) { int mid, i, j, k; mid = (start + end) >> 1; i = start; j = mid + 1; k = 0; while (i 2021. 2. 16.
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 : 덱 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 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 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10845www.acmicpc.net/problem/18258 큐, 큐2 문제는 같지만 명령의 수가 다르다.큐는 N이 작아서 적당히 풀어도 통과할 수 있다.큐2 기준으로 풀려면 모든 명령어를 O(1)이 되도록 풀어야 한다. 큐도 메모리만 넉넉하게 잡으면 스택처럼 배열로만 풀 수 있다.스택과 다른 점은 pointer가 2개 필요하다. 큐에서 push할 때 write pointer를 증가시키고, pop할 때는 read pointer를 증가시키면 큐가 된다.그리고 read와 write의 차이가 queue의 사이즈가 된다. 현재 queue의 뒤에 값을 저장해야 하므로 wp에 값.. 2021. 2. 7.
BOJ 9012 : 괄호 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/9012 올바른 괄호인지 체크하는 문제이다.실제로 작성하는 cpp 코드를 생각하면 쉽다.코드를 작성할 때, 열린 괄호 '('를 썼다면 반드시 닫힌 괄호 ')'를 써야한다.즉, 열린 괄호를 +1, 닫힌 괄호를 -1이라고 생각한다면 마지막에는 반드시 0이 되어야 한다. 열린 괄호 뒤에는 다시 열린 괄호 또는 닫힌 괄호가 와야한다.그러므로, 괄호가 완전히 닫히기 전에 닫힌 괄호가 열린 괄호보다 많아서는 안된다. #include int main(void){ int T; scanf("%d", &T); for (int tc = 0; tc 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 : 스택 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 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에 있다... 2021. 2. 5.
반응형

티스토리툴바