DevBoi

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net

1. 카운팅 정렬 1. 숫자가 등장한 횟수 를 다른 한가지의 배열에 넣는다 2. 다른 한가지의 배열의 누적합으로 값을 update해준다. 3. 기존 숫자들이 있던 배열 마지막부터, 새로 생성한 배열을 보면서, 정렬 index를 찾는다 ex. 4가 5번 등장하면, arr[5] =4 이런식으로 (만약 중복되는 값이 있어, index에 값이 이미있다면, -1 을 해준다.) 이해가 잘되는 애니메이션 링크 https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html Counting Sort This is an animation of the counting sort algorithm found in CLR's Algorithms ..

선택 정렬은, 처음부터 제일 작은값을골라서(큰값이될 수도 있다.) 제일 앞으로 보내고, 그다음부터~ 끝까지 제일 작은값을 찾아서, 그 다음으로 보내는 것이다. 이것도 2중 반복으로 해주면되고, min의 인덱스를 찾아서, 현재 바깥의 index와 min을 스왑해주면 된다. 인덱스가 아니라 밸류로 하게되면, 스왑하기도 어렵고, set으로 되었을때는 swap 이 아니라 제일 최소값으로 값이 전체 복붙이 된다. 1.2중 포문으로 min 찾기 2.min index와 현재 탐색 기준 index 값 swap 하기 https://github.com/Realcheese94/Smith_Algorithm

버블 정렬은 앞에서 부터 1번째와 두번째 두개를 비교해서, 특정 조건에 맞춰서 자리를 바꿔주는 것이다. 이중 for문을 돌려서, 체크를 하고, 두번째 반복문에서는, 제일 마지막에쌓인 데이터는 다시 처리하지 않는다.(처리해도 무방하긴 하다, 다만 낭비가 심하니까, 해당 작업은 하지않는다.) 특수하게 짜는 경우는 내부 반복분에 boolean flag를 두어서, 한번돌았을때, 정렬을 한번 도 하지 않는 경우 즉 swap 이 일어나지 않는 경우는 그냥 끝낸다. 왜냐면, 낭비를 줄이기 위해서....그렇게 하기 이해서는 flag를 내부 반복문 안으로 넣는다. 1. 이중 반복문 (내부 반복문 도는 횟수 max값 -1 씩 감소) 2. 자리바꿈시 flag true , 아니면 break 3. 두개 바꿔야 하면 collec..

힙에 대한 알고리즘 공부를 해보자. 힙은 heap이라고 해서, 다른 의미로 생각할 수 있지만, 쉽게 말하면 단순히 완전 이진 탐색 트리이다. 완전 이진 트리라고 생각하면 된다. 특징으로는 아래와 같다. - 하위의 자식 노드는 무조건 2개가 있다. - 왼쪽이 작거나 오른쪽이 크거나 할 것없이, 단순히 부모가 자식보다 큰게 다이다. - 0의 index는 비워두고 1부터 계산한다. 해당 이유는, 부모는 자식노드 /2 , 오른쪽 은 /2+1 이런식으로 간단하게 구하기 위해서이다. - 최대힙, 최소힙이 존재하여, 데이터를 탐색하는용도 보다 최대값 최소값을 빠르게 찾기 위해서 사용한다. 우선 힙과, 힙에 데이터를 넣는 메소드를 재구현 해보자 데이터를 넣을때, 항상 넣은 데이터와 부모의 데이터를 비교해서, 두개의 s..

트리는 제약 조건이 하나만 있는 간단한 구조이다. 1. 싸이클의 형태를 띄우지 않는다. 이진트리(Binary Search Tree)는 해당 제약 조건에서 2개의 제약 조건이 더 붙는다. 1. 노드의 브랜치는 2개로 제약된다. 2. 노드의 왼쪽은 자신보다 작은 값, 오른쪽은 큰 값을 가지고있는다. import java.util.*; public class Main { public static void main(String[] args) { NodeMgmt mgmt = new NodeMgmt(); mgmt.insertValue(14); mgmt.insertValue(12); mgmt.insertValue(13); mgmt.insertValue(16); mgmt.showAllNodes(mgmt.head); }..

Hash 관련되서, 공부를 해보자, hash는 잘알다 싶이, key-value 로 이루어져 저장하는 구조이다. key를 기반으로 address를 찾아, value를 저장한다. 이를 그냥 저장 할수도 있지만 어떻게 하면 좀 더 잘 이해할수 있을 까 방법은 내가 직접 hash를 구현 해보는 방식이다. Hash는 Key기준으로 별도 address를 가져온다. 따라서 이 key에 해당 하는 address주소가 어떤 값일지 모르기 떄문에 사용하는 량보다 많은 양의 크기를 가지고 있을 수 밖에 없다. key 기준으로 단순히 value 에 값을 넣는 것은 중복 문제를 가질수 있다. 완벽하게 key기준으로 address를 가져오는 함수를 짜면 문제가 안생기겠지만, 그러기는 사실상 어렵다, 따라서 chaining 기법을..