All Good

Computer Science66

🔸Coordinate Compression🔸 intro / implementation 🔸 넓게 퍼져 있는 값들을 문제 해결을 위해 좌표 압축. (위 그림의 경우 -6~5까지의 퍼져 있는 수들을 차례대로 0 - 1 - 2 - 3 - 4로 나열 가능) 🔸 주의점: 주어진 수들의 크기가 중요치 않고, 크기 순서만이 문제 해결에 필요할 때 좌표 압축 진행 🔸 구현 ex) 랜덤 크기 순으로 나열된 A[1], A[2], A[3], .... A[n]을 좌표 압축 ① A[1], A[2], ... , A[n]를 정렬한 새로운 배열 B[] 생성 ② 필요 시 중복된 원소들을 제거(중복 카운트 중요치 않을 경우만) ③ 각 A[i]를 B[]에서 이분탐색하여 B[]에서의 A[i] index를 계산 🔸 쉽게 말하자면, 랜덤하게 배치된 다양한 크기의 숫자들을 index의 크기.. Computer Science/Algorithms 2023. 1. 24.
🎼 Regular Expression 💚 정규 표현식은 '패턴 매칭 기반으로 특정한 규칙을 가지는 문자열을 검색&분리하고 교체하는 강력한 기능을 제공하는 형식 언어' 💚 python에서는 re library를 importimport re1. re.search() & re.match() & re.fullmatch() & re.sub()💚 re.match() checks for a match ONLY at the beginning of the string, whereas re.search() checks for a match anywhere in the string ※ re.match는 문자열 처음부터 매칭 / re.search는 문자열 일부분 매칭 ※ 💚 re.fullmatch() checks for entire string to be.. Computer Science/Algorithms 2023. 1. 11.
Types of Binary Tree🌲 🌲priority queue 자료구조 포스팅에서 heap은 일종의 CBT(Complete Binary Tree) 형태로 구현된다고 언급한 적이 있다. priority queue - heap 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가 sh-avid-learner.tistory.com 🌲 여기서 다양한 종류의 Binary Tree에 대해 간단하게 알아보자. 🌲 Binary Tree란 tree 자료구조의 일종으로, 각 node의 자식 node는 최대 2개 존재하며, 이를 left & right child라고 부른다. ① representation) .. Computer Science/Data Structures 2023. 1. 10.
👯Priority Queue(feat. Binary Heap) intro👯 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' 👯 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 예를 들어 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우, 즉 가치라는 우선순위에 따라 처리할 때 우선순위 큐라는 자료구조 사용. 앞서 배운 스택의 경우 가장 나중에 삽입된 데이터가 먼저 추출되고, 큐의 경우 가장 먼저 삽입된 데이터가 먼저 추출된다. 하지만 우선순위 큐는 직접 정한 우선순위에 따라 추출되는, 즉, 큐라는 자료구조에서 우선순위라는 어떤 기준을 정해 이에 의해 데이터를 추출하는 방식이라 생각하면 된다.   👯 우선순위 큐는 크게 두 가지 방법으로 구현 가능하다. ① 단순히 list로 구현하는 방법과 ② .. Computer Science/Data Structures 2023. 1. 9.
🛝Dynamic Programming🛝 intro🐥 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함. 따라서 완전탐색의 비효율적인 시간 복잡도 성능 한계점을 해결해준다. 또한 '다이나믹 프로그래밍 = 동적계획법'이라고도 부른다. (동적(dynamic) 할당(allocation) - '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'). DP 알고리즘을 활용한다면 여러 sub-problem 포함 모든 문제의 정답이 들어가는 메모리 미리 배치(이 때 여러 문제들의 결과를 저장하는 저장용 list는 dp-table). DP 알고리즘을 활용하기 위해서는 아래 두가지 조건을 만족해야 한다. ① 최적 부분 구조(Optimal Subst.. Computer Science/Algorithms 2023. 1. 3.
bitmasking * intro> 💧 bitmask = '컴퓨터는 내부적으로 모든 자료를 이진수로 표현. 이 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법' (엄밀하게 자료구조는 아님) 💧 2진수 관련 bit 연산을 진행하면 웬만한 모든 연산의 time complexity가 $O(1)$로 표현되므로 매우 매우 유용하고 편리함! 💧 2진수와 10진수 간의 변환방법 (python) ① 10진수 → 2진수: bin() 함수 사용 (반환 결과 string) print(bin(100)) #0b1100100 #type 'str' ② 2진수 → 10진수 (1) 2진수가 0과 1로 구성된 숫자라면 앞에 0b를 붙이고 출력 (2) 2진수가 문자열 형태라면 int()에 문자열과 2를 지정해 변환 ※ bin의 결과가 문자열로 반환.. Computer Science/Algorithms 2022. 12. 20.
👀 Binary Search 👀 intro 🐧 순차 탐색 - 선형 탐색) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 (가장 기본적인 형태 - 한 개씩 확인) 🐧 이진 탐색) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색(시작점, 끝점, 중간점을 이용하여 탐색 범위 설정) ※ 이진 탐색은 순차 탐색에 비해 탐색 범위가 훨씬 줄어들기 때문에 시간 복잡도는 log시간을 보인다. Q. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기 0 - 2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 ① 시작점) index 0, 중간점) index 4, 끝점) index 9 → 중간점이 2개 존재한다면, 소수점은 제외한 앞부분을 설정한다 → 4가 중간점 기준 왼쪽에 존재.. Computer Science/Algorithms 2022. 12. 6.
understanding pesudo-code of QuickSort 🦢 백준 퀵 정렬 대표 문제 모음) 추후 🦢 퀵 정렬 concepts 포스팅) 추후 🦢 QuickSort pseudo-code quick_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q Computer Science/Algorithms 2022. 12. 5.
hash table / hashing * hash table 🤗 반드시 알아야 할 자료구조 - 해시(Hash)에 대해서 알아보자! 🤗 파이썬에서 해시 테이블은 dictionary라는 자료구조를 통해 구현할 수 있다. dict() 클래스에 구현되어 있음. ① list의 경우 숫자로만 indexing - 즉 자료 접근이 가능하지만, dictionary의 경우 key라는 특수한 index를 통해 접근 가능 ② dictionary 함수 time complexity는 대부분 O(1) 매우 빠름 ★ list vs. dictionary time complexity ★ operation dictionary list get item O(1) O(1) insert item O(1) O(1) ~ O(N) update item O(1) O(1) delete it.. Computer Science/Data Structures 2022. 11. 6.
DFS / BFS ① DFS(Depth-First Search)⚡️ 먼저 DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 ⚡️ 스택 자료구조(또는 재귀함수)를 이용하며, 구체적인 동작 과정은 아래와 같다 ① 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.③ 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. ⚡️ 동작 예시※ 먼저 방문노드 / 방문기준을 정하는 게 중요→ 문제마다, 상황마다 방문노드 정하는 기준은 제각각이다ex) 예시에서는 방문노드는 1, 방문기준은 번호가 낮은 인접노드부터 방문한.. Computer Science/Algorithms 2022. 10. 14.
🧭Recursion intro🍓 재귀함수란, 자기 자신을 다시 호출하는 함수이다. 함수 내에 다시 함수를 불러서, 동일 함수 로직을 반복적으로(재귀적) 진행한다. DFS 구현을 위해 자주 사용되는 개념. 아래 코드 예시 참조.def recursive_function(): print('recursive call') recursive_function()recursive_function() → 무한히 출력되다가 python의 경우 'RecursionError: maximum recursion depth exceeded while calling a Python object'라는 메시지 출력 - 재귀 최대 허용 깊이가 있어 오류 메시지가 끝에 출력되며 종료. 함수를 부를 때 마다 스택 자료 구조에 함수가 계속 쌓이면서 .. Computer Science/Algorithms 2022. 9. 27.
🍔stack & queue & deque 🧜‍♀️stack / queue / deque 모두 특정 위치에서만 원소를 넣거나 뺄 수 있는 restricted structure1. stack🧜‍♀️ 스택이란, 한 쪽으로만 데이터를 빼고 넣을 수 있는 자료구조로, 한 쪽만 구멍이 뚫려 있는 프링글스 통을 생각하면 된다. 먼저 들어온 데이터가 나중에 나가는 형식 - 즉 나중에 들어온 데이터가 먼저 나가는 형식(선입후출 FILO)의 자료구조. 입구와 출구가 동일한 형태로 매우 간단한 두 연산(원소 추가 O(1), 원소 제거 O(1))이 제공된다. 제일 상단의 원소 확인은 O(1), 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다. 항상 스택 상단에만 초점이 되어 있음. 따라서 삽입할 때에도 가장 최근에 삽입한 원소 바로 위에 삽입.. Computer Science/Data Structures 2022. 9. 23.

티스토리툴바