본문 바로가기
반응형

덱7

BOJ 13545 : 수열과 쿼리 0 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/13545 참고 - BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 머지 소트 Merge Sort - BOJ 10866 : 덱 with Linked List - BOJ 13546 : 수열과 쿼리 4 수열과 쿼리 4에서 구해야하는 값은 아래와 같다. ● l r : max{|x - y| : l ≤ x, y ≤ r and Ax = Ay} 를 출력한다. 즉, 구간 [left, right]에서 같은 원소가 있는 경우 그 원소의 index의 차이가 가장 큰 값이다. 수열과 쿼리 0에서는 [left, right]에서 부분 수열 중 합이 0인 가장 긴 부분 수열의 길이를 구해야 한다. .. 2023. 2. 7.
BOJ 13546 : 수열과 쿼리 4 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/13546 참고 - BOJ 2042 : 구간 합 구하기 with 제곱근 분할법 (Sqrt Decomposition) - 머지 소트 Merge Sort - BOJ 13547 : 수열과 쿼리 5 - BOJ 10866 : 덱 with Linked List 수열과 쿼리 5에서 사용한 방법으로 문제를 푼다. 여기서는 주어진 구간 [left, right]에서 값이 같은 원소의 index의 차이를 구한다. 제곱근 분할법으로 원소의 길이 저장하기 [left, right]를 Mo's로 한 칸씩 움직이면서 각 원소마다 가장 긴 길이를 갱신하면 된다. 예를 들어 5번 원소가 7번 구간에 존재하고, 이 원소가 추가된다면, 5번 덱에 index .. 2023. 2. 7.
BOJ 10866 : 덱 with Linked List 알고리즘 문제 전체 링크 www.acmicpc.net/problem/10866 참고 - BOJ 10866 : 덱 - 메모리 풀 Memory Pool - 링크드 리스트 Linked List - 링크드 리스트 Linked List Tail ver - BOJ 13546 : 수열과 쿼리 4 배열로 구현했던 덱(deque)을 링크드 리스트를 이용해서 구현해보자. 구조체를 이용하여 DEQUE을 아래와 같이 정의한다. 값을 저장할 value와 앞과 뒤를 연결할 포인터를 선언한다. 그리고 최초로 사용할 deque와 front, back 포인터를 선언하고 메모리 풀을 적절히 잡는다. typedef struct st { int value; struct st* next; struct st* prev; }DEQUE; DEQU.. 2023. 2. 7.
BOJ 10866 : 덱 (deque) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/10866 vector로 동적 배열, 링크드 리스트를 이용할 수 있다. 그러나 vector는 끝에만 원소를 추가할 수 있으므로, 앞에도 원소를 추가해야할 경우에는 덱(deque)을 사용해보자. 스택(stack), 큐(queue)는 배열로 만드는 것이 쉽고 충분하지만, 덱(deque)의 경우는 pure하게 만들 때, 메모리 관리에 이슈가 있을 수 있다. deque에서 자주 사용하는 메서드는 아래와 같다. clear() deque를 초기화 한다. push_front() 앞에 원소를 넣는다. push_back() 뒤에 원소를 넣는다. vector와 동일하다. pop_front() 앞의 원소를 뺀다. pop_back() 뒤의 원소를 .. 2021. 6. 23.
BOJ 17837 : 새로운 게임 2 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17837 덱(deque)를 사용하여 풀이를 하지만, 실제 덱 사용법과는 다르게 풀어본다. (단순 배열이라고 생각하는 것이 좋다.) 나무 재테크와는 달리 덱의 앞 부분에 push/pop되는 경우가 없다. 현재 이동하는 말부터 모두 옮기고, 다음 칸에 넣을 때, 순서대로 넣거나, 반대로 넣는 차이만 있을 뿐, 다음 칸의 말의 앞부분에 넣지는 않는다. 따라서 초기의 front와 back을 0으로 초기화해도 된다. 구현 방법은 아래와 같다. 다음 칸이 WHITE 면, moveWhite를 한다. 다음 칸이 RED 면, moveRed를 한다. 다음 칸이 BLUE 면, 방향.. 2021. 3. 23.
BOJ 16235 : 나무 재테크 (삼성 SW TEST A형) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/16235 시뮬레이션 문제는 시키는대로 잘 구현하면 된다. 봄 : 나무의 나이만큼 양분 감소, 나무의 나이 1 증가, 어린 나무부터 양분 획득, 양분 부족시 사망. 여름 : 죽은 나무가 양분으로 나이 / 2 만큼 추가 가을 : 8방향 번식 나이 1의 나무가 생성 겨울 : 양분 추가 문제의 핵심은 나무가 중복될 수 있다는 것이다. 그리고 어린 나무부터 양분을 획득한다 조건에서 정렬이 필요할 것 같다. 무작정 구현했더니, time out이 나오게 되었다. /* time out */ void spring() { /* 나무를 나이 순으로 정렬 */ for (int r =.. 2021. 3. 4.
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.
반응형

티스토리툴바