본문 바로가기

CS/Algorithm

 (52)
패스트캠퍼스 챌린지 12일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 이진탐색 자료구조 케이스 어제 이진 탐색을 코드로 구현했을 때에는 문제가 없었지만 위와 같은 케이스에서는 문제가 발생했었다. 바로 삭제할 Node의 Child Node가 2개인 경우에서 삭제할 Node의, 바꿀 Node Child Node가 있을 경우였는데, 경우의 수를 잘 살펴보지 못하고 코드를 구현한 것이 문제였다. 당시에는 맞던 케이스라도 놓쳤던 부분이 있으면 오류가 발생할 수 있기 때문에 초기에 구조를 잘 설계하는 것도 중요하지만 만에 하나라는 심정으로 놓쳤던 부분은 없는지 복기하는 것도 중요하다. 코드를 구현하면서 아쉬웠던 것은 파이썬 언어에 대한 이해가 아직 부족하다는 것을 느꼈다...
패스트캠퍼스 챌린지 11일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 이진 탐색 트리 삭제 기능 구현 탐색 기능을 구현한 것에 이어 오늘은 삭제 기능을 구현해보았다. 먼저 강의를 들으면서 전반적인 흐름을 이해했다. 최대한 강의에 의존하지 않도록 노력하고 있는데 쉽지는 않았다. 코드를 먼저 구현해보았고 막히는 부분이 있을 때마다 고민한 이후에 영상을 참고해서 코드를 보완했다. 이진 탐색 트리에서 데이터를 삭제할 때 어떠한 유형으로 삭제되는지 알아보자. 첫 번째로 Leaf Node다. Leaf Node는 Child Node가 없는 Node로 부모 Node로 하여금 좌측 또는 우측 값을 None으로 설정, 해당 노드를 삭제시켜 깔끔하게 삭제시켜준다. 두 번째는 하나의..
패스트캠퍼스 챌린지 10일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 이진 탐색 트리의 탐색 기능 구현 지난번 이진 탐색과 연결 리스트의 기능을 구현하면서 이진 탐색의, O(log N)의 탐색 속도와 연결 리스트의, O(1)의 데이터 삽입 및 삭제의 장점을 결합시켰었다. 오늘은 실제 탐색 기능 구현을 위해 코드를 작성해보는 시간을 가졌다. 코드는 기존 클래스에서 메소드로 구현하였다. 해당 메소드를 보면 인자로부터 value 값을 전달받고 current node를 head로 초기화를 해준 뒤 while문을 통해 순회하면서 현재의 노드의 value 값이 있는지 확인한다. 만약 있다면 True를 반환해주고 없다면 False를 반환시켜준다. BST 객체를 생성 및 노드..
패스트캠퍼스 챌린지 9일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 이진 탐색 트리란? 이진 탐색 트리는 이진 탐색과 연결 리스트를 결합한 자료구조로 효율적으로 탐색 및 비교, 자료를 입력 및 삭제할 수 있다. 기존에 이진 탐색은 시간 복잡도가 O(log n)로 빠른 탐색 기능을 갖고 있지만 데이터 삽입 및 삭제가 불가능한 단점이 있었다. 반면에 연결 리스트의 경우 삽입 및 삭제가 O(1)이지만 탐색하는 시간 복잡도가 O(N)으로 효율이 떨어지는데 이러한 장, 단점을 보완하기 위해 이진 탐색과 연결 리스트를 결합시키게 된다. 특징으로는 각 노드의 자식이 2개 이하로 구성되어야하고 데이터의 값이 비교하는 노드보다 작을 경우 왼쪽 자식으로, 클 경우 오른쪽 자식으..
패스트캠퍼스 챌린지 8일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 트리 구조 트리는 자료구조이며 노드와 브런치를 이용해서 구성된다. 사이클(경로의 시작과 종료가 동일한 경우)을 이루지 않는 것이 특징이며 이진 트리 형태의 구조로 탐색 알고리즘 구현을 위해 많이 사용된다. 알아둘 용어 Node : 트리에서 데이터를 저장하는 기본 요소이다. 이때 데이터와 연결된 다른 노드에 대해 Branch 정보를 포함한다. Root Node : 트리의 최상단에 있는 노드이다. 만약 이진 탐색 트리를 적용한다면 주어진 값들을 크기의 순서대로 정렬했을 때 가장 중앙에 위치하는 값 즉, 중앙값으로 선정한다. Level : 최상위 노드를 Level 0으로 했을 때, 하위 Branch..
패스트캠퍼스 챌린지 7일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 해쉬 테이블 충돌 개선 방법 일반적으로는 해쉬 함수를 재정의하고 해쉬 테이블의 저장공간을 확대해서 충돌을 개선한다. 해쉬 함수와 키 생성 함수 기존에 구현했었던 파이썬의 hash() 함수는 실행할 때마다 값이 달라지기 때문에 통일성을 갖기가 어려웠다. 그래서 데이터에 유일한 값으로 변환시키기 위해서 해쉬 함수 중 유명한 함수인 SHA(Secure Hash Algotithm, 안전한 해시 알고리즘)를 사용했다. SHA는 어떠한 데이터라도 유일한 고정된 크기의 고정 값을 리턴해주기 때문에 해쉬 함수로써 유용하게 활용할 수 있다. 특히, 눈사태 효과로 입력 값의 아주 일부만 변경되어도 전혀 다른 결..
패스트캠퍼스 챌린지 6일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. Linear Probing 기법 오늘은 Linear Probing 기법에 대해서 학습 및 실습을 진행해보았다. 어제 구현했었던 해쉬 테이블 Chaining 기법(Open Hashing)인 테이블의 저장 공간 외의 공간을 활용하는 기법과 다르게 Linear Probing 기법은 Close Hashing 기법으로 테이블의 저장 공간을 활용해서 충돌 문제를 해결하는 기법이다. Linear Probing 기법은 충돌이 일어났을 때 hash address의 다음 address부터 나오는 빈 공간에 저장하는데 기존에 구현했었던 크기의 테이블 내에서만 한정적이기 때문에 공간을 잘 활용할 수 있다는 장점이 ..
패스트캠퍼스 챌린지 5일차 [강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다. 해쉬 테이블의 장점 1. 데이터 저장 및 읽기 속도가 빠르다 2. 해쉬는 키에 대한 데이터가 있는지 확인이 쉽다 단점 1. 일반적으로 저장공간이 많이 필요하다. 2. 여러 키에 해당하는 주소가 동일하면 충돌된다. 따라서 별도의 자료구조가 필요하다. 주요 용도 1. 검색이 많이 필요할 경우 2. 저장, 삭제, 읽기가 빈번할 경우 3. 캐쉬 구현시(중복 확인이 쉽다) 지난 번 실습에서는 내장함수 ord를 통해 문자의 유니코드 값을 불러와 키로 적용했는데, 이번에는 파이썬의 hash() 함수를 사용해서 특정 값을 불러왔다. 하지만 실행할 때마다, 값이 달라질 수 있기 때문에 보통은 사용되지 않는다고..

티스토리툴바