본문 바로가기
반응형

삼성 SW 역량174

BOJ 2338 : 긴자리 계산 with 10^N진법 알고리즘 문제 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/2338 참고 - BOJ 10757 : 큰 수 A+B - BOJ 10757 : 큰 수 A+B with 10^N진법 - BOJ 2338 : 긴자리 계산 - BOJ 2338 : 긴자리 계산 with 10^N진법 - 36진법 긴자리 두 수의 곱셈 - 36진법 긴자리 두 수의 곱셈 with 36^5진법 - 36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input 큰 수 A+B with N진법을 참고하여 뺄셈과 곱셈도 마찬가지로 N진법을 적용해보자. 덧셈의 경우 100000000000000000진법까지 가능했지만, 곱셈은 자릿수가 2배로 오르기 때문에 100000000진법(0이 8개)까지만 가.. 2023. 8. 26.
긴자리 후위 표기법 구현하기 삼성 C형 전체 링크 참고 - 후위 표기식 - 중위 표기식 BOJ 1918 : 후위 표기식을 참고하면, 아래의 규칙대로 중위 표기식을 후위 표기식으로 바꿀 수 있다. 1. stack이 비어있거나 열린 괄호 "(" 는 stack에 넣는다. 2. 열린 괄호 "(" 다음의 연산자는 stack에 넣는다. 3. 현재 stack의 가장 위에 있는 연산자보다 우선순위가 큰 연산자는 넣는다. ( * = / > + = - ) 4. 현재 stack의 가장 위에 있는 연산자보다 우선순위가 낮은 연산자가 들어오려고 한다면, 스택이 비거나, 열린 괄호 "(" 가 나오거나 해당 우선순위가 더 커질 때까지 스택을 비우고, 연산자를 넣는다. 5. 닫힌 괄호 ")" 가 나오면 열린 괄호 "(" 가 나올 때까지 스택을 비운다. 이때, .. 2023. 8. 25.
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.
함수의 매개변수와 배열의 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.
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.
반응형

티스토리툴바