sweetdev

Spanning Tree input: 아무 그래프 output: 그래프 내의 모든 정점을 포함하는 트리 * 트리이므로 사이클이 있어서는 안된다. Minimum Spanning Tree input: 방향없는 weighted edge 그래프 output: cycle 없는 edge cost가 최소인 spanning tree (같은 cost인 그래프가 여러개 나올 수도 있다.) Kruskal's Algorithm input: 방향없는 weighted edge 그래프 output: cycle 없는 edge cost가 최소인 spanning tree 0) weight순으로 edge를 sorting한다 1) weight이 가장 작은 edge를 선택한다, cycle을 만들지 않는다면 추가 시간복잡도 O(NlogN) :..

for문 1개(i) + two pointer을 사용해서 구한다.

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791189909178

한국어로 찾았을 때 아무결과도 안나오는거 보면 좀 마이너한듯?? linear data structure이고, linked list와 array의 장점을 모두 살린 자료구조이다. 링크드 리스트 장점: 삽입하는데 O(1)걸린다. 근데 단점 - search시간이 O(n)이다... Q) search시간을 줄일 수 없을까??? unrolled linked list는 array와 linked list의 장점을 모두 갖고 있다 - 한 노드에 여러개를 보관해서 search시간 낮아지고, insertion과 deletion이 linked list만큼 빠르다. 일반적인 구현으로는 꽉 채우지 않고 3/4정도만 채워준다고 한다. 장점) pointer/refernece를 위한 storage down. linked list는 하..

비트를 지도처럼 쭉 늘여놓아서 비트맵이다. 데이터를 비트 단위로 처리하기 위해서 long 배열로 할당한 자료형 C의 모든 자료형은 최소 단위가 byte라서, 실제로는 8의 배수의 bit로 나오게 된다. 기본 연산 OR can be used to set a bit to one: 11101010 OR 00000100 = 11101110 AND can be used to set a bit to zero: 11101010 AND 11111101 = 11101000 AND together with zero-testing can be used to determine if a bit is set:11101010 AND 00000001 = 00000000 = 011101010 AND 00000010 = 00000010..

XArray는 매우 큰 포인터 배열처럼 동작하는 추상 데이터 타입(abstract data type) 입니다. 해시와 크기 변경 가능한 배열을 모두 만족 시킵니다. 해시와 다른 점이라면, 캐시 친화적인 방식으로 위치 이동(이전, 다음)을 효율적으로 할 수 있습니다. 크기 변경 가능한 배열과 다른 점이라면, 배열의 크기를 증가 시키기 위해서 데이터를 복사 하거나 MMU 매핑을 변경할 필요가 없습니다. 양방향 연결 리스트(doubly-linked list) 보다 메모리 효율성이 좋고 병렬화 가능하며 캐시 친화적입니다. 또한 RCU의 장점을 활용하여 락킹없이 조회 작업을 수행합니다. 위와 같이 XArray는 많은 장점을 가지고 있는 자료구조 입니다. 하지만 XArray에는 몇가지 특징(장단점)들이 있습니다. ..

자료구조 시간에 배운 binary search tree를 알아야 이해할 수 있는 개념이다!! (자신의 왼쪽 트리에는 현재보다 작은거, 오른쪽 tree에는 현재 값보다 큰 값이 왔던 tree이다. ) (inorder traverse를 하면 오름차순으로 정렬된 값을 얻을 수 있다) red black tree는 binary search tree중 balance가 맞는 tree이다. (self-balanced라고 한다) red black tree의 조건 1. root node는 black 2. 모든 external node는 black 3. red의 자식은 black 4. 모든 leaf node에서 root node까지 가는데 만나는 black의 개수는 같다. 처음 root는 black으로 만들고, 자식으로는 ..

* radix tree 는 radix trie, compact prefix tree라고도 부른다 * radix tree역시 binary search tree를 알아야 한다. 개인적으로는 red black tree 글을 작성하고 이 글을 작성했으므로 red black tree 글을 먼저 보고 오는걸 추천한다. radix tree는 binary search tree, red black tree처럼 왼쪽 < 자신 < 오른쪽 노드의 크기로 배치된다. 그러나 radix tree는 트리의 균형을 맞추는 방식이 조금 다르다. red-black tree는 색상값 데이터를 가지고 노드를 좌우로 회전시키면서 균형을 맞췄다. 그러나 radix tree는 이런 회전 작업 없이도, 키 값에 따라서 0이면 왼쪽, 1이면 오른쪽으..

발음은 트라이(try), 트리(tree) 두 개다 쓰인다. 본래 Trie 가 re"trie"val 에서 왔기에 '트리' 발음으로 불려야하지만 tree 도 똑같은 발음을 가지고 있어서 이 둘을 분간하기위해 트라이 라고 부르는 사람도 꽤 된다. 딱히 standardized 된게 아니니 입맛에 맞게 쓰자 https://namu.wiki/w/트라이#fn-5

a보다 b가 먼저 실행되어야해! 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 [알고리즘 구현하기] 각 노드들의 진입 차수 계산 진입 차수가 0(들어오는 간선의 수가 0)인 노드들을 큐에 삽입 큐에서 노드를 꺼내 연결된 간선을 제거 제거로 인해 진입 차수가 0이 된 노드를 큐에 삽입 (3)~(4) 번을 반복하며 큐가 비었으면 종료 https://www.acmicpc.net/problem/1766 백준 문제집 문제를 푸는데 자꾸 시간초과가 났다 ㅠㅠ 3이랑 4 과정을 for문 하나에서 해결해야 했는데 그게 문제였던 것 같다.... 최단거리 구하기 각 노드에 저장소를 만들어서 min거리를 저장해두는 방식으로 해결한다..

합칠 때 정렬이 되어서 머지소트임!

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication6 { class Program { static void Main(string[] args) { int[] b = new int[] { 99,8,4,6,9 }; int temp = 0; for (int i = 1; i b[j]) { temp = b[i]; b[i] = b[j]; b[j] = temp; } } } for (int i = 0; i < b.Length; i++) { C..

해시 테이블을 한마디로 정의하면 공간을 팔아서 성능을 얻는 알고리즘이다... 해시 테이블을 궁극의 탐색 알고리즘이라고 부르기도 하는데, 무려 O(1)의 시간복잡도를 갖기 때문이다. (물론 O(n)이 최악이다) blog[1] = "123123" 라는 딕셔너리가 있다고 가정해보자. 그러면 123123이라는 데이터를 해시함수의 매개변수를 입력한다. 해시함수는 123123이라는 데이터를 1이라는 주소값으로 바꿔서 리턴해준다. 해시 함수는 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있다. 통계적으로 봤을 때 7~80%를 넘으면 성능 저하가 나타난다고 한다... 해시 테이블에서는 크게 두가지의 문제가 나타날 수 있다. 1. Collision 해시함수가 123123도 1을 return하고, 12..

정의 phi(N) - N보다 작고 N과 서로소들인 수의 갯수. ex) phi(10) = 10보다 작고 10과 서로소인 수 = {1, 3, 7, 9} * pi(N)과는 다름. pi(N)은 N보다 작은 소수의 갯수!! * 곱셈역을 배웠다면...Zn*의 크기와 phi(N)은 같다 피함수의 성질 1. phi(1) = 0 2. phi(P) = p-1 3. m,n이 서로소이면 phi(m * n) = phi(m) * phi(n) 4. phi(p^e) = p^e - p^(e-1) (p가 소수이면, e가 양의 정수이면) m,n이 서로소이면 phi(m * n) = phi(m) * phi(n) 증명하기 원래 성질은 서로소이면 다 되는데 여기서 증명은 간단하게 m, n 모두 소수일 때만 한다. phi(m * n)은 m*n보다..

어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 된다. 시간복잡도: O(N^1/2) 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다. 배열을 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.(지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.) 2부터 시작하여 남아있는 수를 모두 출력한다. [참고] velog.io/@max9106/Algorithm-에라토스테네스의-체 [코드] import sys import math import itertools N_input = int(sys.stdin.readline()) line = li..

input: 두 문자열 output: 겹치는 최장 길이 문자열 LCS: Longest Common Subsequence 백준에서 LCS문제를 풀게 되었는데 이것 자체가 하나의 알고리즘이라고 해서 정리하게 되었다. LCS는 DP기반의 알고리즘이고, Subsequence이므로 꼭 연속은 아니어도 된다. 부분부분 잘라서 존재하기만 해도 ㄱㅊ 백준에서 들은 예는 다음과 같다. ACAYKP CAPCAK 에서 LCS는 ACAK이다. 이렇게 세팅해놓고 시작한다. 글자가 같을때는 그 전줄전의값 + 1 해서 넣어주면 되는데, 다를때는 윗줄과 옆칸을 비교해서 더 큰값을 넣어준다. 코드 !! import sys str1 = sys.stdin.readline().rstrip('\n') str2 = sys.stdin.readl..

모든 점을 다 방문해보아야 하는 DFS와 달리, BFS로 찾은 경로는 도착점이 나오는 즉시 최단거리임을 알 수 있어서 바로 종료할 수 있는 장점이 있다. 따라서 최단거리를 구하는 문제에서는 BFS를 쓰는것이 좋다. 코드를 어떻게 짤까 복잡하게 생각했었는데 bfs()를 콜 하고 제일 먼저 도착점과 같아질 때 끝인것이었다..! 백준 2178번을 풀이하면서 작성한 코드는 다음과 같다. # 2178번 미로 탐색 # bfs로 탐색해서 제일 먼저 끝점이랑 같아질 때 리턴. import sys N, M = map(int, sys.stdin.readline().split()) data = [] for _ in range(N): data.append([int(d) for d in str(sys.stdin.readline..

DP...점화식..고딩때 수학할때도 점화식이 너무 어려웠었다 DP의 핵심은 1. 점화식 세우기 2. 값이 아니라 여기까지 했을때 max(경우의 수)를 저장해두기 3. 그리고 그걸 갱신하기 인것 같다. 나는 맨날 값으로 접근해서 되게 어려워했는데 그 전의 max 그리고 그 다음 식의 점화식만 생각하면 훨씬 쉽다. 수학에서의 점화식은 어려운 계산을 잘 다루지 않는데 여기서는 복잡한 계산은 다 컴퓨터가 해주니까 식도 더 복잡해...계산도 더럽다 n=3넘어가면 계산도 못해본다 코드나 잘 짜야지ㅠ

Branch & bound는 한국말로 하면 '분기 한정'이라고 할 수 있는데, 분기를 한정시켜서 쓸데 없는 낭비를 줄이는 방법이다. backtracking보다 나은 방법이라고 하는데, 왜냐면 backtracking은 가보고 진행이 안되면 돌아오는데 branch and bound는 최적해를 찾을 가능성 자체가 없으면 가 보지도 않는 느낌이랄까??? 이게 어떻게 가능한지 한번 살펴보자. 일단 0/1 knapsack problem이 뭔지는 옛날 게시글에서 설명했으니까 패스한다. 이글을 참조하세요 https://sweetdev.tistory.com/528 이런 물건 4개가 있었고, 내 가방의 weight의 한계는 15였다고 해보자. 내가 branch and bound에서 되게 특이하다고 생각했던 점은, 얘는 p..

해밀토니안...! 해밀토니안 자체는 사람 이름이 아니고, '해밀턴'씨가 만들어서 해밀토니안인데 이 아저씨도 약간 다작해서 짜증나는 사람이다. 물리학도 수학도 컴퓨터공학도를 동시에 고통주는 이 능력... 아무튼 해밀토니안 사이클은 다음과 같은 문제이다. 모든 정점을 한번씩 방문하고 첫 지점으로 돌아와야 한다! 그런 길이 존재할까??? (directed graph도 되고 undirected graph도 됨) 다음과 같이 (못그린) 그래프가 있다고 해 보자. 1부터 시작해서 모든 정점을 다 방문하고 다시 1로 돌아오는 path가 있을까?? 이를 위해서 다음과 같은 표를 하나 그렸다. 일단 첫 시작점은 1이니까 1을 써준다. 다음으로 앞에 나오지 않고, 바로 앞 칸과 이어져 있는 정점을 써준다. 이렇게! 마지막..

n-queens problem은 크기가 N인 체스판에, 여왕말 N개를 서로를 공격할 수 없게 두는 것이다. 이건 꽤 흥미로운데, 왜냐면 queen은 좌우상하 대각선4방향 전부 다 되기 때문...!!! 그래서 생각보다 놓을 수 있는 곳이 한정적이다. 이걸 풀기 위해서 backtracking이라는 기법을 적용했다. 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 출처: https://chanhuiseok.github.io/posts/algo-23/ 일단 어떻게 거기 놓을 수 있는지 판단하는 방법부터 알아보자. 다음과 같이 (1,2)에 놓인 queen이 있다. (왼쪽 위는 0,0이..

subset은 한국말로 '부분집합'이라는 뜻이고, subset sum problem은 따라서 부분집합 더하기 문제?라고 생각할 수 있다!! subset sum problem이 어떤거냐면, total = 11이고 {2, 3, 7, 8, 10}인 집합이 있으면, 집합의 원소들을 더해서 total값을 만들 수 있는지 확인하는 문제이다. 세로줄에는 각각 원소들, 가로줄에는 0부터 total까지가 배치되어 있다고 해 보자. 2, 3, 7, 8, 10을 0개씩 쓰면 합이 0이 될 수 있으므로 첫 줄을 다 T로 채워준다. 1은 2의 합으로 될 수 없으므로 F. 2는 2의 합으로 될 수 있으므로 T. 3 이상의 값은 2로 만들어질 수 없으므로 전부다 F. 3보다 작은 값은 !!!윗줄을 그대로 채워준다 3은 T 이제 4..

알고리즘 문제중에 굉장히? 그나마 흥미로운 문제라고 생각했던 knapsack problem!!!! knapsack은 작은 배낭이라는 뜻이다...귀엽네... 가방에 어떤어떤 물건을 넣을수 있을까? 를 물어보는 알고리즘 문제다. 미국놈들은 이렇게 문제 이름은 귀엽게 짓고, 문제는 ㅈㄴ 어렵게 내는 습관이 있는 것 같다. 아무튼 가방에 어떤 물건을 넣을 수 있을지 dynamic problem으로 풀어보자 ^^ 나에게는 이런 4개의 물건이 있다. 각각은 weight과 value를 가지고 있다. 그리고 나에게는 한개의 가방이 있는데, 이 가방에는 최대 7만큼의 weight만 들어갈 수 있다. 내가 넣은 물건들의 value의 합이 최대가 되게 하려면, 어떤 어떤 물건들을 넣어야 할까??? 이를 Dynamic pro..

1. Top-Down 방식: O(2^2/n) a.k.a : Recursive한 방식. T(n): fib(n)을 계산하기 위해서 fibonacci함수를 호출하는 횟수 T(0) = 1 T(1) = 1 T(n) = T(n-1) + T(n-2) + 1 (for n >=2) T(n-1) > T(n-2)임은 명백하고, T(n-1) + T(n-2) > 2 * T(n-2) 임도 명백하다. T(n) > ( 2 ^ 1 )T(n-2)이고, T(n) > ( 2 ^ 2 )T(n-4), T(n) > ( 2 ^ 3 )T(n-6), ... T(n) > 2*(n/2)T(0) 일 것이다. 따라서 계산은 2^n/2번 이루어진다. 2. Bottom-Up 방식 1 1 2 3 5 8 13 이런식으로 n(linear)하다. 그러므로 O(n)

가정 '그림'과 같이 방향이 없는 weighted edge로 구성된 그래프라고 가정한다. 방향이 있는 edge도 가능하다. 결과 내가 정한 시작 노드 한 개에서 모든 노드로 가는 가장 빠른 길과 cost를 알 수 있다. 과정 초기화 먼저 시작 노드를 정한다. (나는 U라고 정했다.) U에 인접한 노드들의 distance를 저장해준다. 루프 저장한 노드들 중에 가장 빠르게 갈 수 있는 노드를 고른다. 그리고 그 노드에서 갈 수 있는 길들을 찾아서 업데이트 해준다. (기존 distance와 새로 찾은 node를 통해서 가는 것중에 짧은 distance로 업데이트 한다. distance = min(저장된 값, 새로 찾은 노드까지 가는 값 + 새로운 노드에서 원하는 노드까지 거리)) 모든 노드를 방문할때까지 반..

void dfs(int v){ nodePointer w; visited[v] = TRUE; printf("%5d", v); for (w=graph[v]; w; w=w->link){ if (!visited[w->vertex]) dfs(w->vertex); } }

undirected graph: (u,v)로 edge표현 directed graph: 로 edge표현, u가 tail이고 v가 head임.

트리를 사용해서 '집합'을 표현해보자 집합의 모든 원소는 0, 1, 2, ..., n-1이라고 가정한다. 모든 집합은 disjoint된다고 가정한다. (각각 집합들끼리 겹치는 원소가 없음) 얘는 0~9인 예제이다. 집합에 대해 수행하고자 하는 연산은 다음 두 가지이다. (1) disjoint set union (2) find(i) (1)은 A∪B를 할 수 있다는 의미, 즉 (2)는 원소 i가 속한 집합을 리턴받는거 가능 A∪B을 하려면 어케 할까... 두 트리중 하나를 다른 트리의 서브트리로 만들면 된다. 저 위에 그림에서 S1 ∪ S2를 하려고 하면, 하면 되는것처럼 말이다! 두가지 함수를 짜보자! void simpleUnion(int i, int j){ parent[i] = j; } int simpl..

forest F에 대응하는 binary tree T의 preorder, inorder traverse는 F의 순회와 자연스러운 대응 관계를 가진다. [Preorder Traverse] T의 preorder traverse는 다음과 같이 정의된 forest preorder로 F의 노드들을 traverse하는 것과 동일하다. (1)F의 첫번째 tree의 node 방문 (2)첫번째 tree의 subtree를 preorder traverse한다. (3) F의 나머지 tree들을 preorder traverse한다 [Inorder Traverse] T의 preorder traverse는 다음과 같이 정의된 forest inorder로 F의 노드들을 traverse하는 것과 동일하다. (1)F의 첫번째 tree의 ..

중앙대학교 소프트웨어대학 강현철교수님의 "자료구조" 과목을 듣는 과정에서 학습 목적으로 작성한 포스트입니다. Selection Tree(선택 트리)는 merge sort에 사용하는 특수한 구조를 가지는 트리 자료구조다. selection tree에는 크게 winner tree와 loser tree가 있다. 다른 말로는 tournament tree라고도 불린다. (merge sort가 뭔지 모른다면 merge sort를 공부하고 와야 이 포스팅을 이해할 수 있다..!) 쪼갠 리스트들을 합치는 과정에서 각 리스트의 최솟값(최댓값)들을 비교해야 하기 때문에 n/2 , n/2개를 합칠때마다 (n-1)번의 비교횟수가 필요하다. 이걸 줄이기 위해서 선택트리를 이용한다. #include #include #includ..