본문 바로가기

알고리즘

(87)

백준 2470 두 용액 백준 2470 두 용액 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 배열 정렬후, 각 끝 인덱스 값 합과 target과 비교. 만약 합이 target보다 작으면 left + 1 이동 합이 target보다 크면 right -1 이동 📄 나의 풀이1 # 배열의 index를 left, right로 하고 # 가깝지 않으면 index 이동하는 방식으로 풀어야 하나..? # 두 용액의 합이 0에 가까운지 비교 impo..

백준 2110 공유기 설치 백준 2110 공유기 설치 이분탐색! https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 최종적으로 원하는 값이 공유기 설치 간격! mid값이 공유기 설치 간격이 나오도록 코드를 구성하는것이 좋을듯하다. 첫번째 집에는 무조건 공유기를 설치해야 한다. 아래 코드는 답안 코드를 보며 분석! accepted한 나의 코드다. 안보고 짤 수 있을 때까지 반복해서 풀 예정... 📄 나의 코드 import s..

데일리 알고리즘 230525 데일리 알고리즘 230525 프로그래머스, 행렬의 덧셈 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📌 0으로 초기화된 행렬 리스트 생성 maxtrix = [[0 for c in range(column)] for r in range(row)] 📄 나의 코드 arr1 = [[1,2],[2,3]] arr2 = [[3,4],[5,6]] def solution(arr1, arr2): result = [[0 for col in range(len(arr1[0]))] for row in range(len(arr1))] for r in range(len(arr1)):..

백준 10971, 외판원 순회 2 백준 10971, 외판원 순회 2 2023.05.21 - [알고리즘] - DFS 순열, 조합 도시 1,2,3,4 방문한다고 하면 시작도시를 1이라 정하자, 그러면 2,3,4의 순열 조합으로 나열한 뒤 시작도시, 끝도시를 1로 설정하면 된다. 이런 식으로 코드를 짜기 어렵게 느껴졌다. 참고용 코드를 보며, 왜 이렇게 하는지 따라가 모든 도시를 방문하는 순열조합을 출력해봤다. 그러니 코드가 이해된다!!! 나는 모든 경우를 다 탐색하는 부르트포스 방식으로 문제를 풀어봤다. 📄 test.py # 출발지 도착지 제외하고 순열 N = 4 visited = [False]*N perm = [] def dfs(n, start): if n == 0: perm.append(start+1) print(*perm) perm.p..

DFS 순열, 조합 DFS 순열, 조합 python 내장함수를 사용하지 않고 dfs로 순열 조합을 풀 수 있다. backtracking 개념과 stack 자료구조가 선행되어야 코드를 이해할 수 있다. 이 개념은 N-queen문제를 정리할때 자세히 포스팅 하도록 하겠다. 📄 순열.py import sys input = sys.stdin.readline N, M = map(int, input().rstrip().split()) visited = [False]*N perm = [] def dfs(m): if m == 0: print(*perm) return else: for i in range(N): if visited[i] == False: visited[i] = True perm.append(i+1) dfs(m-1) visi..

자료구조, RBtree 구현 자료구조, RBtree 구현 2023.04.04 - [알고리즘] - 자료구조, AVL 📌 RBtree란? AVL 자가균형트리의 한 종류로, 가장 많이 사용되는 균형 이진탐색트리이다. 다음과 같은 속성을 지닌다. 1. 모든노드는 red 혹은 black 2. 루트 노드는 black 3. 모든 nil(leaf)노드는 black 4. red의 자녀들은 black(red가 연속적으로 존재할 수 없다) 5. 임의의 노드에서 자손 nil노드들까지 가는 black 수는 같다(자기자신제외) 자가균형트리 AVL에서는 양쪽 부트리 높이가 중요하다. 그러므로 5번 속성이 굉장히 중요하다. 📌 이러한 자료 구조가 필요한 이유? 중간값 자료가 필요할 때! 다른 말로, 최솟값 & 최댓값이 필요한 경우(sort)가 아닐때. 데이터 ..

자료구조, rbtree delete 자료구조, rbtree delete 삭제 역시, 해당 노드를 삭제했을 때, 트리의 균형이 깨지는지 여부가 중요하다. 트리 균형에 위반되지 않는 조건 1. 삭제 노드의 컬러가 Red인 경우 2. 삭제 노드의 컬러가 Black이고 자식이 1개일 경우(유일한 자식) 이 외의 케이스는 모두 트리 균형이 깨질 수 있다. 📌 RB-Transplant 기존 노드의 부모 노드(u.p)를 새로운 노드의 부모(v.p)로 설정해주므로써 노드를 교체하는 함수이다. 📄 rbtree.c void rbtree_transplant(rbtree *t, node_t *u, node_t *v){ if(u->parent == t->nil){ t->root = v; } else if (u == u->parent->left){ u->paren..

자료구조, rbtree insert 자료구조, rbtree insert📌 RB-Insert 삽입노드는 항상 RED 왜? 삽입 후 모든 경로에 Black Height 영향을 주지 않기 때문.root부터 시작해 트리를 순회하면서 z노드(삽입노드)의 부모 위치를 찾아줍니다. 부모 위치(y)를 찾은 뒤 z노드의 부모를 y노드를 가리키도록 포인터로 설정해주고 z노드의 자식들은 모두 nil노드로, 컬러는 빨간색으로 설정해줍니다. 그런 다음, RB트리의 균형을 맞춰주는 함수로 이동! 📄 rbtree.cnode_t *rbtree_insert(rbtree *t, const key_t key) { // TODO: implement insert node_t *y = t->nil; // y will be parent of z node_t *x = t->root..

자료구조, AVL Left-Rotate & Right-Rotate 구현 자료구조, AVL Left-Rotate & Right-Rotate 구현 2023.04.02 - [알고리즘] - 자료 구조, Linked List 2023.04.02 - [알고리즘] - 자료구조, Binary Search Tree 저번에 Linked List와 BST를 공부하면서 AVL을 가볍게 공부해봤다. 오늘은 AVL에 대해서 공부한 내용을 정리해 보려고 한다. 📌 AVL이란? Adelson-Velsky, Landis 사람 이름(소련, 1964년) 약자로 자가균형트리를 의미한다. 모든 노드에 대해서 왼쪽부트리와 오른쪽 부트리의 높이차가 1이하인 BST를 의미한다. BST AVL 차이가 보이는가? BST는 루트 노드에서 오른쪽 부트리와 왼쪽 부트리의 높이차가 2로, 1이하가 아니므로 AVL이 아니다. 반..

자료구조, Binary Search Tree 자료구조, Binary Search Tree Binary Search Tree 📌 BST란? 트리 자료구조의 한 종류 부모노드보다 작은 값은 왼쪽 자식 노드에, 부모노드보다 큰 값은 오른쪽 자식 노드에 저장하는 방식으로 데이터 저장 📌 장점 탐색, 삽입, 삭제 연산 시 시간복잡도 O(log n) 최대 2개의 자식 노드를 가지므로 이진 탐색 트리에서 데이터를 탐색할 때 절반 이하의 노드를 탐색한다. 데이터가 정렬된 상태를 유지하므로 중위순회(왼쪽서브노드 → 루트 → 오른쪽서브노드)하면 오름차순으로 정렬된 값을 얻을 수 있다. 📌 단점 이상적인 BST 모양이 아닐 경우(균형잡힌 이진 탐색트리) 경우, 시간 복잡도가 O(n)에 수렴한다. 이러한 최악의 경우를 피하기 위해, 데이터를 삽입할 때마다 트리의 균형을..

이전 1 2 3 4 5 6 7 ··· 9 다음

티스토리툴바