본문 바로가기

C++

 (44)
[코딩인터뷰 완전정복] 1.9 문자열 회전 Q : 한단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring 이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을때 s1이 s2의 회전인지 판별하고자 한다. isSubstring을 1번만 호출해서 판별할 수 있는 코드를 작성하라. 회전 : abcde → cdeab s1을 문자열 xy로 나눴을때 yx는 s1의 회전이다. 단순하게 생각해보면 y가 s2의 처음에 나오는지 확인하고 그 뒤가 x와 일치하는지 확인하면 되지만 이 방법은 isSubstring을 1번만 호출하라는 지시에 맞지 않다. bool isRotate(string s1, string s2){ return isSubstring(s1+s1, s2); } 조금 더 생각을 해보자. s1 = xy , s2 = yx 라고 한다면..
[코딩인터뷰 완전정복] 1.8 O행렬 Q : M * N 행렬의 한 원소가 0일 경우, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라. #include int** OMatrix(int** input, int m, int n) { bool* horizen0; bool* vertical0; horizen0 = new bool[m]; vertical0 = new bool[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (input[i][j] == 0) { horizen0[i] = 1; vertical0[j] = 1; } } } for (int i = 0; i < m; i++) { if (horizen0[i] == 1) { for (int j = 0..
[코딩인터뷰 완전정복] 1.7 행렬 회전 Q : 이미지를 표현하는 N*N 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때, 이미지를 90도 회전시키는 메서드를 작성하라. 행렬을 추가로 사용하지 않고서도 할 수 있겠는가? #include int** RotateMatrix(int* matrix[], int n) { int temp; for (int i = 0; i
[코딩인터뷰 완전정복] 1.5 하나 빼기 Q : 문자열 두개가 주어졌을 때, 문자열을 같게 만들기 위한 편집횟수가 1회 이내인지 확인하는 함수를 작성하라. 가능한 편집 = 문자 삽입, 문자 삭제, 문자 교체 #include bool CheckChange(char str1[], char str2[], int len1, int len2) { if (len1 - len2 > 1 || len2 - len1 > 1) return false; int maxLength = len1 > len2 ? len1 : len2; int change = 0; int insert = 0; int remove = 0; if (len1 == len2) { for (int i = 0; i < maxLength; i++) { if (str1[i] == str2[i]) cont..
[코딩인터뷰 완전정복] 1.3 URLify Q : 문자열에 들어 있는 모든 공백을 '%20'으로 바꾸는 메서드를 작성하라. 인풋 문자열의 길이가 함께 주어진다. 공간복잡도는 고려하지 않는다. #include char* TransString(char input[], int length); int main() { char input[] = {'c','d',' ','a',' ','e','h','\0'}; printf("%s\n", TransString(input, 8)); } char* TransString(char input[], int length){ int transLength = 0; for (int i = 0; i < length; i++) { if (input[i] == ' ') transLength += 3; else transLength..
[C++ STL] Set, Multiset 1. Set - 저장 데이터의 값이 유일한 자료구조이다.(중복이 허용되지 않는다.) - 노드 기반 컨테이너이다. - 임의 접근이 불가능하다. - 균형 이진 트리로 구현되어있다. - 각 노드는 pair로 구성되었다. - multiset은 set에서 중복이 허용된다는 것 말고는 다른게 없기 때문에 함께 정리한다. 2. Include #include // multiset도 set에 포함되어있음 3. 생성자 std::set name; // 기본 오름차순(== set) std::set name(const key_compare& _Pred); // 정렬 방법을 _Pred로 설정한다. (== set) std::set name(const set& otherSet); std::set name(_Iter first, _I..
[C++ STL] Vector 1. Vector - 원소가 하나의 메모리 블록에 연속하게 저장된다. - 배열은 크기가 고정이고 vector는 크기가 동적으로 변한다. (개수를 미리 알 수 없다면 vector를 사용한다.) - 임의 접근이 가능하다. ( [], at() ) - ArrayList는 배열에 동적 메모리 증가 기능을 구현한 클래스, Vector는 ArrayList에 동기화가 보장되도록 최적화한 클래스이다. - Deque와 비교 Deque Vector 효율성 크기 변경 가능 O (여러 개의 메로리 블록을 하나의 블록처럼 사용 메모리 부족시 새로운 블록 추가 할당) O (할당된 메모리가 부족할 시 이전 메모리 블록 삭제후 새로운 메모리 블록을 재할당) Deque 앞에 삽입, 삭제 용이 O X Deque 뒤에 삽입, 삭제 용이 O..
[C++ STL] Deque 1. Deque - FIFO, LIFO가 모두 가능한 자료형이다. - 임의 접근이 가능하다. - Vector와 의 비교 Deque Vector 효율성 크기 변경 가능 O (여러 개의 메로리 블록을 하나의 블록처럼 사용 메모리 부족시 새로운 블록 추가 할당) O (할당된 메모리가 부족할 시 이전 메모리 블록 삭제후 새로운 메모리 블록을 재할당) Deque 앞에 삽입, 삭제 용이 O X Deque 뒤에 삽입, 삭제 용이 O O Deque 중간 삽입, 삭제 용이 X X Vector 순차 접근 가능 O O = 임의 접근 가능 O O Vector (거의 같음) 2. Include #include 3. 생성자 std::deque name; std::deque name(size_type size); std::dequ..

티스토리툴바