All Good

Computer Science55

🔸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.
🫂 Prefix Sum intro ✊🏻 구간 합 문제는 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 계산하는 문제 유형을 뜻한다. ✊🏻 예를 들면, 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정했을 때, 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40인 90이 된다. ✊🏻 N개의 정수로 구성된 수열이 있고, M개의 query 정보가 주어진다. 각 query는 left와 right로 구성. 각 query에 대하여 [left, right] 구간에 포함된 데이터들의 합을 출력해야 한다. (수행 시간 제한은 O(N+M)) → 위 예와 접목하자면, 5개의 데이터 (N=5)로 구성된 수열에서 매번 새로운 query 구간마다 해당 합을 구한다면 시간 복잡도는 O(N.. Computer Science/Algorithms 2023. 1. 18.
Regular Expression 💚 정규 표현식은 '패턴 매칭 기반으로 특정한 규칙을 가지는 문자열을 검색&분리하고 교체하는 강력한 기능을 제공하는 형식 언어' 💚 python에서는 re library를 import import re 1. re.search() & re.match() & re.fullmatch() 💚 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 a match. ①.. 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(binary heap) 1. concepts> ☝️ 우선순위 큐 = '우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조' ☝️ 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우 자료구조 추출되는 데이터 stack 가장 나중에 삽입된 데이터 queue 가장 먼저 삽입된 데이터 priority queue 가장 우선순위가 높은 데이터 ☝️ 우선순위 큐는 크게 두 가지 방법으로 구현 가능 ① 단순히 list로 구현 ② heap을 이용하여 구현 ※ heap을 사용해서, 단순히 먼저 들어오거나 나중에 들어온 순서가 아닌, 우선순위가 높은, 즉 최댓값 먼저, 아니면 최솟값 먼저 뽑을 수 있는 자료구조를 이용해 효율적인 시간 효율 내로 연산 진행.. 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.

티스토리툴바