본문 바로가기

⏳ 알고리즘

(103)
알고리즘 문제 - LV2. 위장 문제 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. clothes의..
트리(3) - 자가 균형 이진 탐색 트리 책 을 기본으로 배운 알고리즘 내용입니다 목차 자가 균형 이진 탐색 트리의 종류 1. AVL 1-1) AVL의 회전(LL, LR, RR, RL) 1-2) AVL의 삽입 구현 1-3) AVL의 구현 2. 레드-블랙 트리 3. 이진 힙 자가 균형 이진 탐색 트리 트리에서 노드의 삽이과 삭제가 이루어질 때 자동으로 균형 트리를 유지하는 이진 탐색 트리 균형 트리 : 모든 하위 트리의 높이 차가 1이하인 트리 균형도 : 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 균형 조정 방법으로는 ① 노드 분할 및 병합 : 노드의 자식은 2개 이하이다. 노드가 많으면 두 개의 서브 노드로 나뉜다. ② 노드 회전 : 간선을 회전한다. x가 y의 부모이면, y를 x의 부모로 만들고, x는 y의 자식 중 하나늘 거둔다. ..
트리(2) - 이진탐색트리 책 을 기본으로 배운 알고리즘 내용입니다 목차 이진 탐색 트리 구축, 탐색 과정을 그림으로 이해 이진 탐색 트리 구현 이진 탐색 트리(BST, Binary search tree) 이진탐색(binary search)과 연결리스트(linked list)를 결합한 트리 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됨. - 이진탐색의 경우 탐색에 소요되는 계산복잡성은 O(logn)으로 빠르지만 자료 입력, 삭제가 불가능하다. - 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 O(1)로 효율적이지만 탐색하는 데에는 O(n)이다. 이진 탐색 트리의 속성 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드만 존재한다. 각 노드의 오른쪽 서브트리에..
트리(1) - 이진트리 책 을 기본으로 배운 알고리즘 내용입니다 목차 이진 트리의 종류(완전 이진 트리,포화 이진 트리) 이진 트리 구현 1) 개념 계층적인 구조를 표현 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨 2) 용어 더보기 루트 노드(root node) : 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node) : 자식이 없는 노드 내부(internal) 노드 : 리프 노드가 아닌 노드 노드 크기(size) : 자신을 포함한 모든 자손 노드의 개수 노드 깊이(depth) : 루트에서 어떤 노드로 가는 경로의 길이 노드 레벨(level) : 노드 깊이(depth) + 1 노드 차수(degree) : 각 노드가 지닌 가지의 수 트리 차수(degree of tree..
알고리즘 문제 - LV2. 프린터 문제 https://programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 내 풀이 코드 def solution(priorities, location): answer = 1 to_behind = len(priorities)-1 while priorities: poped = priorities.pop(0) for i in priorities: if i > poped: if location == 0: location = to_behind..
그래프 책 을 기본으로 배운 알고리즘 내용입니다 목차 1. 그래프(Graph) 2. 그래프(Graph)의 특징 3. 그래프(Graph) 관련 용어 4. 그래프(Graph)의 종류 5. 그래프와 트리의 차이 6. 그래프(Graph)의 구현 2가지 1. 그래프(Graph) 그래프(Graph)는 일련의 노드(node, 정점) 집합 V와 간선(arc, 아크) 집합 E로 구성된다. 일반적으로 노드엔 데이터, 간선엔 노드와 노드 사이의 관계 정보가 포함되어 있다. 2. 그래프(Graph)의 특징 그래프는 네트워크 모델 이다. 2개 이상의 경로가 가능하다. 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다. self-loop 뿐 아니라 loop/circuit 모두 가능하다. 루트 노드라는 개념이 없다. 부모-..
동적 계획법(Dynamic Programming) 책 을 기본으로 배운 알고리즘 내용입니다 목차 동적 계획법(Dynamic Programming) 메모이제이션(memoization) 메모이제이션을 활용한 피보나치 수열 동적 계획법(Dynamic Programming) 동적 계획법은 복잡한 문제를 재귀를 통해 간단한 하위 문제로 분류하여 단순화하여 해결하는 방법이다. 어떤 문제가 최적 부분 구조, 중복되는 문제를 가지고 있으면 동적 계획법으로 해결 가능하다. 메모이제이션(memoization) 메모이제이션은 동적 계획법의 핵심이다. 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거하는 것. ex) 메모이제이션을 활용한 피보나치 수열 피보나치 수열은 제 0항을 0, 제 1항을 1로 하고, 그 다음 항..
검색 알고리즘(순차 검색, 이진 검색) 책 을 기본으로 배운 알고리즘 내용입니다 목차 정렬되지 않은 배열 - 순차 검색(Linear Search) 정렬된 배열 - 이진 검색(Binary Search) 리스트가 정렬되어 있다고 할 때, 이진 검색(binary search)이 순차 검색(linear search)보다 더 효율적이다. 정렬되지 않은 배열 순차 검색(Linear Search) 순차 검색은 키(key)라는 요소를 가지고 순차적으로 리스트의 각 요소들을 비교하는 검색방법이다. 리스트 요소의 수가 커지면 커질수록 선형 검색 시간이 증가하므로, 큰 리스트에서는 비효율적이다. (시간복잡도 O(1),O(n/2),O(n)) 키(key)가 찾고자 하는 요소와 일치 할 때 까지 수행을 진행하고, 매치되었다면, 순차 검색은 매칭된 요소의 위치(inde..
알고리즘 문제 - LV1. K번째 수 문제 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100 이하입니다. arra..
알고리즘 문제 - LV1. 가운데 글자 가져오기 문제 단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요. 단어의 길이가 짝수라면 가운데 두글자를 반환하면 됩니다. 재한사항 s는 길이가 1 이상, 100이하인 스트링입니다. 입출력 예 s return abcde c qwer we 내 풀이 def solution(s): answer = '' if len(s)%2 == 0: answer = s[len(s)//2-1] + s[len(s)//2] else: answer = s[len(s)//2] return answer 다른 풀이 def solution(s): return s[(len(s)-1)//2: (len(s)//2) + 1]