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) :..

def combine(n, k): results = [] def dfs(elements, start, k): if k==0: results.append(elements[:]) for i in range(start, n+1): elements.append(i) dfs(elements, i+1, k-1) elements.pop() dfs([], 1, k) return results N, M = map(int, input().split()) for i in combine(N, M): print(*i)

def permute(N, M): elements = [i for i in range(1, N+1)] results = [] prev_elements = [] def dfs(elements): if len(elements) == N-M: results.append(prev_elements[:]) for e in elements: next_elements = elements[:] next_elements.remove(e) prev_elements.append(e) dfs(next_elements) prev_elements.pop() dfs(elements) return results N, M = map(int, input().split()) for i in permute(N, M): print(*i) 기억..

이번에 배워볼 알고리즘은 벨만 포드 알고리즘(Bellman-Ford Algorithm)이다. 이 알고리즘 또한 이전에 배운 다익스트라 알고리즘처럼 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구할 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다익스트라 알고리즘보다 시간이 더 걸리지만 음의 간선이 존재해도 최단 경로를 찾을 수 있는 알고리즘이다. 벨만 포드 알고리즘은 다이나믹 프로그래밍이라고 할 수 있다. 그 이유는 매번 저장해놓은 최소 비용을 이용해서 새로운 최소 비용으로 갱신하기 때문이다. ​벨만 포드 알고리즘이 다익스트라 알고리즘보다 시간이 오래 걸리는 이유는 다익스트라는 최소 비용을 가지는 간선만 우선적으로 뽑으면서 경우의 수를 줄여가며 비용을 갱신하였다. 하지만 벨만 포드 알고리즘..

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는 하..

bubble: 이중 For문으로 계속 swap merge: 나눠서 다시 합친다. quick: pivot정해서 왼쪽에는 작은거, 오른쪽에는 큰거 selection:?? insertion: 이미 정렬된 애한테 새로운 값을 끼워넣는다.

브루트포스로 풀 걸 그래도 생각하는 과정이 할만했던 것 같다... top을 정의해서 top이 6, 16, 26 처럼 6이 한개이면 last6 = 1, 66, 266처럼 6이 2개이면 last6 = 2.. 이런식으로 커지고 top6가 1이라면 안에서 10번 loop를 돌아서 {top}66{i} 를 프린트 해준다. 6660부터 6669까지 프린트 할 수 있는 이유이다. 마찬가지로 top6가 2이라면 안에서 100번 loop를 돌아서 {top}6{i} 를 프린트 해준다. 66600부터 66699까지 프린트 할 수 있는 이유이다. 이런식으로 top6가 5일때까지 구해줬다. import sys N = int(sys.stdin.readline()) count = 1 top = 0 last6 = 0 while cou..

서론 중국인의 나머지 정리(Chinese remainder theorem; CRT)는 중국의 5세기 문헌인 『손자산경(孫子算經)』에는 나오는 문제로, 내용은 다음과 같다. 3으로 나누었을 때 2가 남고, 5로 나누었을 때 3이 남고, 7로 나누었을 때 2가 남는 수는 무엇인가? x = r1 (mod n1) x = r2 (mod n2) ... x = rk (mod nk) 이고 N = n1 * n2 * ... * nk 라고 하자. mi는 mi * (N/ni) = 1(mod ni)를 계산해서 구한다. 일반해는 x = m1 (N/n1) + m2 (N/n2) + ... + mk (N/nk) mod N 배경 지식 곱셈의 역원 구하기 출처 https://namu.wiki/w/중국인의%20나머지%20정리

비트를 지도처럼 쭉 늘여놓아서 비트맵이다. 데이터를 비트 단위로 처리하기 위해서 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거리를 저장해두는 방식으로 해결한다..

[문제] https://www.acmicpc.net/problem/14719 반례가!!!!!중요하다!!!!! 4 7 3 0 3 4 1 2 1 이러면 끝쪽에서 문제가 생긴다. # 자신보다 크거나 같은 레벨인거 찾고, 없다면 그나마 가장 큰 값인거 찾기 이게 해답에 가까워지는 방법..😇 코드 짜다가 자꾸 헤매서 정리 하기 위해서..! 블로그에서 되게 좋은 코드를 봤는데 영역에서 돌면서, 새로운 영역을 결정할 때 만약 더 높아서 해결이 딱 되면 리턴 해주고, 아니면 제일 큰 height을 계속 갱신을 해주는 방식을 쓰는데 되게 좋아 보였다. 함수로 짜지 않으면 return을 쓰지 못해서 못 짜는 구조였는데 엄청 잘 짰다..! https://gaza-anywhere-coding.tistory.com/113

# 1931 회의실 배정 import sys N = int(sys.stdin.readline()) arr = [] used = [] startTime = 0 endTime = 0 num = 0 for i in range(N): startAndEnd = list(map(int, sys.stdin.readline().split())) arr.append(startAndEnd) arr = sorted(arr, key=lambda x: (x[1], x[0])) while len(arr) > 0: popped = arr.pop(0) if popped[0] >= endTime: used.append(popped) startTime = popped[0] endTime = popped[1] num += 1 print(..

"문제를 잘 읽자!!" 1. 가장 처음과 마지막 문자는 숫자이다 2. 수는 0으로 시작할 수 있다 -> 이거 안읽어서 한시간 날림 ㅠ

# 1655번 가운데를 말해요 import sys import heapq N = int(sys.stdin.readline()) list = [] max_heap = [] min_heap = [] for i in range(N): num = int(sys.stdin.readline()) if len(max_heap) == len(min_heap): # max 에다가 붙이기 heapq.heappush(max_heap, (-num, num)) else: # min 에다가 붙이기 heapq.heappush(min_heap, num) if len(max_heap) > 0 and len(min_heap) > 0: if max_heap[0][1] > min_heap[0]: # swap해주기 fromMax = heap..

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

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..

using System; using System.Collections; using System.Collections.Generic; namespace tutoring { class MyStack { static void Main(string[] args) { Stack stack = new Stack(); stack.Push(1); stack.Push(2); stack.Push(3); stack.Push(4); stack.Push(5); Console.WriteLine("stack.Count: {0}", stack.Count); Console.WriteLine(); while (stack.Count > 0) Console.WriteLine(stack.Pop()); Console.WriteLine(); C..

System.Collections 라이브러리로 해봤다 using System; using System.Collections; using System.Collections.Generic; namespace tutoring { class Program { static void Main(string[] args) { Queue _queue = new Queue(); _queue.Enqueue("1"); _queue.Enqueue("2"); _queue.Enqueue("3"); Console.WriteLine("이제 프린트 한다!"); foreach (var queue in _queue) { Console.WriteLine("Queue: {0}", queue); } } } }

https://kamang-it.tistory.com/entry/Macvisual-studio-code-간단한-c프로젝트-만들기 [Mac][visual studio code] 간단한 c#프로젝트 만들기 visual studio code를 맥에서 실치하는 이유는 아마 대부분은 C#때문일 것이다. 물론 다른 언어도 할 수 있지만 다른 언어는 원래 좋은툴이 너무너무너무 많다. 게다가 엄밀히 말하면 visual studio code는 kamang-it.tistory.com "dotnet new console" 했을 때 command not found: dotnet 이라고 나온다면, brew install dotnet 해주자!

# 1722 순열의 순서 # 10845 큐 N = int(input()) queue = [] for i in range(N): command = input() if command.__contains__("push"): queue.append(command[-1]) elif command.__contains__("pop"): if len(queue) != 0: val = queue.pop(0) print(val) else: print("-1") elif command.__contains__("size"): print(len(queue)) elif command.__contains__("empty"): if len(queue) == 0: print("1") else: print("0") elif comman..

# 2504 괄호의 값 str = input() # 맞는지 검증 stack = [] for index, char in enumerate(str): if char == '(': stack.append('(') elif char == '[': stack.append('[') elif char == ')': if len(stack) > 0: ret = stack.pop() if ret != '(': print("0") exit(0) else: print("0") exit(0) elif char == ']': if len(stack) > 0: ret = stack.pop() if ret != '[': print("0") exit(0) else: print("0") exit(0) if len(stack) !=0:..

import sys T = int(sys.stdin.readline()) for i in range(T): A, B = map(int, sys.stdin.readline().split()) # B를 2의 제곱으로 분리하기 binaryArrayForB = list(map(int, list(bin(B)[2:]))) binaryArrayForB.reverse() modularArrayForB = [0] * len(binaryArrayForB) # modular array 만들기 modularArrayForB[0] = A % 10 for j in range(1, len(binaryArrayForB)): modularArrayForB[j] = (modularArrayForB[j-1] ** 2) % 10 # pri..