반응형 삼성 B형70 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. Visual Studio LNK1168: 쓰기용으로 열 수 없습니다 해결방법 (실행 파일 이름 변경하기) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 참고- 삼성 A형 전체 링크- 삼성 B형 전체 링크- 삼성 C형 전체 링크- 알고리즘 테스트 용 Visual Studio Setting - Input- 알고리즘 테스트 용 Visual Studio Setting - Output 알고리즘 문제를 풀다 보면 메모리를 잘못 접근하거나 무한루프에 빠지는 경우, : 오류 LNK1168 C:\Users\source\repos\Project3\Debug\Solution.exe을(를) 쓰기용으로 열 수 없습니다. 와 같은 에러가 발생할 수 있다. 대부분 exe를 종료하면 해결되지만, 가끔 백그라운드로 남아서 다시 실행되지 않을 때가 있다.심한 경우는 비주얼 스튜디오를 끄고 켜더라도 동작하지 않아 컴퓨터.. 2022. 12. 16. Indexed Priority Queue - 우선순위 큐의 임의 원소 갱신, 변경 (update) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 [수정] 항상감사합니다.님의 의견에 따라 방어코드가 필요한 것을 확인하였습니다.제 코드는 update할 index = updatehn이 updatehn * 2 == hn(힙의 현재 크기)인 경우 문제가 발생합니다. PRO 시험에 제 코드를 사용하시는 분들은 아래 추가된 글 참고 부탁드립니다. Reference code ver Inde.. 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. 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 7785 : 회사에 있는 사람 (map) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/7785 Hash Table / vector를 이용할 필요없이 이름을 key, 회사에 들어있는 상태를 value로 보는 map으로 문제를 풀 수 있다. map enterMap; 하지만 map을 iterator를 이용하여 출력하면, 오름차순 정렬(사전순 정렬)이 된다. 따라서 map의 key가 정렬되는 기준을 변경해줘야 한다. algorithm의 sort에서 정렬 기준을 변경한 것처럼 map도 compare를 만들고 넘겨주면 된다. struct compare { bool operator()(const string& a, const string& b) const { return a > b; } }; map enterMap; 이제 .. 2021. 6. 22. BOJ 7785 : 회사에 있는 사람 (vector, erase) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/7785 vector를 이용한 방법에서 erase도 사용해보자. vector.erase(pointer)를 이용하면 해당 원소를 삭제할 수 있다. leave 구현 부분을 아래의 코드로 바꾸면 된다. else /* leave 입력 */ { ull h = getHash(name.c_str()); int size = Hash[h].size(); for (int i = 0; i name == name) { Hash[h][i]->in = 0; /* in = 0 으로 변경 */ Hash[h].erase(Hash[h].begin() + i); break; /* 동명이인이 없으므로 종료 .. 2021. 6. 22. BOJ 7785 : 회사에 있는 사람 (vector) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/7785 Hash Table + Merge Sort로 풀었던 회사에 있는 사람을 vector, string을 이용해서 풀어보자. 아래의 코드는 vector로 대체 가능하다. /* before */ typedef struct st { char name[6]; int in; }DB; DB dbList[1001000]; /* 전체 사람을 관리하는 list */ DB enterList[1001000]; /* 회사에 남은 사람을 저장할 list */ typedef struct st2 { DB *db; struct st2 *next; }HASH; HASH Hash[MAX_TABLE]; HASH POOL[MAX_TABLE]; int pcn.. 2021. 6. 22. 이전 1 2 3 4 5 6 ··· 8 다음 반응형
