THIS IS ELLIE

오늘은 83번 문제를 풀어보겠습니다. EASY고 현재는 47.9%의 성공률을 보이네요. 오늘 주제는 Linked List입니다. 정렬된 링크드 리스트의 헤드가 주어지면, 중복되는 것들을 지워서 각 원소들이 한 번씩만 나타나게 해라. 주어진 예시들을 보겠습니다. 1번 예시를 보면, 1이 2번 나왔잖아요. 그래서 1노드 한 개를 지워줍니다. 지운 결과는 [1,2]이 됩니다. 2번 예시를 보면, 1이 2번 2가 1번, 3이 2번 나왔습니다. 그럼 1노드 1개 지워주고 3노드 1개 지워줘야겠죠. 지운 결과는 [1,2,3]이 됩니다. 문제에서 주어진 제약조건들을 살펴보면 노드의 수, node의 value값, 정렬 보장이 적혀있네요. 마지막 문장이 가장 눈에 띄네요. 일단 정렬이 보장되니까 이 문제는 쉽게 접근할 ..

오랜만에 알고리즘 포스팅을 해보려 합니다. 오늘은 Leetcode 94번 문제를 풀어볼 거예요. 제목은 Binary Tree Inorder Traversal이고 64.1%의 성공률을 가지고 중간 난이도입니다. 이진트리 중위 순회하는 문제입니다. 문제를 풀기 전에 이진 트리 순회 개념부터 살펴봅시다. 트리 순회는 트리 구조에서 각각의 노드를 정확히 한 번만 체계적인 방법으로 방문하는 과정을 말합니다. 연결 리스트와 1차원 배열과 같은 선형 자료 구조에서는 한 가지의 논리적인 순회 방법이 존재하지만, 트리 구조의 순회에는 많은 방법이 존재합니다. 전위 순회 (preorder) 1. 노드를 방문합니다. 2. 왼쪽 서브 트리를 전위 순회합니다. 3. 오른쪽 서브 트리를 전위 순회합니다. 전위 순회는 깊이 우선 ..

전화번호부에서 이름을 검색할 때 이진 탐색을 사용한다. 이전 프로젝트에서도 전화번호부에서 이름을 검색해야 했는데 배열의 처음부터 다 매칭 해보는 방법을 사용해 O(n)의 시간 복잡도를 가졌습니다. 그때 이진 탐색을 사용했더라면 O(logn)의 시간 복잡도를 가져 배열이 길수록 훨씬 더 효율적으로 검색할 수 있었겠죠. ㅠ_ㅠ 사실 이진 탐색 알고리즘이 무엇인지는 학교에서 배워서 대충은 알고 있었으나 실전에서 이렇게 사용되는지는 와 닿지 않았습니다. 그래서 이번 기회에 이진 탐색 알고리즘을 학습하고 정리하려 합니다. 먼저 이진 탐색 알고리즘의 조건은 데이터가 정렬되어 있어야 합니다. 스위프트로 작성한 코드를 봅시다. 중간 인덱스를 찾아서 중간 인덱스의 값이랑 비교를 합니다. 중간 인덱스 값과 내가 원하는 값..