본문 바로가기

분류 전체보기224

DP-Coin Change Algorithm 코인 체인지 알고리즘! Dynamic Programmming(동적 계획법)이란 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방식을 의미합니다. 동적 계획법을 구현하는 방법 중의 하나가 바로 coin change algorithm(동전 선택 알고리즘) 입니다! 어떻게 코드로 구현하는 지, 어떠한 경우에 사용되는지 한 번 알아보겠습니다. ☺️ 1. 코드 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 //amount원 만큼을 coins[]에 있는 coin들을 사용하여 만들 수 있는 조합의 수를 구하는 method public static long change(int amount, int[] coins) { //조합의 수를 저장할 array 생성 long[] combinat.. 2022. 6. 2.
Graph class 만들기! 안녕하세요 ☺️ 지난번에 알아보았던 Graph! 그렇다면 코드로는 어떻게 나타낼 수 있는지 알아보겠습니다. 크게 Adjacency matrix(인접 행렬)와 Adjacency list(인접 리스트)가 있었는데, 두 가지 모두 코드로 설계해보겠습니다. 먼저! 코드를 작성하기 전에 Graph에는 어떤 것들이 필요한 지 생각해 보면 작성하기 훨씬 수월합니다. 1) Graph를 구성하는 것에는 Vertex가 있죠 2) 또, vertex들을 연결하는 edge가 있습니다. 그렇다면 1) vertex를 추가할 수 있는 코드 2) edge를 추가할 수 있는 코드 이렇게 두개는 필수적으로 들어가야 겠다는 사실을 인지하고 코드를 작성해주면 됩니다! Graph를 이루고 있는 것은 Vertex이죠. Vertex는 node입니.. 2022. 6. 1.
Non-linear(비선형)자료구조(2) - Graph(그래프) 안녕하세요! 이번 글에서는 또다른 비선형 자료구조인 graph에 대해 알아보겠습니다. 처음에 그래프라는 단어를 들었을 때, 코드로 그래프를 어떻게 표현한다는 거지 라는 생각과 엄청나게 개념이 복잡할 수도 있다는 무서움이 있었습니다.😂 그런데 막상 알아보니 크게 두려워할 존재는 아니었습니다.☺️ 그래프는 아래 그림과 같은 형태를 띄는 데이터 구조를 뜻합니다. 트리와 유사하게 노드가 있고, 노드들을 연결하는 edge가 있죠? 구성 요소는 유사한데, 트리와는 조금 다른 것 같습니다. 한번 그림으로 tree와 차이점을 살펴보도록 하겠습니다. 이렇게 양옆에 두고 보니 좀 더 차이점이 명확하게 보이죠? 가장 크게 눈에 띄는 점은 트리는 일방향인 반면에 그래프는 루프 형태가 가능하다는 것입니다. Tree에서 node.. 2022. 6. 1.
Counting sort(계수 정렬) - O(n) Counting sort는 배열에 담긴 숫자가 몇 번씩 들어가 있는지 counting하여 정렬해주는 방식입니다! 예를 들어서 1부터 9까지의 정수만 들어갈 수 있는 int[] unsorted = {9, 2, 1, 3, 9, 7} 이라는 배열이 있다고 가정하면 index가 0부터 9까지의 빈 배열을 하나 만들어 줍니다. int[] countArr = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0} countArr의 인덱스가 1부터 9까지의 정수 역할을 해주게 됩니다. index 0 에는 숫자 0의 갯수가 들어가고, index 1에는 숫자 1의 갯수가 들어가고, index 2에는 숫자 2의 갯수가 들어가고,,,index 9에는 숫자 9의 갯수가 들어가게 되는 것입니다. (여기서는 1~9만 들어가므로 .. 2022. 5. 31.
Bubble sort(버블 정렬) - O(n2) (효율적인 코드 추가) 이름이 귀여운 bubble sort는 배열에서 i번째 요소와 (i + 1)번째 요소 값의 크기를 비교한 후 i번째 요소의 값이 (i + 1)번째 요소의 값보다 크다면 서로 자리를 바꾸어 주는 방식의 정렬법 입니다. 두 요소 중에 작은 값이 수면 위로 버블처럼 떠오르는 장면을 생각하면, 왜 이름이 버블 정렬인지 알 수 있을 것 같습니다. 배열의 모든 요소를 반복해서 돌며 다 확인하기 때문에 시간 복잡도가 O(n2)입니다. - 사용: ① 배열의 규모가 작을 때 적합 ② 구현이 비교적 간단 - 시간 복잡도: O(n2) - 구현 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 public static void bubbleSort(int[] arr) { for(int i = 0; i 2022. 5. 31.
Scanner input 타입 체크하기! Scanner로 input을 받을 때, 원하지 않는 타입이 들어와 런타임에러가 발생하는 경우가 있습니다. 특히나 int, double, long과 같은 타입의 변수에 String 또는 맞지 않는 타입이 들어오게 되면 에러가 발생하게 됩니다. String type 변수인 경우는 숫자를 입력해도 자동적으로 String으로 변환해서 인식을 하는데 숫자 type은 그럴 수 없기 때문입니다. 이런 사항을 미연에 방지하기 위해서는 타입체크가 필수인데요! 방법은 굉장히 간단합니다 ☺️👏 바로 hasNextInt() method를 사용하면 됩니다. (type에 따라 hasNextDouble(), hasNextLong() 등 맞춰서 사용하면 됩니다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16.. 2022. 5. 30.
반응형

티스토리툴바