Level 1. 가장 가까운 같은 글자 단순한 방법이라면 이중 for문을 돌면서 자신보다 앞에 있는 같은 글자를 찾을 수도 있지만 O(n²) 시간이 소요되며 비효율적이다. 차례대로 순회하면서 각 문자가 가장 마지막에 등장한 위치를 저장하고 확인할 수 있다면 O(n) 시간이 소요된다. map을 활용해 마지막 등장 위치를 저장하고 확인하여 해결했다. map에서 키의 존재 여부를 확인하기 위해 map.find()나 map.count()를 쓰는 경우도 있는데, map의 구현 스펙을 참고하면 키가 존재하지 않는 경우를 0이나 NULL로 확인하는 방법도 안전하다고 알려져 있다. #include #include #include using namespace std; vector solution(string s) { s..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 이진 검색 분할 정복 알고리즘의 하나이다. 시퀀스(정렬된 상태)에서 검색 범위를 2배씩 줄여나가며 검색한다. O(log n) 복잡도를 갖는다. 재귀를 이용하면 쉽게 구현할 수 있다. 이진 검색 과정 시작 F, 끝 L의 전체 시퀀스를 범위로 잡는다. 가운데 원소 M을 정한다. M이 찾는 원소이면 끝낸다. F와 L이 같은 경우 찾지 못 한 상태로 끝낸다. 찾는 원소가 M보다 작으면 끝 L을 M - 1로 설정하고, M보다 크면 시작 F를 M + 1로 설정한다. 2부터 다시 반복한다. 선형 검색과 이진 검색의 성능 비교 #include #include #include #include #include using namespace std; bool linea..

Level 1. 폰켓몬 정렬된 상태를 유지하지 않아도 되므로 set 대신 unordered_set을 사용했다. 중복 포켓몬을 제거한 후 최대 N/2마리의 포켓몬을 가져가면 된다. #include #include #include using namespace std; int solution(vector nums) { return min(unordered_set (nums.begin(), nums.end()).size(), nums.size() / 2); }

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 분할 정복 분할: 문제를 작은 부문제로 나눈다. 정복: 나눠진 각 부문제의 솔루션을 구한다. 결합: 각 부문제의 솔루션을 합쳐 전체 문제의 솔루션을 구한다. 일반적인 경우, 재귀를 사용하면 좀 더 쉽게 나타낼 수 있다. 분할 정복의 예시 이진 검색 병합 정렬 퀵 정렬 행렬 곱셈 ...

Level 1. 푸드 파이트 대회 쉬운 문제였다. #include #include using namespace std; string solution(vector food) { string answer = "0"; for (int i = food.size() - 1; 0 < i; --i) { string sub(food[i] / 2, '0' + i); answer = sub + answer + sub; } return answer; }

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 알고리즘 정해진 입력을 받아 변환하고 일련의 명령을 수행하여 결과를 출력하는 솔루션 효율적인 알고리즘 연산 횟수를 입력 크기 N에 대한 다항식으로 나타낼 수 있다면 효율적이다. 문제의 종류 Class P (Polynomial Time, 다항 시간): 복잡도를 다항식으로 나타낼 수 있는 문제 Class NP (Non-Deterministic Polynomial Time, 비결정적 다항 시간): 다항 시간 내에 해결할 수는 있지만 정해진 다항식이 존재하지 않는 문제 Class EXPTIME (Exponential Time, 지수 시간): 복잡도를 지수 함수 형태로 나타낼 수 있는 문제 Class PSPACE (Polynomial Space, 다항 공간..