반응형 알고리즘/[PRO] 삼성 SW 역량 테스트 B형45 함수의 매개변수와 배열의 register 속도 비교 삼성 B형 전체 링크 참고 - 변수 register 테스트 - B형에 필요한 최적화 코드 (1) (register 변수) - B형에 필요한 최적화 코드 (2) - 함수의 매개변수와 배열의 register 속도 비교 - 삼성 B형 디버깅 Tip - 비주얼 스튜디오 output.txt 설정하기 - 삼성 SW 역량 시험 환경에서의 인라인 함수 - Visual Studio LNK1168: 쓰기용으로 열 수 없습니다 해결방법 변수 외에도 함수의 매개변수나 배열에 register 키워드를 추가하면 속도 향상 효과를 볼 수 있다. 특히, 자주 사용하는 배열일수록 효과적이다. 매개변수 register 같은 동작을 하는 test1과 test2 함수가 있다. test2는 parameter에 register를 추가하였다. .. 2023. 8. 15. #define printf 재정의를 이용한 로그 출력 디버깅 팁 삼성 B형 전체 링크 삼성 C형 전체 링크 printf를 이용하여 로그를 출력해서 디버깅을 완료하였다고 하자. 이제 정답을 제출해야 되므로 printf를 모두 삭제하거나, 주석 처리해야 한다. 하지만 이 과정은 꽤 번거롭다. 지우는 것도 일이지만, 정답이 아닌 경우 지웠던 printf를 다시 복구하는데 시간이 꽤 많이 쓰인다. #define을 이용해서 printf를 재정의하면 이런 일을 간단히 해결할 수 있다. 아래 코드를 실행해보자. #include #define P printf int main() { P("hello!\n"); P(">> %s %d\n", "world", 100); return 0; } #define을 이용하여 printf를 P로 재정의했을 뿐이다. 그러니 원래 printf의 효과와 .. 2023. 7. 29. BOJ 10999 : 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) 알고리즘 문제 전체 링크 삼성 B형 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/10999 참고 - 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) BOJ 2042 - 구간 합 구하기와 비슷한 문제지만, 배열의 갱신이 연속된 특정 구간에 발생한다. 매 구간마다 하나씩 구간의 값을 바꾸면 느리기 때문에 알고리즘을 .. 2023. 1. 16. BOJ 2042 : 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) 알고리즘 문제 전체 링크 삼성 B형 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) 여러 배열이 있고 구간의 합이 쿼리로 주어지면 합을 구해서 답을 구하는 문제다. 바텀 업 세그먼트 트리를 이용하여 구간 합을 구해보자. 주어진 구간의 합을 구해야할 배.. 2023. 1. 15. BOJ 2042 : 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) 알고리즘 문제 전체 링크 삼성 B형 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) 여러 배열이 있고 구간의 합이 쿼리로 주어지면 합을 구해서 답을 구하는 문.. 2023. 1. 15. BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) 알고리즘 문제 전체 링크 삼성 B형 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - 구간 합 구하기 2 with 나중에 업데이트하기 (Top-Down Segment Tree with Lazy Propagation) 여러 배열이 있고 구간의 합이 쿼리로 주어지면 합을 구해서 답을 구하는 문제다. 아래와 같이 크기가 20인 배열이 있다고 가정하자. 문제에서는 배열이 1부터 시작하지만.. 2023. 1. 15. Indexed Priority Queue - 우선순위 큐의 임의 원소 갱신, 변경 (update) 삼성 B형 전체 링크 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 [수정] 항상감사합니다.님의 의견에 따라 방어코드가 필요한 것을 확인하였습니다. 제 코드는 update할 index = updatehn이 updatehn * 2 == hn(힙의 현재 크기)인 경우 문제가 발생합니다. PRO 시험에 제 코드를 사용하시는 분들은 아래 추가된 글 참고 부탁드립니다. Reference code ver Indexed Priority Queue, Heap - updat.. 2022. 1. 13. BOJ 14427 : 수열과 쿼리 15 (Reference) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 B형에서는 Reference로 우선순위 큐 code가 주어진다. 하지만 STL(priority_queue) 사용이 가능하더라도, 갱신이 가능한 우선순위 큐는 직접 만들어야 한다. 여기서는 Reference 우선순위 큐로 문제를 풀었다. (Indexed Priority Queue, Heap) 해설은 이전 글을 참고하자. #include int N, M; typedef struct st { int value; int id; }HEAP; HEAP heap[100100]; int heapIdx[100100]; int heapSize; int isMin(HEAP a, HEAP b) { if (a.value < b.value).. 2021. 7. 3. BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 참고 - BOJ 14427 : 수열과 쿼리 15 with 세그먼트 트리 우선순위 큐의 갱신을 이용하여 문제를 풀 수 있다. update를 위해 우선순위 큐를 최악의 값으로 초기화한다. for (int i = 0; i < 200100 /* heap size */; i++) heap[i].id = heap[i].value = 0x7fff0000; 처음의 값들은 순서대로 A1 ~ AN 이므로 heapIdx(id)를 각각 i = 1 ~ N으로 본다. for (int i = 1; i 1; i /= 2) { if (isMin(heap[i / 2], heap[i])) break; tmp = heap[i]; heap[i] = he.. 2021. 7. 3. 이전 1 2 3 4 5 다음 반응형
