본문 바로가기
반응형

삼성 EXPERT60

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.
세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제 삼성 B형 전체 링크 삼성 C형 전체 링크 참고 - 링크드 리스트 Linked List - 링크드 리스트 삭제 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 - BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 (구현) append, insert, erase 구현 세그먼트 트리를 이용해 링크드 리스트를 더 빠르게 insert, erase 할 수 있다. append는 세그먼트 트리에서 node를 순서대로 추가한다. 그리고 insert, erase는 해당 node를 각각 링크드 리스트로 구현하여 해결할 수 있다. 세그먼트 트리의 index를 잘 관리한다면 O(logN) 연산으로 a.. 2023. 8. 25.
2차원 배열 탐색과 캐시 미스 (Cache Misses in 2D Arrays) 삼성 C형 전체 링크 참고 - Visual Studio 실행 시간 확인 방법 1차원 배열은 연속된 메모리의 집합이다. 2차원 배열은 [row][col]로 접근하지만, 1차원 배열과 마찬가지로 연속된 메모리의 집합이다. Cache Friendly Code - 특정 데이터를 참조할 때, 그 데이터 주위의 데이터도 함께 캐시에 로드되는 특성. (Locality) - 연속적인 메모리 주소에 있는 데이터는 캐시에 함께 로드될 가능성이 높음. 즉, 2차원 배열(arr[r][c])을 접근할 때, r이 증가하는 방향보다, c가 증가하는 방향으로 먼저 탐색하는 것이 더 빠르다. 임의의 2차원 배열을 만들어서 주소를 출력해보자. #include int main() { char arr[5][5]; for (int r = 0.. 2023. 8. 15.
타입 캐스팅으로 한 번에 메모리 쓰기, 읽기 (Memory Write and Read with Type Casting) 삼성 C형 전체 링크 참고 - 타입 캐스팅으로 deep copy, memcpy 구현하기 타입 캐스팅을 이용하면 char 배열 8칸을 한꺼번에 입력할 수 있다. 즉, 크기가 작은 타입의 배열을 long type으로 한 번에 읽거나 쓸 수 있다. 이 방법은 메모리를 통째로 복사하는 방법과 원리가 같다. Write char a[8]; 배열에 1, 2, 3, 4, 5, 6, 7, 8을 입력해야 한다고 하자. 그러면 for문을 8번 순회해서 i 번째 배열에 i + 1을 입력하는 코드를 만들 수 있다. char a[8] = { 0 }; for (int i = 0; i < 8; i++) a[i] = i + 1; 하지만 type casting으로 a[0]번째 주소 (&a[0])을 long type으로 캐스팅하면, 한 .. 2023. 8. 15.
타입 캐스팅으로 deep copy, memcpy 구현하기 (Memory Copy with Type Casting) 삼성 C형 전체 링크 참고 - 타입 캐스팅으로 한 번에 메모리 쓰기, 읽기 삼성 C형에서는 string.h 라이브러리를 사용할 수 없기 때문에 memcpy를 사용할 수 없다. 그래서 배열을 복사할 때, for문을 이용해 직접 복사한다. 그런데 임시 변수 없이 변수 바꾸기에서 long 타입을 캐스팅하여 배열을 한꺼번에 교체하였다. 이 방법을 더 확장하여 더 빠른 copy를 메모리 casting으로 구현할 수 있다. 1차원 배열 복사 - 배열 복사 먼저 단순 복사 코드를 보고 실행 시간을 확인해 보자. (SW Expert Academy 문제에서 비교) char 1000개의 배열 a를 for를 이용해 b에 복사한다. #include #include /* memcpy test */ #define MAX (100.. 2023. 8. 15.
C, C++ - 비트 교환 (Change Some Bits) C, C++ 전체 링크 삼성 C형 전체 링크 참고 - 비트 연산 기본 매크로 함수 - 비트 단위로 출력하기 1. char 타입 4bit 교환 2. 4bit 단위로 교환 3. 1bit 교환 char 타입 4bit 교환 char는 1byte = 8bit이므로 아래와 같이 4bit씩 양 옆으로 옮겨주면 비트가 교환된다. 예를 들어 char a = 0xA9라면 0x9A가 된다. typedef unsigned char uc; uc change4Bit(unsigned char value) { return (value > 4); } 전체 코드는 다음과 같다. #include typedef unsigned char uc; uc change4Bit(unsigned char value) { return (value > 4.. 2023. 8. 15.
간단한 윤곽선 검출로 정사각형 찾기 (Find Squares with Simple Edge Detection) 삼성 C형 전체 링크 에지 디텍션은 영상의 밝기의 변화를 검출하여 윤곽선을 찾는 방법이다. 여기서는 간단히 2차원 배열에 겹쳐져 있는 정사각형을 검출해보자. makeRectangle 함수는 좌표 (sr, sc) ~ (er, ec)의 사각형을 모두 1로 증가시키는 함수다. #define MAX (20) int originalMap[MAX][MAX]; void makeRectangle(int sr, int sc, int er, int ec) { for (int r = sr; r < er; r++) for (int c = sc; c < ec; c++) originalMap[r][c]++; } 여기서 만들 정사각형의 최소 사이즈는 4라고 가정한다. makeRectangle(5, 5, 10, 10); // 길이가.. 2023. 8. 14.
메모리 주소를 기록하여 배열에 접근하기 삼성 C형 전체 링크 참고 - 포인터의 크기 (Size of Pointer) - 삼성 SW 역량 시험 환경 memoryTest에서 memory[] 없이 memory 배열에 0 ~ 9를 할당해보자. #include void memoryAllocation(char address[], char memory[]) { } void memoryTest(char address[]) { } int main() { char address[10] = { 0 }; char memory[100] = { 0 }; for (int i = 0; i < 10; i++) printf("%d ", memory[i]); putchar('\n'); memoryAllocation(address, memory); memoryTest(addre.. 2023. 7. 30.
C, C++ - 비트 뒤집기 (Reverse Bits) C, C++ 전체 링크 삼성 C형 전체 링크 참고 - 비트 단위로 출력하기 - 1 비트 개수 세기 1 비트 개수를 세는 방법을 응용하면 비트를 뒤집는 것도 가능하다. long, int, short, char ver 구현을 참고하자. #include typedef unsigned long long int ll; template void printBitNumber(T number) { unsigned int bitSize = sizeof(number) * 8; T mask = (1ull) = 1; if (i % 8 == 7) printf(" "); } putchar('\n'); } ll getBitConvertLong(ll number) { ll convert = number; convert = (conve.. 2023. 7. 30.
반응형