전체 글144 [Algorithm / Java] ✒️ Selection Sort(선택 정렬) Selection Sort란? Selection Sort는 Bubble Sort과 유사한 알고리즘으로, 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. Selection Sort와 Insertion Sort를 헷갈려하시는 분들이 종종 있는데, Selection Sort는 배열에서 해당 자리를 선택하고 그 자리에 오는 값을 찾는 것이라고 생각하면 편하다. Process (Ascending) 주어진 배열 중에 최솟값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. (pass) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. Code (Ascending) void selectionSort(int[] arr) { int indexMin, temp; f.. 2022. 8. 16. [Data Structure / Java] ✒️ Graph(그래프) 그래프란? 그래프는 정점과 간선으로 이루어진 자료구조이다. 정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수도 있다. 그런 면에서 트리는 그래프의 일종인 셈이다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 실생활에서 다양한 예를 그래프로 표현할 수 있다. 대표적으로 지하철 노선도, 도심의 도로 등이 있다. 이런 식으로 활용할 수 있는 방법이 많기에 문제도 다양하게 출제를 할 수 있다. 그래프는 알고리즘에서 굉장히 많이 사용된다. 특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알아두어야 한다. .. 2022. 8. 16. [Algorithm / Java] ✒️ Bubble Sort (거품 정렬) Bubble Sort란? Bubble Sort는 Selection Sort와 유사한 알고리즘으로 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. Process (Ascending) 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다. 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 .. 2022. 8. 15. [Data Structure / Java] ✒️ Vector Vector란? Vector는 ArrayList와 동일한 내부구조를 가지고 있다. ArrayList와 마찬가지로 Vector내부에 값이 추가되면 자동으로 크기가 조절되며 그다음 객체들은 한 자리씩 뒤로 이동된다. 하지만 Vector와 ArrayList의 한 가지 다른 점이 있는데 Vector는 동기화된 메소드로 구성되어 있기 때문에 멀티 스레드가 동시에 이 메소드들을 실행할 수 없고, 하나의 스레드가 실행을 완료해야만 다른 스레드들이 실행할 수 있다. 그래서 멀티 스레드 환경에서 안전하게 객체를 추가하고 삭제할 수 있다. Vector의 단점 (ArrayList와 비교) Vector는 항상 동기화된다는 장점이자 단점을 가지고 있다. 스레드가 1개일때도 동기화를 하기 때문에 ArrayList보다 성능이 떨어.. 2022. 8. 15. [Data Structure / Java] ✒️ Stack, Queue Stack이란? Stack이란 쌓아 올린다는 것을 의미. 따라서 Stack 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. Stack의 특징 Stack은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고,Top으로 정한 곳을 통해서만 접근할 수 있다.가장 위에 있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다.Stack에서 자료를 삭제할 때에도 top을 통해서만 가능하다. 데이터 넣기(Stack에서 top을 통해 삽입): push() 데이터 최상위 값 빼기(top을 통한 삭제): pop() 비어있는지 확인: isEmpty() 꽉 차 있는지 확인: isFull() 따라서 Stack.. 2022. 8. 15. [Data Structure / Java] ✒️ Map Array는 index로 빠르게 읽기는 좋은데 유연하지 못하고 ... List는 유연하기는 한데 index로 빠르게 읽기는 못하고... 유연하면서도 빠르게 읽어내는 방법이 없을까? Map Key와 Value로 이루어진 자료구조. 순차적으로 메모리에 데이터를 저장하는 Array와 List와는 달리 Key와 Value로 구성되어 있다. hashing: Key를 범위(배열 크기)에 맞게 적절히 겹치지 않는 index로 변경한다. hash function: hashing의 기능을 수행함, key값을 넣으면 hash값으로 변환하여 bucket의 index로 사용된다. bucket: Map의 Array hash collision: 해쉬 충돌, 이미 존재하는 key값에 다른 key값으로 같은 hash의 index를 .. 2022. 8. 12. [Data Structure / Java] ✒️ ArrayList와 LinkedList의 차이 List 개념 이해하기 자료구조 중 하나인 List는 배열의 한계를 극복할 수 있는 강력한 자료구조 중 하나이며 데이터를 단순하지만 효율적으로 다룰 수 있는 자료구조이다. List는 Array처럼 어떠한 데이터들을 묶기 위한 개념이다. Array와 대표적으로 다른 특징들은 아래와 같다. 데이터를 담을 공간의 추가가 가능하다. (Array는 초기 공간을 지정하기 때문에 한정적) 데이터를 담을 공간의 삭제가 가능하다. (Array는 데이터가 담기는 공간의 값을 변경할 수 있지만 그 공간을 삭제할 수 는 없다.) 즉, 크기가 가변적이다. List 인터페이스의 구현체에는 Stack, Vector, ArrayList, LinkedList가 있다. 이 중에서도 대표적인 클래스인 ArrayList와 LinkedLis.. 2022. 8. 8. [Data Structure / Java] ✒️ 시간 복잡도 시간 복잡도 입력되는 데이터의 증가에 따른 성능의 변화를 예측 1. O(1) int function(int[] n) { if(n.length < 3) return 0; int a = n[0]; a += n[1]; a += n[2]; return a; } int배열 n개가 들어오는데 몇개가 들어와도 메소드 안의 처리는 연산의 양은 변하지 않는다. 즉, 변화가 없이 항상 일정하다. 2. O(n) int sum(int[] n) { int s = 0; for (int index : n) { s += index; } return s; } int 배열 n개가 들어올 때 메소드 안의 처리하는 연산이 n번 수행된다. 입력되는 배열 n개에 따라 연산하는 양이 비례한다. 3. O(n^2) void bubbleSort(in.. 2022. 8. 4. [Data Structure / Java] ✒️ Call By Value / Call By Reference 함수 호출 방법에는 크게 두 가지가 있다. Call By Value (값에 의한 호출) - Primitive Type 기본 자료형 (int, short, long, float, double, char, boolean) 일 경우 Call By Reference (참조에 의한 호출) - Reference Type 참조 자료형 (Array, Class Instance) 일 경우 Call By Value (값에 의한 호출)는 인자로 받은 값을 복사하여 처리를 한다. Call By Reference (참조에 의한 호출)는 인자로 받은 값의 주소를 참조하여 직접 값에 영향을 준다. (주소 값을 넘긴다.) 다시 말해 값을 복사하여 처리하느냐, 직접 참조를 하느냐의 차이. Programming 구조상 Call By V.. 2022. 8. 4. [Data Structure / Java] ✒️ 컴퓨터가 데이터를 다루는 방법 Java는 데이터를 어떻게 표현하는가 Java는 크게 두 가지 Data Type을 사용한다. Primitive Reference (Object) Primitive Type와 Reference Type이 어떻게 다른지를 이해하기 위해서는 이 타입들이 컴퓨터 메모리에서 어떻게 존재하는지를 이해해야 한다. Primitive Type은 ? int i = 42; float pi = 3.14; boolean b = true; i 라는 int 변수 하나가 만들어져 있다. 이 변수는 메모리 상 어딘가에 42라는 값이 저장이 된다. 우리는 i라는 변수를 사용하면 메모리에서 42라는 값을 꺼내와서 사용할 수 있다. pi 라는 float 변수와 b 라는 boolean 변수도 동일하게 pi 나 b 라는 변수를 사용하여 메모리.. 2022. 8. 3. 이전 1 2 3 4 5 ··· 15 다음
