본문 바로가기
반응형

linked list12

BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 삼성 C형 전체 링크 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5397 참고 - BAPC 2010 I번 문제 - BOJ 5397 : 키로거 (스택) - 링크드 리스트 Linked List - 링크드 리스트 삭제 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 - 세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제 - BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 위 문제를 스택을 이용한 방법 대신, 세그먼트 트리와 링크드 리스트로 풀어보자. 다만 이 방법으로는 이 문제의 tc를 시간 내에 통과할 수 없다. 키로거는 커서를 한 칸씩 이동.. 2023. 8. 25.
더블 링크드 리스트 구현 (Double Linked List Tail ver) 삼성 C형 전체 링크 참고 - 메모리 풀 Memory Pool - 메모리 풀 vs malloc 속도 비교 - 링크드 리스트 Linked List - 링크드 리스트 Linked List Tail ver - 더블 링크드 리스트 Double Linked List - 더블 링크드 리스트 Double Linked List Tail ver 더블 링크드 리스트에 TAIL이 추가되면 구현이 편하고 성능도 나아진다. HEAD의 next에 TAIL을 연결하고 TAIL의 prev에 HEAD를 연결하자. (초기화) HEAD.next = &TAIL; TAIL.prev = &HEAD; TAIL이 존재하기 때문에 curNode->next가 NULL이 되지 않는다. 따라서 if문이 삭제된다. nd->prev = curNode; nd.. 2023. 7. 30.
더블 링크드 리스트 구현 (Double Linked List) 삼성 C형 전체 링크 참고 - 메모리 풀 Memory Pool - 메모리 풀 vs malloc 속도 비교 - 링크드 리스트 Linked List - 링크드 리스트 Linked List Tail ver - 더블 링크드 리스트 Double Linked List - 더블 링크드 리스트 Double Linked List Tail ver 더블 링크드 리스트를 이용하여 도중에 삽입이 가능한 2차원 배열을 구현해보자. 편의상 index는 1부터 시작한다고 가정하자. 삽입 insert - index 1, hello insert - index 2, c++ insert - index 2, world! ㄴ 위 명령어를 실행하면 아래와 같이 저장된다. hello world! c++ 첫 번재에 hello를 추가하고 두 번째에 .. 2023. 7. 30.
BOJ 2042 : 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 메모리 풀 Memory Pool - 메모리 풀 vs malloc 속도 비교 - 링크드 리스트 Linked List 이전 글에서는 tree의 크기를 넉넉하게 잡았다. 구간의 길이가 100만이기 때문에 실제로는 2배 정도의 크기만 있으면 된다. 여기서는 필요한 만큼만 적절히 잡아서 다이나믹하게 트리를 만들어보자. 배열의 index를 이용하는 방법 원래 update 코드는 아래와 같다. void update(int left, int right, int node, int index, ll value) { if (inde.. 2023. 2. 8.
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 9612 : Maximum Word Frequency 삼성 B형 전체 링크 www.acmicpc.net/problem/9612 해시 테이블을 이용하여 가장 빈도수가 높은 단어와 개수를 세보자. 같은 수의 단어가 있는 경우 사전 순으로 뒤에 있는 단어를 출력한다. 구조체에는 단어의 수와 실제 단어, 그리고 링크드 리스트를 위한 struct pointer가 필요하다. 메모리 풀 방식으로 연결하기 위해 POOL 메모리와 pcnt를 선언한다. typedef unsigned long ul; #define MAX_TABLE (1007) #define MAX_WORD (20 + 5) int N; typedef struct st { int count; char word[MAX_WORD]; struct st *next; }HASHTABLE; HASHTABLE hashTab.. 2021. 5. 9.
최적화) 삼성 C형 샘플 문제 : 블록 부품 맞추기 삼성 B형 전체 링크 삼성 C형 전체 링크 블록 부품 맞추기 문제를 더 최적화 해보자. 아래의 makeBlock에서 코드를 하나씩 지워보며 시간을 재보면 sort에서 비용이 많이 드는 것을 알 수 있다. int makeBlock(int module[][4][4]) { register int i, sum; bcnt1 = bcnt2 = mcnt1 = mcnt2 = 0; for (i = 0; i < 30000; i++) check1[i] = check2[i] = 0; makeHash(module); sort(match1, 0, mcnt1 - 1, isMinForMatch); sort(block1, 0, bcnt1 - 1, isMinForBlock); sort(match2, 0, mcnt2 - 1, isMinF.. 2021. 4. 3.
반응형

티스토리툴바