분류 전체보기
[알고리즘] 정렬만 되어있으면 검색하기 참- 좋은데, 트리의 이진검색(Java)
이진 검색 트리 (BST : Binary Search Tree) 최대 두 개의 자식을 가지는 구조 노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이상이다. 이진 검색 트리의 장점 가운데 하나로 룩업 연산(트리에 있는 특정 노드의 위치를 알아내는 연산)을 빠르고 간단하게 처리할 수 있다. ⛔️ 순차 탐색보다 조금 더 효율적이지만, 미리 정렬이 되어있어야 한다. 순차 탐색은 O(n)의 복잡도를 가지는 반면 이진 탐색은 O(log n)이다. 코드 흐름 0,1,2,3,4,5,6,7,8 1. 중간 값 4가 root가 된다. 만약 짝수 개인 경우 더 작은 숫자를 root로 설정한다. 2. 앞 뒤로 0,1,2,3 / 5,6,7,8에서 중간 값 1, 7을 4의 자식 노드로 ..
[알고리즘] 힙 (Heap) - 최소힙, 최대힙
힙 (Heap) 최댓값이나 최솟값을 빠르게 하기 위해서 고안된 완전 이진트리(왼쪽부터 추가하는 구조)를 기본으로 한 자료구조이다. 트리 구조를 기반으로 한 구조 방식이라고 생각하면 된다. 🥇 최소힙, 최대 힙 최소 힙은 작은 값을 항상 트리의 위에 두어, root에 가장 작은 값이 온다. 그렇기에 자식의 부모 요소는 자식보다 작다. 최대 힙은 가장 큰 값을 항상 트리의 위에 두어, root에 가장 큰 값이 온다. 그렇기에 자식의 부모요소는 자식보다 크다. 🥇 최소 힙에 노드 추가하기 완전 이진트리에 맞게 맨 마지막 레벨에 왼쪽부터 노드를 추가해준다. 추가한 노드의 값과 부모 요소를 비교하여 더 작으면 자리를 바꾼다. 부모 노드보다 작도록 반복한다. 한번 돌 때마다 절반식 경우가 줄어들기에 시간 복잡도는 ..
[알고리즘] 트리 (Tree)의 종류
트리 부모 자식의 관계를 가짐 계층이 있고, 그룹이 있음 노드가 하나이상의 자식을 가지기 때문 더 이상 자식이 없는 노드를 leaf라고 부름 트리의 종류 🎄 삼항 트리, 이진트리 삼항 트리 (Ternary tree) 최대 세개의 자식을 같은 구조 이진트리 (Binary Tree) 최대 두 개의 자식을 같은 구조 🎄 이진트리, 이진 검색 트리 이진트리 (Binary Tree) 최대 두 개의 자식을 같은 구조 -> 12를 찾는다고 할 때 2 레벨에서 9가 더 커서 오른쪽으로 이동해도 찾을 수가 없다. 이진 검색 트리 (BST : Binary Search Tree) 최대 두 개의 자식을 가지는 구조 노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이상이다. 이진 검색..
Java 개념 다시 공부하기 DAY1 - 객체, 클래스, 인스턴스, 필드, 메서드, 오버로딩
어제 알고리즘 스터디를 다녀와서 내가 static개념도 없구나..🫣 충격먹고 다시 개념잡기 위한 공부. 공부일 : 2022-05-18 공부범위 : p.212-p.269 학습 자료 : 혼자 공부하는 자바 - 신용권 지음 객체 속성과 동작을 가지고 있는 것. 자동차 객체는 색상, 인원수라는 속성을 가지고 있고, 달리다, 멈추다 라는 동작을 가지고 있다. 객체 호출 방식 객체. 메서드(매개 값 1, 매개 값 2..) 도트 연산자는 객체의 필드와 메서드에 접근할 때 사용한다. 클래스 객체는 하늘에서 갑자기 떨어지는 게 아니라 설계도를 통해 만들어내야 한다. 자바의 설계도가 클래스이다. 클래스에는 객체를 생성하기 위한 필드와 메서드가 정의되어있다. 클래스로부터 만들어진 객체를 해당 클래스의 인스턴스라고 한다. [..
알고리즘 공부를 위한 자료구조 알아보기 (Array, Hash Table, Stack, Queue)
자료 구조 데이터를 정리하는 것이다. 데이터를 어떻게 정리하냐(어떤 데이터 구조를 사용하냐)에 따라서 어플리케이션의 속도에 영향을 준다. 검색,읽기, 삽입, 삭제 4개가지 상황을 염두하고 데이터 구조를 보고 적절히 사용해야 한다. Array배열 reading 🟢 index값을 통해 간단히 값을 가져올 수 있다. searching 🔴 배열에서 값을 찾으려면 하나하나 체크하는 과정을 거쳐야 함으로 좋은 방법이 아니다. 이런 식으로 처음부터 끝까지 순차적으로 검색해야하는 것을 "Linear Search 선형 검색"이라고 한다. add 🟡 배열에 여분의 공간이 있을때, 맨 마지막에 값을 추가하는건 문제가 없다. 하지만 처음이나 중간에 값을 추가하거나 남아있는 공간이 없을 경우에는 기존의 값들이 이동하거나 복사까..
시간 복잡도(Big O)란 무엇인가?
코딩테스트를 준비하면서, 알고리즘에 대한 학습이 부족하다는 걸 깨닫고 공부 시작!👩🏻💻 ✔️시간 복잡도 데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고, 느린지 측정하는 방식이다. 알고리즘의 속도 측정 방식이다. 1초, 2초와 같은 시간을 측정하는 것이 아니라, 얼마나 많은 단계(steps)가 있는가로 측정한다. 즉, 단계가 적을수록 좋은 것이다. ▪️O(N) 선형 검색의 시간 복잡도(Linear Time Complexity)는 O(N)이라고 한다. array데이터 구조에서 10개를 선형검색하면선형 검색하면 10번의 step이 실행되고, 20개를 선형 검색하면 20개의 step이 실행된다. 즉, 인풋값과 step이 비례한다. 만약 for문을 두 번 돌리면 step이 두배가 되니까 O(2N)이 되..
[프로그래머스 Level1] 완주하지 못한 선수 - 나의 코드, 우수코드(Javascript)
🚨문제 https://programmers.co.kr/learn/courses/30/lessons/42576# 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 🔅예제 이해 출발한 사람 배열과 도착한 사람 배열을 비교하여 결승전에 도착하지 못한 한명이 누구인지 찾아내자 ☺️나의 코드 map(), Object.values(), Object.keys() function solution(participant, completion) { //1,2 const ob = {} participant.map..
[프로그래머스 Level1] 소수 만들기 - 나의 코드(Javascript)
🚨문제 https://programmers.co.kr/learn/courses/30/lessons/12977?language=javascript 코딩테스트 연습 - 소수 만들기 주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 programmers.co.kr 🔅예제 이해 숫자의 배열에서 3개를 골랐을 때 소수가 될 경우를 구합니다. ☺️나의 코드 Math.floor(), Math.sqrt() function solution(nums) { function isPrime(e){ //2은 무조건 소수이다. if(e === 2){ return true; } //..
[프로그래머스 Level1] 내적 - 나의 코드, 우수코드(Javascript)
🚨문제 https://programmers.co.kr/learn/courses/30/lessons/70128 코딩테스트 연습 - 내적 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 programmers.co.kr 🔅예제 이해 두배열의 곱을 모두 합친다. ☺️나의 코드 reduce() function solution(a, b) { var answer = a.reduce((prev, cur, i) => { return prev + (cur * b[i]) }, 0); return ans..
[프로그래머스 Level1] 음양 더하기 - 나의 코드, 우수코드(Javascript)
🚨문제 https://programmers.co.kr/learn/courses/30/lessons/76501 코딩테스트 연습 - 음양 더하기 어떤 정수들이 있습니다. 이 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어집니다. 실제 정수들의 합을 구하여 re programmers.co.kr 🔅예제 이해 true, false여부에 따라 증가, 감소시킨다. ☺️나의 코드 reduce() function solution(absolutes, signs) { var answer = absolutes.reduce((a,cur,i) => { if(signs[i] === true){ return a + cur; }else{ retu..