CS기초/Algorithm, Data Structures
-
[Leet Code] 27.Remove Element - EasyCS기초/Algorithm, Data Structures 2023. 8. 3. 00:15
문제 Description Input: nums => list[int], val => int Remove all elements same with "val" in the given array "nums" and change the array to starts with the elements which are not same with "val". The array must be changed in place. Return the number of elements same with "val". The judge will test below two points: 1. The returned value is correct - name this value as "k" 2. Each element from 0 to..
-
[알고리즘] 정렬 알고리즘 : 합병정렬 (Merge sort)CS기초/Algorithm, Data Structures 2023. 6. 27. 08:19
정렬의 기초로 분할 정복 방법을 사용해 분할, 정복, 결합의 세 단계를 거친다. 분할: 배열을 동일한 크기의 두 개의 부분 배열로 분할한다. 입력 크기를 n이라고 한다면 분할된 부분배열의 크기는 n/2가 된다. 정복: 각각의 부분 배열에 대해 합병 정렬을 순환적으로 적용한다. 결합: 정렬된 두 부분 배열을 합쳐서 하나의 정렬된 배열을 만든다. 간단하게 설명하면 합병정렬은 배열을 쪼개서 각각 정렬한 후 합치는 알고리즘이다. def merge_sort(num): l = len(num) if l > 1: mid = round(l/2+0.1) left = merge_sort(num[:mid]) right = merge_sort(num[mid:]) num = merge(left, right, mid, l-mid)..
-
[자료구조] 자료구조를 알아야하는 이유와 배열(list), 연결리스트(linked list)CS기초/Algorithm, Data Structures 2023. 4. 1. 00:56
배열 포스팅을 쓰면서 참조, mutable, id까지 쓰려다가 평생 포스팅 못 할 것 같아 일단 간단하게 자료구조에 대한 글 먼저 쓰려고 한다. 자료구조 (Data Structure) 자료구조는 컴퓨터에서 값을 담는 구조이다. 컴퓨터는 자료구조로 값 사이의 논리적 관계를 조직화한다. 예를 들어 값 사이의 계층을 만든다던가, 값의 순서를 인식한다던가 하는 것이다. 이런 논리적 관계의 인식 때문에 각 자료구조는 같은 값을 담아도 컴퓨터 내에서 사용하는 메모리의 용량과, 값을 삽입, 수정, 탐색, 삭제 시 소요하는 시간이 달라진다. 시간과 메모리는 프로그램의 가장 기본적인 비용이며, 이것이 개발자가 자료구조를 알아야하는 이유이자 알고리즘을 배울 때 자료구조가 항상 따라오는 이유이다. 컴퓨터의 기본 자료구조는 ..
-
[Leet Code] Two Pointers (투포인터): 876.Middle of the Linked List - EasyCS기초/Algorithm, Data Structures 2023. 1. 2. 02:04
문제 / 코드 드디어 linked list가 나왔다. 링크드리스트 자료구조 포스팅이랑 같이 올리려고 했는데 시간이 너무 늦어 다음 코드리뷰 포스팅이랑 같이 올려야겠다 (어차피 앞으로 링크드리스트 주구장창 나올 예정이기 때문에..) Description Return middle node of the linked list. If there are two middle nodes, return the second middle node. How to solve Simple way Iterate the linked list from the first node to get the full length. Iterate the linked list from the first node again, change the cu..
-
[알고리즘] 투포인터(Two pointers)와 슬라이딩 윈도우(Sliding window)CS기초/Algorithm, Data Structures 2022. 11. 13. 17:51
예제문제는 leetcode로 리뷰할 거기도 하고, 이미 다른데서 포스팅을 많이 해 둬서 특정 문제가 아닌 기본 개념에 집중해서 포스팅을 하려고한다. 투 포인터와 슬라이딩 윈도우의 기본 concept은 다음과 같다. 1. 배열의 특정 두 부분에 포인트를 설정한다. 해당 두 포인터의 사이는 "타겟이 있을 법한 범위"이다. 2. 조건에 따라 해당 포인트를 옮겨가며 타겟을 찾는다. 두 알고리즘의 원리는 같지만 투 포인터의 경우 포인터가 가리키는 값 두 개 자체에만 집중하기 때문에 반복문 loop마다 조건에 따라 포인트 사이의 거리가 달라질 수있지만 슬라이딩 윈도우의 경우 반복문 loop간 window사이의 교집합이 알고리즘의 핵심이기 때문에 두 점사이의 거리가 일정(/고정) 되어있다는 점이 특징이다. 시간 복잡..
-
[알고리즘] 선형 검색과 이진 검색CS기초/Algorithm, Data Structures 2022. 11. 13. 13:37
검색의 종류 - 배열 검색 - 연결 리스트 검색 - 트리 검색 1. 선형 검색 (linear search/ sequential search) 특징: 무작위로 늘어놓은 데이터 집합에서 검색 쉽게 말해 배열의 전체 요소를 모두 탐색하는 것을 뜻한다. - 보초법: 선형검색의 비용을 줄이는 방법. 반복을 종료하는 판단 횟수를 줄이는 역할을 하는 것이 보초. 시간 복잡도: O(n) 2. 이진 검색(binary search) (분할정복법(divde and conquer 중 하나) 특징: 일정한 규칙으로 늘어놓은 데이터 집합에서 검색, 즉 시퀀스가 정렬(sort)되어있어야함. 중간 값과 찾으려는 값의 대소비교를 통해 범위를 절반씩 줄여 나감. 시간복잡도: O(logn) 길이가 n인 배열을 이진 탐색하면 n, n/2,..