CS기초
-
[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) 자료구조는 컴퓨터에서 값을 담는 구조이다. 컴퓨터는 자료구조로 값 사이의 논리적 관계를 조직화한다. 예를 들어 값 사이의 계층을 만든다던가, 값의 순서를 인식한다던가 하는 것이다. 이런 논리적 관계의 인식 때문에 각 자료구조는 같은 값을 담아도 컴퓨터 내에서 사용하는 메모리의 용량과, 값을 삽입, 수정, 탐색, 삭제 시 소요하는 시간이 달라진다. 시간과 메모리는 프로그램의 가장 기본적인 비용이며, 이것이 개발자가 자료구조를 알아야하는 이유이자 알고리즘을 배울 때 자료구조가 항상 따라오는 이유이다. 컴퓨터의 기본 자료구조는 ..
-
컴퓨터에서의 뺄셈 구현 - 보수(complement)를 활용한 감산의 가산 처리CS기초/OS,HW 2023. 3. 29. 20:09
컴퓨터에서 곱셈은 덧셈, 뺄셈과 나눗셈은 보수의 덧셈을 활용하여 동작한다. 따라서 컴퓨터는 사칙연산 중 덧셈밖에 하지 못한다. 일단, 곱셈의 경우 덧셈으로 간단하게 구현이 가능한데, 해당 연산을 위한 회로를 따로 설계하는 것은 비효율적이기 때문이다. 나눗셈 역시 피제수(나누어지는 수)에서 제수(나누는 수)를 제수보다 적어질 때까지 계속 뺀 후 뺄셈의 횟수를 세면 되기 때문에 뺄셈을 구현하면 따로 회로를 설계할 필요가 없다. (예 - 7/2 → 2보다 작아질 때까지 7에서 2를 빼서 뺀 횟수를 구함 → 3, 나머지 1) 그렇다면 뺄셈은 왜 보수의 덧셈으로 구현할까? 뺄셈은 정확히 말하면 양수와 음수, 또는 음수끼리의 덧셈이다. 덧셈은 교환법칙이 성립하지만 뺄셈은 성립하지 않으므로, 앞 뒷 값의 절대값 크기..
-
[Leet Code] Two Pointers (투포인터): 19.Remove Nth Node From End of List - MediumCS기초/Coding Test 2023. 1. 5. 02:43
문제 / 코드 Description Remove the nth node from the end of the list and return its head. How to solve Since the given linked list can only be traversed from the first to the last node, we need to find a way to calculate where nth node from the end is from the start. However, the length of a linked list is not fixed, how can we find it? Let the length of the given linked list be l. Then the position..
-
[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..
-
[Leet Code] Two Pointers (투포인터): 189. Rotate Array - Medium (What "modify in-place" means on Leetcode?)CS기초/Coding Test 2022. 12. 20. 01:36
문제 / 코드 사실 이 문제도 미디움치고는 정말 빨리 풀었다. 나중에 나오는 링크드 리스트 미디움에 비하면 정말.. 이건 이지다. 릿코드에서 이 문제를 투포인터로 분류해놨는데 나는 왜 이 문제가 투 포인터인지 한참을 생각했다 (심지어 투 포인터로 푸는 방법이 따로 있는지 계속 생각함). 원리를 이해하니 두 점을 찍고 푼다는 점에서 투 포인터가 맞는데 기존의 투 포인터 푸는 방식과 다르다는 이유로 투 포인터라고 생각을 안했다니, 역시 고정관념에서 벗어나는 것이 참 힘들다. Leetcode said it's a Two pointers problem, I was confused how it can be done with two pointers with O(1) extra space (well, it wasn'..
-
[Leet Code] Two Pointers (투포인터): 167. Two Sum 2 - Input Array Is Sorted - MediumCS기초/Coding Test 2022. 12. 19. 21:37
* Two Pointers 알고리즘 설명 문제 / 코드 개인적으로 medium 중 제일 쉬웠던 문제. Two pointers에서 항상 중앙값을 가지고 풀던 것을 끝 값을 활용하는 것으로 아이디어만 바꾸면 수월하게 풀 수 있는 문제이다. Description Find two numbers such that they add up to a specific target number and return a list of those integers' index in the input array. Condition - The input array is 1-indexed - The array is already sorted in non-decreasing order - There is only one solution ..