Level 0. 유한소수 판별하기 유한 소수인 분수는 다음을 만족한다. 최소공배수를 구하여 약분하기보다는 이 풀이가 좀 더 간단하고 효율적이라고 생각한다. 분모를 먼저 2와 5로 나누어 떨어지지 않을 때까지 나눈다. 이때 분자가 분모로 나누어 떨어지면 유한 소수로 나타낼 수 있는 분수이다. #include using namespace std; int solution(int a, int b) { while ((b & 1) == 0) b >>= 1; while (b % 5 == 0) b /= 5; return (a % b) ? 2 : 1; }

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 빠른 검색의 필요성 선형 검색은 O(n) 복잡도를 갖는다. 균형 트리에서의 검색은 O(log n) 복잡도를 갖는다. 유전자 데이터처럼 수백 수천만의 데이터가 저장된 경우에는 훨씬 효과적인 검색 방법이 필요하다. 해시 함수 주어진 입력을 고정 길이의 고유한 값으로 변환하는 단방향 함수이다. 그러므로 해시 값을 통해 원본 문자열을 복원하는 역함수는 존재하지 않는다. 좋은 해시 함수는 중복 확률이 낮은 함수이다. 해싱 해시 함수로 계산한 값을 통해 자료 저장 주소를 찾아내는 탐색 방법이다. 해시 테이블 해시 함수로 계산한 값을 인덱스로 하여 키(해시)와 값을 저장하는 자료구조이다. 키 값만 가지고는 테이블에 원소가 존재하는지 알 수 없고 값도 함께 확인..

insert() 함수로 값을 추가할 때 vector와 set의 인자가 다른 것을 발견했다. vector는 반복자를 첫 번째 인자로 받는 반면 set은 값만을 받는다. #include #include #include using namespace std; void main() { vector v1 = {1, 2}; vector v2 = {3, 4}; v1.insert(v1.end(), v2.begin(), v2.end()); set st = {1, 2}; st.insert(v2.begin(), v2.end()); } 생각해보니 이유는 간단했다. vector는 임의 위치에 원소를 추가할 수 있기 때문에 가능하지만 set은 정렬된 상태를 유지하기 때문에 원하는 위치에 원소를 추가할 수 없기 때문이다.

vector에서 중복 원소를 제거하는 방법이다. unique가 실행될 때 각 원소는 자신의 양 옆 원소와 비교하여 중복을 제거한다. 그러므로 O(n)에 수행되지만 정렬된 상태에서만 정상 작동한다. 버블 정렬과 비슷한 방식이며 뒤로 몰아 놓은 중복 원소들의 시작 지점 반복자를 반환한다. #include #include #include using namespace std; template ostream& operator

Level 0. 소인수분해 소인수분해는 다음과 같은 과정을 통해 수행할 수 있다. n = 120을 예로 들 때 i는 2부터 시작한다. n이 1이 아닌 동안 반복한다. 1씩 증가시키며 나누어 떨어지는 수 i를 찾는다. i를 소인수 리스트에 추가한다. n이 더 이상 나누어 떨어지지 않을 때까지 i로 나눈다. 2로 돌아가 과정을 반복한다. 아래는 재귀를 이용하여 부문제로 나누어 해결한 풀이이다. 예들 들면 solution(120)은 2와 solution(60)의 결과를 합친 것이다. solution(60)은 2와 solution(30)의 결과를 합친 것이다. solution(30)은 2와 solution(15)의 결과를 합친 것이다. solution(15)는 3과 solution(5)의 결과를 합친 것이다. ..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 트리의 단점 계층적 구조를 표현할 수 있는 반면 순환적인 종속성을 표현할 수 없다. 그래프 순환 구조를 표현할 수 있다. 도시의 도로망, 항공 네트워크 등 정점(Vertex)과 정점 사이를 연결하는 간선(Edge)으로 구성된다. 각 정점은 연결된 다른 정점들의 정보를 유지해야 한다. 인접 행렬(Adjacency Matrix) 혹은 인접 리스트(Adjacency list)로 관리한다. 인접 행렬과 인접 리스트 인접 행렬은 삽입/삭제 시 O(1) 시간 복잡도를 갖으나 O(n²) 공간 복잡도를 갖는다. 인접 리스트는 삽입 시 O(1), 삭제 시 O(n) 시간 복잡도를 갖으나 간선의 개수만큼의 공간만 필요로 한다. 그래프의 구분 순환 그래프(Cyclic ..